Algorytm zachłanny - Greedy algorithm

Algorytmy zachłanne określają minimalną liczbę monet, które należy rozdać podczas dokonywania zmian. Są to kroki, które większość ludzi podjęłaby, aby naśladować zachłanny algorytm reprezentujący 36 centów, używając tylko monet o wartościach {1, 5, 10, 20}. Moneta o najwyższej wartości, mniejszej niż pozostała należna zmiana, jest lokalnym optimum. (Ogólnie rzecz biorąc, problem wprowadzania zmian wymaga dynamicznego programowania, aby znaleźć optymalne rozwiązanie; jednak większość systemów walutowych, w tym euro i dolar amerykański, to szczególne przypadki, w których strategia zachłanna znajduje optymalne rozwiązanie.)

Zachłanny algorytm jest jakiś algorytm , który następuje po rozwiązywania problemów heurystyki składania lokalnie optymalny wybór na każdym etapie. W wielu problemach strategia zachłanna nie daje optymalnego rozwiązania, ale zachłanna heurystyka może dostarczyć lokalnie optymalne rozwiązania, które przybliżają rozwiązanie optymalne globalnie w rozsądnym czasie.

Na przykład zachłanna strategia dla problemu komiwojażera (która ma dużą złożoność obliczeniową) to następująca heurystyka: „Na każdym etapie podróży odwiedź najbliższe nieodwiedzone miasto”. Ta heurystyka nie ma na celu znalezienia najlepszego rozwiązania, ale kończy się rozsądną liczbą kroków; znalezienie optymalnego rozwiązania tak złożonego problemu zazwyczaj wymaga bezzasadnie wielu kroków. W optymalizacji matematycznej algorytmy zachłanne optymalnie rozwiązują problemy kombinatoryczne o właściwościach matroidów i dają aproksymacje stałoczynnikowe do problemów optymalizacyjnych ze strukturą submodularną.

Specyfika

Ogólnie algorytmy zachłanne składają się z pięciu elementów:

1. Zbiór kandydacki, z którego tworzone jest rozwiązanie
2. Funkcja selekcji, która wybiera najlepszego kandydata do dodania do rozwiązania
3. Funkcja wykonalności, która służy do określenia, czy kandydat może zostać wykorzystany do wniesienia wkładu w rozwiązanie
4. Funkcja celu, która przypisuje wartość rozwiązaniu lub rozwiązaniu częściowemu, oraz
5. Funkcja rozwiązania, która wskaże, kiedy odkryliśmy kompletne rozwiązanie

Algorytmy zachłanne dają dobre rozwiązania niektórych problemów matematycznych , ale nie innych. Większość problemów, nad którymi pracują, będzie miała dwie właściwości:

Chciwy wybór nieruchomości

Możemy dokonać wyboru, który w danej chwili wydaje się najlepszy, a następnie rozwiązać pojawiające się później podproblemy. Wybór dokonany przez zachłanny algorytm może zależeć od wyborów dokonanych do tej pory, ale nie od przyszłych wyborów lub wszystkich rozwiązań podproblemu. Iteracyjnie dokonuje jednego chciwego wyboru za drugim, redukując każdy dany problem do mniejszego. Innymi słowy, zachłanny algorytm nigdy nie zastanawia się nad swoimi wyborami. Jest to główna różnica w porównaniu z programowaniem dynamicznym , które jest wyczerpujące i gwarantuje znalezienie rozwiązania. Po każdym etapie programowanie dynamiczne podejmuje decyzje na podstawie wszystkich decyzji podjętych w poprzednim etapie i może ponownie rozważyć algorytmiczną ścieżkę do rozwiązania z poprzedniego etapu.

Optymalna podbudowa

„Problem wykazuje optymalną podstrukturę, jeśli optymalne rozwiązanie problemu zawiera optymalne rozwiązania podproblemów”.

Przypadki awarii

Przykłady tego, jak zachłanny algorytm może nie osiągnąć optymalnego rozwiązania.

Zaczynając od A, zachłanny algorytm, który próbuje znaleźć maksimum, podążając za największym nachyleniem, znajdzie lokalne maksimum w „m”, nie zwracając uwagi na globalne maksimum w „M”.

