Új hozzászólás Aktív témák

• #11983 cucka addikt bobace #11982

  Új Válasz 2012-11-21 09:33:57 #11983

  Új hozzászólás

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  cucka

  addikt

  válasz bobace #11982 üzenetére

  A mohó algoritmusok úgy működnek, hogy minden egyes iterációban a lokális optimumot választják.

  Például ha az a célod, hogy a legrégebbi számlákat kell kiegyenlíteni, akkor a mohó algoritmus minden egyes lépésben kiválasztja a legrégebbi számlát, amit ki tud egyenlíteni (ez a lokális optimum) a meglévő keretből és kiegyenlíti. Elég könnyű belátni, hogy így a végén is optimumhoz jutunk.

  Ha viszont az a célod, hogy a lehető legnagyobb összeget kel kiegyenlíteni, akkor a mohó algoritmus minden egyes lépésben kiválasztja a legnagyobb összegű számlát, amit ki tud egyenlíteni (ez a lokális optimum) a meglévő keretből. Szintén elég könnyű belátni, hogy ez összességében nem fog optimális eredményhez vezetni.
  Pl. ha a számláid összege 80, 40, 50 és a rendelkezésre álló pénz 100, akkor a mohó algoritmus kiegyenlíti a 80-as számlát és megáll, miközben az optimális a 40 és 50 kiegyenlítése lenne.

Új hozzászólás Aktív témák