Producenci arkuszy (tafle szkła, płyty wiórowe, płyty kamienne, blacha, itp) wytwarzają materiał, o wymiarach znacznie przekraczających potrzeby zwykłych klientów. W momencie otrzymania zlecenia, firma staje przed poważnym problemem. Musi z dużego arkusza wyciąć mniejsze formatki. Doświadczony fachowiec potrafi w głowie poukładać formatki na arkuszu tak, aby odpad był jak najmniejszy. Jednak proszę sobie wyobrazić taką sytuację, że mamy 10 arkuszy i 100 różnych formatek do wycięcia. Żaden człowiek nie jest w stanie ich tak poukładać, aby układ był optymalny, czyli żeby odpad był jak najmniejszy.
Problem jest podobny do kostki rubika. Mamy ułożoną kostkę – każda ściana jest w jednym kolorze. Teraz dowolnie, kilkakrotnie przekręcamy kolory w różnych kierunkach. W wyniku otrzymujemy kostkę z różnokolorowymi ściankami. Ponowne ułożenie, dla niedoświadczonej osoby, jest bardzo trudne. Po prostu jest tyle kombinacji, że trudno jest sobie to wszystko wyobrazić. Tak samo jest z małymi formatkami na dużym arkuszu, zwłaszcza gdy formatek jest dużo więcej niż może się zmieścić na jednej płaszczyźnie. Kombinacji są miliony, a nawet miliardy. Nawet komputer, analizując wszystkie możliwości, nie jest w stanie rozwiązać tego w rozsądnym czasie.
Powróćmy na chwilę do ostatniego przykładu – 100 formatek. Sama próba brania ich pod uwagę w różnej kolejności daje nam 100! (100 silnia) kombinacji, czyli około 9,33×10157. Liczba jest ogromna. A trzeba jeszcze wziąć pod uwagę, że formatka może być położona w pozycji poziomej lub pionowej, z lewej lub prawej strony. Dodatkowo dochodzi warunek, że arkusz może być cięty tylko po linii prostej – zawsze na dwie części. Tak więc, widać że problem nie jest prosty.
Takiej ilości kombinacji nie jest chyba w stanie przeliczyć żaden komputer na ziemi – w rozsądnym czasie oczywiście. Ale, całe szczęście istnieje dziedzina informatyki, która zajmuje się rozwiązywaniem takich problemów. Chodzi tu o optymalizację. Jak sama nazwa wskazuje, dziedzina ta zajmuje się optymalizacją procesu wyszukiwania. Polega to na tym, że nie są sprawdzane wszystkie kombinacje, ale tylko te, które mogą dać lepszy wynik od aktualnego.
Ostatnie komentarze