Tanulási útmutató
Összefoglalás
A tananyag vége felé közeledve kitekintünk a továbblépési lehetőségekre. Olyan feladatokat nézünk át, amelyek alapvetően más tantárgyak témakörébe tartoznak, de a Programozási alapismeretek tantárgy eszközkészletével tökéletesen megoldhatóak.
Ebben a leckében a mohó stratégia egy klasszikus példáját nézzük meg.
Követelmény
Önállóan megoldható feladatok
Mohó algoritmusok
Benzinkút probléma
A Budapest-Párizs útvonalon N benzinkút van, az i-edik Bi távolságra Budapesttől (az első Budapesten, az utolsó Párizsban). Egy tankolás az autónak K kilométerre elég.
Készítsünk programot, amely megadja a lehető legkevesebb benzinkutat, ahol tankolni kell, úgy, hogy eljuthassunk Budapestről Párizsba!
Bemenet
N,K:Egész
B:Tömb[1..N:Egész]
Kimenet
Db:Egész
T:Tömb[1..N-1:Egész]
Előfeltétel
∀i(1≤i<N): B[i+1]-B[i]≤K
Utófeltétel
Db=??? és T⊆(1,…,N-1) és T[1]=1 és
∀i(1≤i<Db): B[T[i+1]]-B[T[i]]≤K és B[N]-B[T[Db]]≤K
A megfogalmazásból látható, hogy a tankolási helyek halmaza az összes benzinkút halmazának egy részhalmaza lesz.
Állítsuk elő az összes részhalmazt, majd válogassuk ki közülük a jókat (amivel el lehet jutni Párizsba), s végül adjuk meg ezek közül a legkisebb elemszámút!
Probléma: 2N részhalmaz van!
Optimalizálási probléma megoldására szolgáló algoritmus gyakran olyan lépések sorozatából áll, ahol minden lépésben adott halmazból választhatunk. Sok optimalizálási probléma esetén a dinamikus programozási megoldás túl sok esetet vizsgál annak érdekében, hogy az optimális választást meghatározza. Bizonyos esetekben ennél egyszerűbb, hatékonyabb algoritmus is létezik. A mohó stratégia mindig az adott lépésben optimálisnak látszó választást teszi. Vagyis, a lokális optimumot választja abban a reményben, hogy ez globális optimumhoz fog majd vezetni.
A megoldás: Budapesten mindenképpen kell tankolni! Menjünk, ameddig csak lehet, s a lehető legutolsó benzinkútnál tankoljunk! … Belátható, hogy ezzel egy optimális megoldást kapunk. A megoldás tehát egy kiválogatás tétel! Az a specialitása, hogy a kiválogatás feltétele nem csupán az adott elem valamely tulajdonságától függ, hanem az adott elemtől és a korábban már kiválogatott elemektől.
Benzinkút(N,B,Db,T):
Db:=1; T[1]:=1
Ciklus i=2-től N-1-ig
Ha B[i+1]-B[T[Db]]>K akkor Db:=Db+1; T[Db]:=i
Ciklus vége
Eljárás vége.
Tekintse meg az alábbi animációt, amelyben összefoglaljuk a lecke lényegét!