Aby osiągnąć największą sumę, na każdym kroku algorytm zachłanny wybierze to, co wydaje się być optymalnym wyborem natychmiastowym, więc wybierze 12 zamiast 3 w drugim kroku i nie osiągnie najlepszego rozwiązania, które zawiera 99.

Algorytmy zachłanne nie są w stanie stworzyć optymalnego rozwiązania dla wielu innych problemów, a nawet mogą stworzyć unikalne najgorsze możliwe rozwiązanie. Jednym z przykładów jest wspomniany powyżej problem komiwojażera : dla każdej liczby miast przypisywane są odległości między miastami, dla których heurystyka najbliższego sąsiedztwa tworzy unikalną najgorszą możliwą trasę. Inne możliwe przykłady, patrz efekt horyzontu .

Rodzaje

Algorytmy zachłanne można scharakteryzować jako „krótkowzroczne”, a także „nieodwracalne”. Są idealne tylko w przypadku problemów, które mają „optymalną podbudowę”. Mimo to, w przypadku wielu prostych problemów, najlepiej nadające się algorytmy są zachłanne. Należy jednak zauważyć, że algorytm zachłanny może być używany jako algorytm wyboru do ustalania priorytetów opcji w ramach wyszukiwania lub algorytm rozgałęzienia i ograniczenia. Istnieje kilka odmian algorytmu zachłannego:

• Czyste zachłanne algorytmy
• Ortogonalne algorytmy zachłanne
• Zrelaksowane zachłanne algorytmy

Teoria

Algorytmy zachłanne mają długą historię badań w zakresie optymalizacji kombinatorycznej i informatyki teoretycznej . Wiadomo, że zachłanne heurystyki dają nieoptymalne wyniki w wielu problemach, więc naturalne pytania to:

• W przypadku jakich problemów zachłanne algorytmy radzą sobie optymalnie?
• Dla jakich problemów zachłanne algorytmy gwarantują w przybliżeniu optymalne rozwiązanie?
• Dla jakich problemów algorytm zachłanny gwarantuje, że nie stworzy optymalnego rozwiązania?

Istnieje obszerna literatura odpowiadająca na te pytania dla ogólnych klas problemów, takich jak matroids , a także dla konkretnych problemów, takich jak set cover .

Matroidy

Matroid jest strukturą matematyczną że uogólnia pojęcie liniowej niezależności od przestrzeni wektorowej do dowolnych zestawów. Jeśli problem optymalizacyjny ma strukturę matroidu, to odpowiedni algorytm zachłanny rozwiąże go optymalnie.

Funkcje submodułowe

Funkcja zdefiniowana na podzbiorach zbioru nazywana jest submodularną, jeśli dla każdego mamy to . ${\displaystyle f}$${\ Displaystyle \ Omega}$${\ Displaystyle S, T \ subseteq \ Omega}$${\ Displaystyle f (S) + f (T) \ geq f (S \ kubek T) + f (S \ czapka T)}$

Załóżmy, że ktoś chce znaleźć zestaw, który maksymalizuje . Algorytm zachłanny, który buduje zestaw poprzez przyrostowe dodawanie elementu, który zwiększa się najbardziej na każdym kroku, daje jako wynik zestaw, który wynosi co najmniej . Oznacza to, że chciwy działa w stałym współczynniku tak dobrym, jak optymalne rozwiązanie. ${\displaystyle S}$${\displaystyle f}$${\displaystyle S}$${\displaystyle f}$${\ Displaystyle (1-1/e) \ max _ {X \ subseteq \ Omega} f (X)}$${\ Displaystyle (1-1/e) \ około 0,63}$

Podobne gwarancje można udowodnić, gdy na dane wyjściowe nakładane są dodatkowe ograniczenia, takie jak ograniczenia kardynalności, chociaż często wymagane są niewielkie zmiany algorytmu zachłannego. Zobacz przegląd.

Inne problemy z gwarancjami

Inne problemy, dla których zachłanny algorytm daje silną gwarancję, ale nie optymalne rozwiązanie, to:

• Ustaw okładkę
• Drzewo problemem Steiner
• Równoważenie obciążenia
• Niezależny zestaw

