Użycie heurystyki

Najtrudniejsze problemy w informatyce to te, które rozwiązuje się w czasie ponadwielomianowym, podwajając liczbę wymaganych kroków za każdym razem, gdy zwiększa się rozmiar danych wejściowych — a nawet więcej niż podwajając! Komputery mogą rozwiązywać takie problemy dla bardzo małych rozmiarów danych wejściowych, ale bardzo szybko dochodzą do punktu, w którym ich rozwiązanie może zająć miesiące lub lata.

Informatycy stosują inne podejście do rozwiązywania tych trudnych problemów: zamiast próbować znaleźć idealne rozwiązanie, próbują znaleźć rozwiązanie przybliżone. Dobra odpowiedź jest lepsza niż żadna.

Jednym ze sposobów uzyskiwania przybliżonych odpowiedzi na problem jest zastosowanie heurystyki — technika, która prowadzi algorytm do znalezienia dobrych wyborów. Gdy algorytm korzysta z heurystyki, nie musi już dokładnie przeszukiwać wszystkich możliwych rozwiązań, więc może szybciej znajdować rozwiązania przybliżone. Heurystyka to droga na skróty, która traci na dokładności i kompletności.

Aby lepiej zrozumieć heurystykę, prześledźmy jeden z najsłynniejszych trudnych problemów informatycznych.

W problemie podróżującego komiwojażera postawiono następujące pytanie:

"Biorąc pod uwagę listę miast i odległości między każdą parą miast, jaka jest najkrótsza możliwa trasa, która odwiedza każde miasto i wraca do miasta początkowego?".

Na przykład ten diagram przedstawia najkrótszą trasę między 46 niemieckimi miastami:

Problem komiwojażera był pierwotnie rozwiązywany przez podróżujących sprzedawców, ale w rzeczywistości dotyczy wielu dziedzin: trasowania danych w sieci, produkcji mikroprocesorów, obserwacji miejsc za pomocą teleskopu, a nawet sekwencjonowania DNA. We wszystkich tych przypadkach chcemy znaleźć rozwiązanie, które pozwoli nam znaleźć efektywną ścieżkę między wieloma miejscami.

Problem komiwojażera jest problemem kombinatorycznym i właśnie dlatego jest tak trudny. Jedynym sposobem, w jaki komputer może znaleźć optymalne rozwiązanie, jest "podejście siłowe" (ang. brute force approach): wypróbuj wszystkie możliwe ścieżki między miastami, zmierz odległość każdej z nich i wybierz ścieżkę o najmniejszej odległości.

Poniższa wizualizacja generuje cztery losowe miasta, oblicza możliwe ścieżki i zaznacza ścieżkę optymalną. Kliknij na ścieżki, aby zobaczyć, jakie możliwości zostały zaproponowane, lub zacznij od nowa, aby spróbować z nowym zestawem miast.

Czy zauważyłeś, że zawsze generowane są dwie optymalne ścieżki? Ścieżki wyglądają tak samo, ale są w odwrotnej kolejności. Technicznie rzecz biorąc, oba rozwiązania są optymalne, a sprzedawca może wybrać jedną najkrótszą ścieżkę zamiast drugiej z powodów niezwiązanych z odległością.

Wygenerowanie możliwych ścieżek dla 4 miast nie zajmuje komputerowi zbyt wiele czasu — na moim komputerze jest to mniej niż dziesiąta część milisekundy. Jest to dość szybkie nawet dla 5 miast, 6 miast i 7 miast; możesz spróbować samemu, jeśli masz zaufanie do swojego komputera. Czas działania rośnie jednak wykładniczo, więc kilka milisekund wkrótce zamieni się w kilka sekund.

Oto tabela czasów wykonania dla miast od 4 do 11 na moim komputerze:

Zauważyłeś skok z 520 do 5770 na końcu? To właśnie wtedy postanowiłem ulitować się nad moim biednym laptopem i nie iść wyżej.

W tym tempie komputer potrzebowałby około $2^{53}$‍ milisekund, aby obliczyć trasy dla 46 niemieckich miast z wcześniejszego diagramu. To około $6^{42}$‍ lata, czyli znacznie dłużej, niż istnieje wszechświat. Oczywiście istnieją komputery o większej mocy niż mój laptop, ale nawet superkomputer, który jest 200 000 razy potężniejszy, potrzebowałby $3^{37}$‍ lat.

Jak więc obliczono powyższą ścieżkę 46 miast? Oczywiście za pomocą heurystyki!

Jednym ze sposobów wymyślenia heurystyki jest zastanowienie się, jak sami podeszlibyśmy do danego problemu. Ludzie nie lubią marnować niepotrzebnego wysiłku na rozwiązywanie problemów, więc często znajdujemy skróty, które prowadzą nas do wystarczająco dobrego rozwiązania.

Poniższa wizualizacja przedstawia 5 losowych miast. Zaproponuj najkrótszą ścieżkę, klikając miasta, zaczynając od następnego miasta z punktu A. Po zakończeniu sprawdź, jak Twoja ścieżka wypada w porównaniu z optymalną ścieżką.

