Požrešna metoda

Iz Wikipedije, proste enciklopedije

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.

[uredi] Pojmi

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.

[uredi] Algoritmi

• preprosti problem nahrbtnika
• minimalna vpeta drevesa
  • Primov algoritem
  • Kruskalov algoritem
  • Dijkstrov algoritem ali drevo najkrajših poti

[uredi] Splošna procedura

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