Wiele z tych problemów ma dopasowane dolne granice; tzn. zachłanny algorytm nie działa lepiej niż gwarancja w najgorszym przypadku.

Aplikacje

Algorytmy zachłanne zazwyczaj (ale nie zawsze) nie znajdują globalnie optymalnego rozwiązania, ponieważ zwykle nie operują wyczerpująco na wszystkich danych. Mogą zbyt wcześnie zobowiązać się do pewnych wyborów, uniemożliwiając im późniejsze znalezienie najlepszego ogólnego rozwiązania. Na przykład, wszystkie znane algorytmy zachłannego kolorowania problemu kolorowania grafów i wszystkich innych problemów NP-zupełnych nie znajdują konsekwentnie optymalnych rozwiązań. Niemniej jednak są one przydatne, ponieważ szybko się wymyślają i często dają dobre przybliżenia do optimum.

Jeśli można udowodnić, że algorytm zachłanny daje globalne optimum dla danej klasy problemu, zwykle staje się on metodą z wyboru, ponieważ jest szybszy niż inne metody optymalizacji, takie jak programowanie dynamiczne . Przykłady takich chciwych algorytmów Algorytm Kruskala i Algorytm Prima znalezienia minimum drzew rozpinających i Algorytm dla znalezienia optymalnego drzew Huffmana .

Algorytmy zachłanne pojawiają się również w routingu sieciowym . Wykorzystując routing zachłanny, wiadomość jest przekazywana do sąsiedniego węzła, który jest „najbliżej” miejsca docelowego. Pojęcie lokalizacji węzła (a tym samym „bliskość”) może być określone przez jego fizyczną lokalizację, tak jak w przypadku trasowania geograficznego używanego przez sieci ad hoc . Lokalizacja może być również całkowicie sztuczną konstrukcją, jak w przypadku routingu małego świata i rozproszonej tablicy mieszającej .

Przykłady

• Problemem wyboru aktywność jest charakterystyczne dla tej klasy problemów, gdzie celem jest, aby wybrać maksymalną liczbę działań, które nie kolidowały ze sobą.
• W komputerze Macintosh gry Kryształ Quest celem jest zbierać kryształy, w sposób podobny do problemu komiwojażera . Gra posiada tryb demo, w którym gra wykorzystuje zachłanny algorytm, aby przejść do każdego kryształu. Sztuczna inteligencja nie stanowią przeszkody, więc tryb demo często kończy się szybko.
• Poszukiwanie dopasowujące jest przykładem algorytmu zachłannego stosowanej na aproksymacji sygnału.
• Chciwy algorytm znajduje optymalne rozwiązanie problemu Malfattiego polegającego na znalezieniu trzech rozłącznych okręgów w danym trójkącie, które maksymalizują całkowitą powierzchnię okręgów; przypuszcza się, że ten sam zachłanny algorytm jest optymalny dla dowolnej liczby kręgów.
• Algorytm zachłanny jest używany do skonstruowania drzewa Huffmana podczas kodowania Huffmana, gdzie znajduje optymalne rozwiązanie.
• W uczeniu drzew decyzyjnych powszechnie stosuje się algorytmy zachłanne, jednak nie gwarantuje się ich znalezienia optymalnego rozwiązania.
  • Jednym z popularnych takich algorytmów jest algorytm ID3 do budowy drzew decyzyjnych.
• Algorytm Dijkstry i powiązany z nim algorytm przeszukiwania A* są weryfikowalnymi optymalnymi algorytmami zachłannymi do przeszukiwania grafów i znajdowania najkrótszej ścieżki .
  • Wyszukiwanie A* jest warunkowo optymalne i wymaga „ dopuszczalnej heurystyki ”, która nie przeszacowuje kosztów ścieżki.
• Algorytm Kruskala i Algorytm Prima są chciwi algorytm konstruowania minimalne drzew rozpinających danego podłączonego wykresie . Zawsze znajdują optymalne rozwiązanie, które generalnie może nie być unikalne.

Zobacz też

Bibliografia

Źródła

Zewnętrzne linki

• „Algorytm zachłanny” , Encyklopedia Matematyki , EMS Press , 2001 [1994]
• Prezent, Noe. „Przykład chciwej monety w Pythonie” .