algorytm.org

Metoda zachłanna

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Metoda zachłanna
Ocena użytkowników:***** / 53
SłabyŚwietny 
Wpisany przez Michał Knasiecki, 01 sierpnia 2005 22:13

Jeżeli mamy daną kombinację danych, które mogą być rozwiązaniem danego problemu można się posłużyć metodą "zachłanną". Metoda "zachłanna" polega na rozpatrywaniu danych w kolejności uporządkowanej, np. posortowane. W danym kroku wybierane są te dane, które są najodpowiedniejsze. Najczęściej metoda ta prowadzi do otrzymania rozwiązania przybliżonego, choć istnieją problemy, dla których metoda zachłanna daje roziwązanie optymalne (jest tak, gdy problem ten daje się przedstawić w postaci matroidu zob: minimalne drzewo rozpinające).
Przykład:
Znaleźć w macierzy A taki podzbiór elementów, że
  1. w każdej kolumnie znajduje się co najmniej jeden wybrany element
  2. suma elementów wybranych jest maksymalna
Optymalny algorytm oparty o metodę zachłanną przedstawia się następująco:
Wybieraj kolejne elementy o maksymalnych wartościach, dla których spełniony jest warunek 1.

"Zachłanność" tego algorytmu polega na wybieraniu największego elementu, czyli elementu najbardziej odpowiedniego w danej chwili (nie interesują nas wybory dokonane w przeszłości). Powyższy problem można łatwo zmodyfikować do postaci, której nie można rozwiązać algorytmem zachłannym, dodajmy warunek:
    1'.  z każdego wiersza może być wybrany co najwyżej 1 element.
W takim przypadku musimy już brać pod uwagę wybory dokonane w poprzednich krokach (by móc spełnić warunek 1').

Poprawiony: 19 lutego 2008 12:28
Dodaj komentarz