Spisu treści:
Definicja - Co oznacza Chciwy Algorytm?
Chciwy algorytm to strategia algorytmiczna, która dokonuje najlepszego optymalnego wyboru na każdym małym etapie, aby ostatecznie doprowadzić do optymalnego globalnie rozwiązania. Oznacza to, że algorytm wybiera obecnie najlepsze rozwiązanie bez względu na konsekwencje. Wybiera najlepsze natychmiastowe wyjście, ale nie bierze pod uwagę dużego obrazu, dlatego jest uważane za chciwe.
Techopedia wyjaśnia Chciwy Algorytm
Chciwy algorytm działa, wybierając najlepszą możliwą odpowiedź na każdym kroku, a następnie przechodząc do następnego kroku, aż dojdzie do końca, bez względu na ogólne rozwiązanie. Ma tylko nadzieję, że ścieżka, którą podąża, jest globalnie optymalna, ale jak wielokrotnie udowodniono, ta metoda często nie daje globalnie optymalnego rozwiązania. W rzeczywistości jest całkowicie możliwe, że najbardziej optymalne rozwiązania krótkoterminowe prowadzą do najgorszego możliwego globalnego rezultatu.
Pomyśl o tym jako o wielu skrótach w branży produkcyjnej: w krótkim okresie duże koszty są oszczędzane na kosztach produkcji, ale ostatecznie prowadzi to do spadku, ponieważ jakość jest zagrożona, co powoduje zwroty produktów i niską sprzedaż, gdy klienci zapoznają się z „Tani” produkt. Ale nie zawsze tak jest, istnieje wiele aplikacji, w których chciwy algorytm działa najlepiej w celu znalezienia lub przybliżenia optymalnego globalnie rozwiązania, takiego jak przy tworzeniu drzewa Huffmana lub drzewa uczenia się decyzji.
Na przykład: Wybierz ścieżkę z największą sumą. Chciwy algorytm wybrałby niebieską ścieżkę z powodu krótkowzroczności, a nie pomarańczową, co daje największą sumę.
Składniki:
- Zestaw danych kandydata, który potrzebuje rozwiązania
- Funkcja wyboru, która wybiera najlepszego współtwórcę ostatecznego rozwiązania
- Funkcja wykonalności, która wspomaga funkcję selekcji poprzez określenie, czy kandydat może przyczynić się do rozwiązania
- Funkcja celu, która przypisuje wartość do rozwiązania częściowego
- Funkcja rozwiązania wskazująca, że odkryto optymalne rozwiązanie
