Požrešna metoda

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje

Požrešna metoda je strategija, pri kateri je bistvo, da lažji del prepustimo računalniku, težji del pa izvedemo sami, ko izvedemo neko dejanje, ki nas privede na preprost način do cilja. Princip delovanja je, da iščemo optimum funkcije (minimum ali maksimum), tako da sproti gradimo rešitev. Rešitev gradimo tako, da ji dodajamo najboljše dopustne dele rešitev.

Pojmi[uredi | uredi kodo]

Pri požrešni metodi so pomembni naslednji pojmi:

  • dopustna množica oz. dopustna rešitev je kakršna koli množica, ki izpolnjuje določene omejitve (njeni elementi).
  • kriterijska funkcija je funkcija, ki optimizira njeko (pod)množico - rešitev.
  • optimalna rešitev/množica, ki optimizira kriterijsko funkcijo, se imenuje optimalna rešitev/množica

Značilno za metodo je, da množico rešitev gradimo postopoma. To pa pomeni, da na tekočem koraku poiščemo element, ki največ prinese h kriterijski funkciji.

Algoritmi[uredi | uredi kodo]

Splošna procedura[uredi | uredi kodo]

Pocedura v množici a z n elementi, poišče optimalno podmnožico in jo zabeleži v podmnožico rešitev.

procedure Požresnost (n, a, rešitev)
begin
  rešitev := 0
  for i:= 1 to n do
  begin
    x := izberi (n, a, rešitev)    // izberemo naslednji element
    if dopustna (x, rešitev) then
      rešitev := rešitev υ X   // če je x dopusten, ga vključi v rešitev
  end
end