Ocena brak

Na czym polega metoda algorytmiczna zwana „zachłanną”?

Autor /Barnim7777 Dodano /29.12.2011

Istnieją zadania, których rozwiązanie można budować z dobieranych kolejno elementów i do takich właśnie zadań przeznaczona jest metoda zachłanna. Postępuje ona zawsze zgodnie z zasadą „łap co masz najlepszego pod ręką i nigdy nie oddawaj tego co już masz”. Jest to metoda efektywna tylko w pewnej grupie problemów.

Przykładem zastosowania metody „zachłannej” jest algorytm poszukiwania najtańszej sieci wiążącej wszystkie podane punkty (czyli budowanie minimalnego drzewa rozpinającego w zadanym grafie). Mając daną sieć punktów połączonych odcinkami o podanej wadze wybieramy najtańszy. Potem wybieramy najtańszy odchodzący od punktów które już mamy itd. Czynność powtarzamy do chwili kiedy nie połączymy wszystkich oznaczonych na płaszczyźnie punktów.

Opis algorytmu:

1. wybierz odcinek o najmniejszej wadze

2. powtarzaj co następuje aż do połączenia wszystkich punktów na płaszczyźnie:

- wybierz najtańszy odcinek łączący punkt który już masz, z tym dowolnym który nie jest jeszcze przyłączony

Metoda ta daje bardzo dobre wyniki gdy poszukiwana jest najtańsza wagowo ścieżka połączeń wszystkich punktów na płaszczyźnie (tzw. minimalne drzewo rozpinające). Nie daje jednak poprawnych wyników gdy wykorzystuje się ją do np.: poszukiwania najtańszej drogi łączącej dwa wskazane punkty na płaszczyźnie.

Podobne prace

Do góry