If you're seeing this message, it means we're having trouble loading external resources on our website.

Jeżeli jesteś za filtrem sieci web, prosimy, upewnij się, że domeny *.kastatic.org i *.kasandbox.org są odblokowane.

Główna zawartość

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.

Problem komiwojażera

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:
46 dots labeled as German cities. A line goes through the dots, going through each of them exactly once.
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.

Metoda brute force

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:
MiastaŚcieżkiMilisekundy
460,1
5240,3
61200,8
77203
85.04010
940.32050
10362.880520
113.628.8005.770
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, start superscript, 53, end superscript milisekund, aby obliczyć trasy dla 46 niemieckich miast z wcześniejszego diagramu. To około 6, start superscript, 42, end superscript 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, start superscript, 37, end superscript lat.
Jak więc obliczono powyższą ścieżkę 46 miast? Oczywiście za pomocą heurystyki!

Opracowywanie 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.

Heurystyka najbliższego sąsiada

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.

Heurystyki są wszędzie

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.
Grafika przedstawiająca plecak i 4 pudełka. Plecak ma napis "15 kg". Pudełko 1 ma napis "12 kg" i kosztuje 4 dolary. Pudełko 2 ma napis "2 kg" i kosztuje 2 dolary. Pudełko 3 ma napis "4 kg" i kosztuje 10 dolarów. Pudełko 4 ma napis 1 kg i kosztuje dolara.
Prosty problem z plecakiem o łącznej wadze 15 kg i 4 rodzajach przedmiotów.
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, point, 880 możliwych przypadków, ale w odniesieniu do bardziej skomplikowanej gry, takiej jak szachy, jest to już 10, start superscript, 120, end superscript przypadków! Na szczęście heurystyki, takie jak "minimax", pomagają ograniczyć drzewo możliwości.
Diagram drzewiasty z trzema poziomami. Na pierwszym poziomie jest pusta plansza do gry w Kółko i krzyżyk. Na drugim poziomie widać trzy plansze do gry w Kółko i krzyżyk, a na każdej z nich krzyżyk znajduje się w innym miejscu. Na trzecim poziomie znajduje się 12 plansz, a na każdej z nich jest także kółko.
Częściowe drzewo gry dla gry Kółko i krzyżyk.
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.
Dwuczęściowy diagram. W pierwszej części przedstawiono 20 niebieskich kropek rozmieszczonych na prostokątnej powierzchni. W drugiej części przedstawiono 5 różowych kropek rozmieszczonych wśród tych kropek, a strzałki łączą każdą różową kropkę z kropką niebieską.
20 lokalizacji i możliwe rozwiązanie z 5 centrami logistycznymi.
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ń!