algorytm.org Algorithmics turorial Metoda zachłanna  
Home AlgorithmsData structuresAlgorithmics turorialPractiseDesign patternsIT Law SitemapPortal historyContributors ForumToolsWrite an articleSearch 

Metoda zachłanna
User Rating: / 7
PoorBest 
Written by Michał Knasiecki   
Monday, 01 August 2005 22:13
There are no translations available.

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').

Last Updated on Tuesday, 19 February 2008 12:28
 

Add comment







Danation
Donate us


RSS Channels
Articles
Implementations
Comments
Forum


Bookmarks








Poll
Czy znalazłeś na stronach www.algorytm.org to czego szukałeś?
 

www.algorytm.org (c) 2000-2010