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
"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').
Przykład:
Znaleźć w macierzy A taki podzbiór elementów, że
- w każdej kolumnie znajduje się co najmniej jeden wybrany element
- suma elementów wybranych jest maksymalna
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