Jak wypadła Twoja trasa w porównaniu z trasą optymalną? Jakich heurystyk użyłeś, aby zdecydować o kolejności odwiedzania miast? Czy komputer mógłby zastosować tę samą heurystykę?

Nie wszystkie heurystyki są jednakowe, ale wszystkie mogą dostarczyć nam pomysłów na różne sposoby prowadzenia komputera w celu szybszego znalezienia dobrego rozwiązania.

Często stosowaną heurystyką w rozwiązywaniu problemu komiwojażera jest "najbliższy sąsiad": komputer zawsze wybiera najbliższe nieodwiedzone miasto jako następne miasto na ścieżce.

Wypróbuj to na poniższej wizualizacji. Teraz, gdy używamy heurystyki, możesz wypróbować tę metodę dla znacznie większej liczby miast niż poprzednio. Na moim komputerze nawet 46 miast zajmuje zaledwie kilka milisekund.

Imponujące, prawda? Bez heurystyki moglibyśmy czekać aż do śmierci cieplnej wszechświata, aby znaleźć idealne rozwiązanie. Teraz, dzięki prostej heurystyce, wyniki widzimy niemal natychmiast.

Pamiętaj jednak, że heurystyka daje tylko przybliżone rozwiązanie. W przypadku tej konkretnej heurystyki rozwiązanie będzie średnio o około 25% dłuższe niż najkrótsza możliwa ścieżka. Zdarzają się nawet sytuacje, gdy heurystyka najbliższego sąsiada wyznaczy najgorszą trasę.

Informatycy wymyślili dziesiątki innych heurystyk dla problemu komiwojażera, w tym "optymalizację kolonii mrówek", heurystykę zainspirowaną sposobem, w jaki mrówki wysyłają feromony wzdłuż ścieżki. Dla każdej z heurystyk przeanalizowano, jak bardzo zbliża się ona do znalezienia idealnego rozwiązania, ile czasu to zajmuje i jak często zdarza się najgorszy przypadek.

Oprócz problemu komiwojażera istnieje wiele problemów, w których można skorzystać z heurystyki.

Oto kilka z nich:

Problem plecakowy: Masz plecak i zestaw przedmiotów, z których każdy ma swoją wagę i wartość. Ile każdego z tych przedmiotów możesz zapakować, aby łączna waga nie przekroczyła limitu, a łączna wartość była jak największa? Tego typu problem występuje w wielu postaciach w różnych branżach, np. doradcy finansowi wybierają inwestycje do portfela lub fabryki zastanawiają się nad optymalnym sposobem pocięcia surowców. Jedną z heurystyk jest sortowanie według stosunku wartości do wagi przy wyborze kolejnego przedmiotu do spakowania.

Granie w gry: Aby komputer mógł pokonać człowieka w grze (lub przynajmniej przegrać w rozsądny sposób), musi wybrać ruch, który ma największe szanse powodzenia. Aby móc naprawdę przewidzieć zwycięstwo, komputer musi obliczyć całe drzewo gry, od bieżącego ruchu do ostatniego, przewidując wszystkie ruchy, które człowiek może wykonać w odpowiedzi. W przypadku prostej gry w Kółko i krzyżyk daje to $362.880$‍ możliwych przypadków, ale w odniesieniu do bardziej skomplikowanej gry, takiej jak szachy, jest to już ${10}^{120}$‍ przypadków! Na szczęście heurystyki, takie jak "minimax", pomagają ograniczyć drzewo możliwości.

Lokalizacja centrów dystrybucyjnych: Wyobraźmy sobie sieć supermarketów, która ma 20 placówek w pewnym województwie i chce wybudować 5 magazynów, aby dostarczać żywność do supermarketów. Ich celem jest minimalizacja kosztów i maksymalizacja szybkości dostaw. Problem lokalizacji centrów dystrybucyjnych polega na znalezieniu optymalnej lokalizacji dla tych pięciu magazynów. Z tym samym problemem borykają się aplikacje internetowe, które chcą rozlokować swoje zapasowe serwery, aby szybko reagować na żądania użytkowników. Heurystyki takie jak "wyszukiwanie lokalne" pomagają zawęzić listę możliwych lokalizacji.

Wszystkie te problemy są problemami kombinatorycznymi, w przypadku których komputer musiałby przeszukiwać rosnącą wykładniczo liczbę kombinacji, aby znaleźć optymalną odpowiedź. Problemy kombinatoryczne są dość powszechne w świecie rzeczywistym, dlatego zarówno firmy, jak i informatycy bardzo starają się znaleźć heurystyki, które dadzą najlepsze przybliżone rozwiązania.

🙋🏽🙋🏻‍♀️🙋🏿‍♂️Czy masz jakieś pytania na ten temat? Chętnie na nie odpowiemy — wystarczy, że zadasz pytanie w poniższym obszarze pytań!