Cím: Mohó algoritmusok
Szerző(k):  Schmieder László 
Füzet: 2016/szeptember, 353 - 356. oldal  PDF  |  MathML 
Hivatkozás(ok):2016/október: Mohó algoritmusok 2.

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Mielőtt a címben jelzett algoritmusok közös jellemzőit megvizsgálnánk, oldjunk meg néhány egyszerű feladatot.

 
1. probléma (címletezés): A jelenleg használatos forint címletek segítségével fizessünk ki P pénzösszeget a lehető legkevesebb számú pénzérme/papírpénz fölhasználásával.
Fizessünk ki pl. 66 970 Ft-ot. A legkevesebb számú pénzt a 3⋅20000+5000+1000+500+2⋅200+50+20 címletezéssel tudjuk elvégezni. A megoldás általánosan, P pénzösszeg esetén is rendkívül egyszerű, feltéve, hogy mindegyik címletből elegendő számú áll rendelkezésre: megnézzük, hogy melyik a legnagyobb címlet, amely még nem haladja meg a kifizetendő pénzösszeget, és azzal kifizetjük a lehető legnagyobb összeget. A megmaradt pénzösszeg további részénél ugyanígy járunk el, itt nyilván már a kisebb címletekkel. Mivel minden kifizetéskor a lehető legnagyobb pénzösszeget fizettük ki a lehető legkevesebb számú pénzzel, ezért megoldásunk összességében is a lehető legkevesebb számú címletet használja föl.
Kérdések és feladatok:
1.Írjuk le az előbb megfogalmazott algoritmust és készítsünk belőle programot!
2.Adjunk meg olyan címleteket és pénzösszeget, amelyek mellett a fenti algoritmus nem a legkevesebb címletet használja föl, tehát nem ad optimális megoldást!

 
2. probléma (Informatika OKTV 2014/15, Döntő forduló, 1. feladat): Hosszú utca lakói elhatározták, hogy közösen WiFi szolgáltatást szerveznek. Kedvező ajánlatot kaptak olyan hálózati eszközre, amelynek hatósugara H méter. Minden hálózati eszközt valamelyik házba kell telepíteni. Minden ház megadta a ház azon pontját, ahová az eszközt telepítené, és amelyet a hatótávolság megállapításánál számításba kell venni. Ezt a pontot referencia pontnak nevezik, és az utcában az első háztól mért, méterben kifejezett értékkel adják meg.
Készíts programot, amely meghatározza, hogy hány hálózati eszközt kell venni és azokat hova kell telepíteni, hogy minden ház a legközelebbi elérési pont hatótávolságán belül legyen!
A program bemenete a H hatótávolság, a házak N száma és a házak referencia pontjai, vagyis N darab pozitív egész növekvő sorrendben. A feladatból nem derül ki, hogy az utca mely pontjain szeretnének WiFi elérést. Az egyik lehetséges értelmezés, hogy az utca minden pontján, a másik, hogy legalább a házak referencia pontjain. A feladat szövegéből inkább ez utóbbi következik, tehát keressük erre a problémára a választ. A program kimenete azon házak sorszáma, ahová adót érdemes telepíteni.
A megoldása rövid töprengés után szintén elég egyértelmű. Induljunk el az utca elejétől. Mivel minden referencia pontnak valamely másik referencia pont H sugarú környezetén belül kell lennie, ezért az első WiFi adót úgy kell elhelyezni, hogy az első referencia pontot is elérje. Ugyanakkor szeretnénk a lehető legtöbb házat ezzel a WiFi adóval lefedni, ezért az első háztól a lehető legtávolabbi, még H-nál nem nagyobb távolságra lévő referencia pontba telepítjük. Továbbhaladva az utcában ez az eszköz feltehetőleg elér más házakat, tehát megkeressük az első olyat, amely már a hatótávolságán kívül esik, és az előző lépéshez hasonlóan járunk el. Így minden esetben egy olyan helyet választunk a WiFi adónak, amely eléri az első még nem lefedett házat, ugyanakkor a lehető legtöbb további házat éri el.
Kérdések és feladatok:
1.Írjuk le az előbb megfogalmazott algoritmust és készítsünk belőle programot!
2.Tekintsük úgy a feladatot, hogy a WiFi elérést a teljes utcafronton biztosítani kell, nem csak a referencia pontokban, és terjedjen az utca az első referenciaponttól az utolsóig. Hogyan kellene módosítani az előbbi algoritmust, hogy megoldja a feladatot, illetve megadja, ha a teljes lefedés nem lehetséges?

 

Nézzük meg, hogy milyen hasonlóságok fedezhetők fel a két feladat, illetve a két megoldás között. Látható, hogy mindkét esetben a megoldás az adatok rendezett sorozatán halad végig. Kiválasztja a lehetséges legkedvezőbb, a feltételeknek még megfelelő címletet/helyet. A választás után már csak egy kisebb sorozaton keresi a megoldást, és itt is az előző stratégiával jár el. Próbáljuk megoldani ezek szellemében a következő feladatot:
 
