| Startuj z nami | Strona główna | Powrót | Kontakt | Linki | 
Wstęp
 »Definicja i własności
 »Cechy algortmów
 »Zapis algortmów
 »Uwagi końcowe
Algorytmy
 »Rekurencja
 »Algorytmy zachłanne
 »Drzewo minimalne
 »Minimalna ścieżka
 »Problem komiwojażera
 »Problem 5 filozofów
 »Problem konika szach.
 »Problem powłoki
 »Złożoność obliczeniowa
 »Problemy NP zupełne
Algorytmy sortujące
 »Wstęp
 »Sort. bąbelkowe
 »Sort. przez wybieranie
 »Sort. przez wstawianie
 »Sort. metodą Shella
 »Sort. przez scalanie
 »Sort. przez kopcowanie
 »Sort. szybkie
Struktury danych
 »Wstęp
 »Stos
 »Kolejka
 »Lista
 »Drzewa
 »Grafy
Statystyki
Licznik odwiedzin :
Reklama

Nakarm głodne dziecko - wejdź na stronę www.Pajacyk.pl

Def. Algorytm zachłanny ( ang. greedy algorithm) wykonuje zawsze działanie, które wydaje się w danej chwili najkorzystniejsze. Wybiera zatem lokalnie optymalną możliwość w nadziei, że doprowadzi ona do globalnie optymalnego rozwiązania.

Problem kasjera

Problem
Kasjer ma wydać resztę, będącą dowolną kwotą między 0,01PLN a 0,99PLN, przy użyciu minimalnej liczby monet. Rozwiązanie oparte na algorytmie zachłannym Najpierw używamy monety o największej dopuszczalnej wartości, redukując w ten sposób problem do wypłacenia mniejszej kwoty.

Ogólne własności metody zachłannej

Jak przekonać się czy zastosowanie strategii zachłannej daje optymalne rozwiązanie problemu? Problemy, dla których może być zastosowana strategia zachłanna mają dwie cechy charakterystyczne:
  • własność wyboru zachłannego,
  • własność optymalnej podstruktury.

a) Własność wyboru zachłannego

Jeżeli wybory "lokalne" są optymalne, to wybór "globalny" (ostateczny) jest optymalny. Różnica między strategią zachłanną a programowaniem dynamicznym polega na tym, że w programowaniu dynamicznym w każdym kroku podejmowane są decyzje, których wybór zależy od rozwiązań podproblemów. W algorytmie zachłannym wybory są podejmowane jako najlepsze (z punktu widzenia zadania) w danej chwili. Wybory podejmowane w algorytmie zachłannym nie są zależne od wyborów przeszłych, w przeciwieństwie do wyborów podejmowanych przy strategii programowania dynamicznego. Można formalnie udowodnić (stosując metodę indukcji), że dany problem ma własność wyboru zachłannego.

b) Własność optymalnej podstruktury

Problem ma własność optymalnej podstruktury, jeżeli optymalne rozwiązanie jest funkcją optymalnych rozwiązań podproblemów. Ta własność jest również spełniona dla problemów rozwiązywalnych metodą programowania dynamicznego.
 Strona główna     Powrót     Do góry