Požrešna Metoda

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.

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.

• preprosti problem nahrbtnika
• minimalna vpeta drevesa
  • Primov algoritem
  • Kruskalov algoritem
  • Dijkstrov algoritem ali drevo najkrajših poti
• požrešni algoritem za egipčanske ulomke

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