Požrešna metoda

Iz MaFiRaWiki

Požrešna metoda je ena od standardnih metod za načrtovanje algoritmov. Z njo rešujemo optimizacijske probleme. Pri požrešni metodi problem rešujemo kot končno zaporedje podproblemov. Pri vsakem koraku izberemo med delnimi rešitvami tisto, ki daje trenutno največji profit.

Primer: "Problem predavalnice"

Vhodni podatki:

  • predavanja pi
  • število predavanj n
  • za vsako predavanje začetek ai ter konec bi

Na voljo imamo le eno predavalnico P. Izbrati želimo največje število predavanj, ki jih lahko izvedemo (brez prekrivanja).

Postopek:

  • izberemo tisto predavanje, ki se najprej konča in ga je še mogoče izvesti
  • predavanja uredimo po bi
  • vzamemo prvega
  • vzamemo prvega takega, ki ima a večji od našega prejšnjega b
  • ponavljamo zadnji korak

Zgledi

Osebna orodja