Az előző részben megoldottunk néhány problémát mohó algoritmusok segítségével. A kitűzött feladatok mindegyikénél sikerült egy optimális megoldást találni úgy, hogy a megoldást végző algoritmus nem vizsgált meg minden lehetséges esetet, hanem minden lépésnél egy, az addigi ismeretek alapján optimális lehetőséget választott. Ezzel ugyanakkor egyszerűsítette a problémát, vagyis a továbbiakban egy kisebb halmazból kellett választani, és az eredetivel ekvivalens feladatot megoldani.
Az előző részben a megoldások során nem igazoltuk, hogy a mohó stratégiával talált eredmény valóban egy optimális megoldás. Bár ez sok esetben szinte magától értetődik, mégis érdemes ezeket a könnyebb példákat is végiggondolni.
Nézzük először a címletezés problémáját. A ma használatos forint érmék vagy papírpénzek esetén sikerült mohó módszerrel megoldást adnunk. Az eljárás bármely pénzösszeg esetén a lehető legnagyobb olyan címletből választ, amely még nem nagyobb az összegnél. Ez a mohó módszer azonban nem működik pl. az 1, 5, 7, 10 címleteknél, hiszen a 14-et öt érmével fizeti ki, pedig kettővel is lehet. Tehát nem minden címletezési problémára ad optimális megoldást a mohó módszer.
Vizsgáljunk olyan címleteket, ahol a pénzértékek közelebb állnak a megszokotthoz, pl. nem fordul elő, hogy két kisebb értékű címlet összege meghalad egy nagyobb értékű címletet. Oldjuk meg a címletezés feladatát például azzal a feltétellel, hogy bármely címlet legalább kétszerese a csökkenő sorrendben utána következőnek.
Ekkor elég egyértelműnek tűnik, hogy a mohó módszerrel kapott eredmény optimális. De hogyan tudnánk ezt bizonyítani? Mivel annyira nyilvánvaló a dolog, próbáljuk meg az indirekt bizonyítást. Tegyük föl, hogy van egy optimális megoldás, amely nem azonos a mohó módszerrel kapott megoldással, sőt, kevesebb számú pénzzel fizet ki egy bizonyos pénzösszeget. Vizsgáljuk a két megoldást a címletek szerint csökkenő sorrendben, és keressük az első címletet, ahol darabszámban eltérés van. Nézzük azt a pénzösszeget, ami a közösen, azonos számban választott nagyobb pénzek fölhasználása után megmaradt. Ha a mohó módszer esetén van kevesebb számú ebből a címletből, az azt jelenti, hogy a fennmaradó, kifizetésre váró pénzösszeg kisebb, mint a címlet. De ekkor a másik, optimális megoldás nagyobb összeget fizetett ki, mint szükséges, hiszen ebből a címletből még legalább egyet választott. Ez azt jelenti, hogy a másik megoldás nem lehet optimális megoldás, sőt, nem is helyes címletezés. Ha a mohó módszer esetén van több az első különböző számú címletből, akkor az előbb definiált fennmaradó összeg nem kisebb, mint a címlet. Ha a mohó megoldás egy ilyen címlettel kifizet egy összeget, akkor a nem mohó megoldásban a feltétel szerint ennek az összegnek a kifizetéséhez legalább két pénzdarab szükséges. Ha tehát ezekkel a pénzösszegekkel mindkét megoldás szerint fizetünk, akkor a mohó megoldás egy darab, míg a másik legalább kettő darab pénzzel fizeti ki ugyanakkora összeget. Folytassuk a címletek összehasonlítását a kisebb címletek felé haladva, és tegyük ugyanazt, mint az előbb. Nyilván ugyanazok az esetek lehetségesek, mint az előbb, vagyis nem fordulhat elő, hogy a második, optimálisnak mondott megoldás kevesebb pénzdarabot használ föl azonos összegek kifizetésére. Ez azt jelenti, hogy a másik optimális megoldás vagy mégsem optimális, vagy megegyezik a mohó algoritmussal kapott megoldással.
A címletezés problémakört még folytatjuk majd, mivel további izgalmas kérdéseket vet föl, hogy hogyan oldható meg más feltételekkel, vagy akár bármilyen feltétel nélkül a probléma.
Nézzük meg a mohó megoldást az előző részben tárgyalt fényképezés feladatnál. Megállapítottuk, hogy a feladat ekvivalens azzal, hogy $N$ darab balról zárt, jobbról nyílt $\left[E_i\mathrm{,}{T}_i\right)$ intervallumhoz $\left(1\le i\le N\right)$, melyek végpontjai egészek, meg kell keresnünk a lehető legkisebb $K$ számú $F_j$ egész pontot $\left(1\le j\le K\right)$, amelyekre teljesül, hogy mindegyik intervallumban szerepel közülük legalább egy. A mohó módszert itt úgy alkalmaztuk, hogy a $T_i$ értékek szerint nem csökkenő sorrendbe állítottuk az intervallumokat, majd kiválasztottuk az elsőt, és az intervallum végénél eggyel kisebb egész lett $F_1$. Ezután elhagytuk azokat az intervallumokat, amelyek tartalmazták $F_1$-et, és a megmaradtak közül választottuk a következő legkisebb $T_i$ értékűt, illetve $F_2$ az annál eggyel kisebb egész lett.
Nézzük, hogy most hogyan igazolható, hogy a mohó megoldás optimális. A módszer abból indult ki, hogy a sorrendben első intervallum végpontja előtt kell lennie egy $F_1$ pontnak, és ez akkor van benne a lehető legtöbb további intervallumban, ha $T_1-1$-hez tesszük. Megint nyilvánvalónak látszik, hogy az $F_1$ érték a ,,lehető legjobb'' a többi lehetséges közül. Próbáljunk meg ismét egy indirekt bizonyítást. Tegyük föl, hogy van egy optimális, a mohó algoritmussal kapott $K$ számú pontnál kevesebb pontot tartalmazó megoldás. Rendezzük most is az intervallumokat a végpontjaik szerint növekvően, és tegyük ezt a nem mohó megoldásban szereplő $K\text{'}$ számú $F{\text{'}}_j$ egésszel (a mohó megoldás $F_j$ értékei eleve növekvő sorrendben vannak). Nézzük az azonos indexű egészek egymáshoz viszonyított helyzetét. $F_1$-nél nem lehet nagyobb $F{\text{'}}_1$, mivel ekkor a nem mohó megoldásban a rendezett sorrendben első intervallum nem tartalmazná egyik $F{\text{'}}_j$ egészet sem, hiszen a legkisebbet sem tartalmazza. Így biztosan teljesül, hogy $F{\text{'}}_1\le F_1$. Így a mohó megoldás első pontja biztosan legalább annyi intervallumban szerepel, mint a nem mohó megoldás első pontja. Ebből következik, hogy a két pont által tartalmazott intervallumok elhagyása után a mohó megoldás legalább azokat az intervallumokat (vagy többet) lefed, amelyeket a másik megoldás. Tehát a nem mohó megoldásban is biztosan szerepel a mohó megoldás második pontját meghatározó intervallum. Ekkor az előbbi gondolatmenettel tudjuk igazolni, hogy $F{\text{'}}_2\le F_2$, és indukcióval a többi értékre is. Ezzel azonban ellentmondást kapunk, hiszen így a mohó megoldás és a másik, optimális megoldás azonos számú pontot tartalmaz. Tehát helytelen az a föltevés, hogy a mohó megoldás nem optimális.
A címletezéshez képest talán jobban látszik, hogy az intervallumok elhelyezkedésétől függően több optimális megoldás is van, és a mohó algoritmus ezek közül ad egyet.
Az elmúlt évek OKTV és Nemes Tihamér programozási versenyfeladatai között sok olyan problémát találunk, amelyek mohó módszer segítségével oldhatók meg. A http://mester.inf.elte.hu weboldalon a Mohó algoritmusok témakörben összegyűjtve is megtaláljuk őket. Gyakorlásként oldjuk meg a következő feladatot (a feladat pontos szövege a http://nemes.inf.elte.hu oldalon érhető el.)