Hirdetés

Keresés

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

  • 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