Izpitno vprašanje RAČ2PRA 15500

Iz MaFiRaWiki

Vsebina

Vprašanje

|15500| Požrešna metoda - opiši pojem dopustna rešitev in optimalna rešitev.
Prikaži nekaj primerov.

Odgovor

Rešujemo optimizacijski problem s požrešno lastnostjo:
na vsakem koraku bi radi čimveč / čimmanj
zmeraj izberemo najboljše ta hip.

Opis problema

  • imamo n elementov ai
  • izberimo podmnožico {ai, i \isin J}, J {1, 2, ..., n}
  • dopustna podmnožica
    ali zadošča vsem omejitvam?
  • optimalna podmnožica
    dopustna podmnožica, ki optimira kriterijsko funkcijo

Ideja

  • rešitev gradimo postopoma
  • začnemo s prazno množico - ta je zagotovo dopustna
  • obstoječi dopustni množici dodamo element, ki prinese največ

(ki mini/maksi-mizira kriterij)
Seveda le, če je dobljena množica še vedno dopustna.

  • ko pridemo do konca (ni več kandidatov za dodajanje k dopustni množici), smo zgradili optimalno rešitev.

Dopustna rešitev

Je ena od rešitev, ki reši problem. Ni pa nujno najboljša.

Optimalna rešitev

Je tista izmed dopustnih rešitev, ki je najboljša. Sami moramo dokazati, da je rešitev res optimalna.
Včasih požrešna metoda ne pripelje do optimalne rešitve.

Problemi s požrešno lastnostjo:

  • globalno optimalno konfiguracijo lahko dobimo kot zaporedje lokalno optimalnih odločitev
  • torej, na vsakem koraku je "lokalno" najboljša rešitev tudi prava (oz. del prave rešitve).

Primeri

Problem enostavnega nahrbtnika

Glej Izpitno vprašanje RAČ2PRA 15600

Razporeditev N enot na trak

Glej Izpitno vprašanje RAČ2PRA 15900

Razporejanje poslov

Glej Izpitno vprašanje RAČ2PRA 14900

Osebna orodja