3. probléma (Informatika OKTV 2004/05, Második forduló, 4. feladat): Egy rendezvényre N vendéget hívtak meg. Minden vendég előre jelezte, hogy mettől meddig lesz jelen. A szervezők fényképeken akarják megörökíteni a rendezvényen résztvevőket. Azt tervezik, hogy kiválasztanak K időpontot és minden kiválasztott időpontban az akkor éppen jelenlevőkről csoportképet készítenek. Az a céljuk, hogy a lehető legkevesebb képet kelljen készíteni, de mindenki rajta legyen legalább egy képen.
Írj programot, amely kiszámítja, hogy legkevesebb hány fényképet kell készíteni, és megadja azokat az időpontokat is, amikor csoportképet kell készíteni! A program bemenete a vendégek N száma, valamint minden vendég érkezési és távozási időpontjai 1≤Ei<Ti≤1000 egészek (1≤i≤N). A vendégek az érkezési időpontjuktól a távozás előtti időpontig tudnak részt venni a fényképezésben. A program kimenete a szükséges fényképek K száma, valamint a fényképek készítésének időpontjai.
Gondoljuk meg, hogy milyen matematikai jellegű problémával ekvivalens a feladat. Adott az [1,1000] intervallum, illetve annak N darab balról zárt, jobbról nyílt [Ei,Ti) intervalluma. Meg kell keresnünk a lehető legkisebb K számú Fj egészet (1≤j≤K), amelyekre teljesül, hogy mindegyik intervallumban szerepel közülük legalább egy.
Vajon hasonlít-e a feladat az előzőekre? Ha belegondolunk, látjuk, hogy igen. Itt is adódik egy rendezési szempont, hiszen érdemes időben előrehaladva feldolgozni az adatokat. Van-e lehetőségünk arra, hogy mohó stratégiával megoldjuk a feladatot? Ehhez az szükséges, hogy megtaláljuk az időrendben első fénykép készítésének optimális idejét. Milyen időpontig készíthetjük ezt el, vagyis milyen feltételnek kell megfelelnie ennek az időpontnak? Könnyen kitalálható, hogy az első távozási időpont előtt kell készítenünk a képet (és nyilván az első távozó érkezési időpontjában, vagy az után). Vajon ezek közül az időpontok közül melyik az optimális? Mivel az első távozási időpont előtt még senki nem ment el, ezért minél később készül a kép, annál többen lehetnek rajta. Vagyis a távozási időpont előtti időpontot kell választanunk. Ezen a fényképen mindenki rajta lesz, aki eddig az időpontig megérkezett. A második fényképet majd az első képen nem szereplő személyekről kell készíteni. Vagyis az első lépéssel csökkentettük az intervallumok számát, és most ismét az előző módon, mohó módszerrel tudunk következő időpontot választani.
A megoldás algoritmusa tehát először rendezi az adatokat a távozási időpont szerint növekvő sorrendbe, majd kiválasztja az első időpontot. Ezután elhagyja azokat a személyeket, aki ekkor már jelent voltak, azaz megkeresi a következő olyan személyt, akinek a távozási időpontjáig képet kell készíteni. Ha van ilyen személy, akkor elkészíti a képet, és újra keres egy olyan személyt, aki még nincs az előző képen. Ha már nincs ilyen személy, akkor készen vagyunk. A mohó megoldás, amely K és F értékét meghatározza a következő:
 

Fényképezés-eljárás  (N, E, T)       E és T együttes rendezése növekvő T értékek szerint    K := 1   // ez lesz az első kép       F[1] := T[1]-1   // az első kép készítésének időpontja       J := 2   // a 2. távozótól folytatjuk       Ciklus amíg   J≤N   // amíg mindenkit le nem fényképezünk           Ciklus amíg   J≤N  és  E[J]≤F[K]            J := J+1   // átlépjük a már képen lévő személyeket           Ciklus vége           Ha   J≤N   akkor   // a J-edik még nincs egyik képen sem                   K := K+1                   F[K] := T[J]-1                   J := J+1           Elágazás vége       Ciklus vége   Fényképezés-eljárás vége   

 
Megoldásunk hatékonyságát is érdemes megvizsgálnunk. Amennyiben az adatok átlagos, véletlenszerű sorrendben vannak, akkor pl. a gyorsrendezés N⋅logN-nel arányos lépésben rendezi azokat. Az ezt követő mohó algoritmus N értékével arányos lépésszámú, hiszen gyakorlatilag minden adatot egyszer vizsgál meg. A rendezés és a mohó algoritmus tehát a többi, lehetséges megoldáshoz képest hatékony megoldást ad.
Nem foglalkoztunk azzal a kérdéssel, hogy a mohó stratégia valóban az (egyik) optimális megoldását adja a fenti problémáknak. Vajon nem lehet-e kevesebb WiFi adóval lefedni az utca referencia pontjait, vagy kevesebb képet készíteni? Az általunk leírt módon nem, de egy más gondolatmenettel és eljárással sem? A következő részben választ adunk erre a fontos kérdésre. Addig is érdemes körülnézni a korábbi évek versenyfeladatai között, és megvizsgálni, hogy melyek oldhatók meg mohó stratégiával.
A Nemes Tihamér és OKTV feladatok pontos szövege a http://nemes.inf.elte.hu oldalon érhető el. A feladatokat a http://mester.inf.elte.hu feladatbankban is megtaláljuk, és itt a megoldásunkat is értékeli a rendszer.
 
Kérdések és feladatok:
1.Oldjuk meg a címletezés feladatot abban az esetben, ha ma használatos forint címlet mindegyikéből csak adott számú áll rendelkezésre. Megoldható a probléma mohó algoritmussal?
2.Milyen feltételnek kell teljesülnie a címletekre, hogy a címletezés tetszőleges (az adott címletekkel kifizethető) pénzösszeg esetén mohó algoritmussal megoldható legyen?