Vegyünk először egy egyszerűbb problémát
A nehézséget az okozza, hogy a séta összhosszára is van egy korlátunk, és az összköltségre is optimalizálni kell. Átmenetileg elfelejtjük a jegyárakat, és csak azt fogjuk nézni, hogy legkevesebb gyaloglással hogyan érhetünk célba.
Gráfreprezentáció
Mivel a buszjáratokon ingyen utazhatunk, azt kell vizsgálni, hogy két buszjárat között az átszállásnál. illetve egy pont és egy buszjárat között mennyit kell gyalogolni. A következő gráfot építjük fel:
Csúcsok: A, B és a buszjáratok, összesen R+2 pont.
Élek: Bármely két csúcs között van.
Élek súlya: A csúcsoknak megfelelő ponthalmazok "Manhattan-távolsága". Két ponthalmaz távolsága a legközelebb lévő pontjaik távolsága, véges sok pont esetében ez mindig létezik.
Pontok Manhattan-távolsága
Két pont távolsága, ha csak rácsszakaszokon lépkedhetünk.
$d_m(x,y)=|x_1-x_2|+|y_1-y_2|$
Pont és szakasz Manhattan-távolsága
A pontból vagy a szakasz valamelyik végpontjába kell menni, vagy a szakaszra bocsájtott merőleges talppontjába. A három lehetőség közül a legrövidebb a távolság.
Szakaszok Manhattan-távolsága
A szakaszok vagy párhuzamosak vagy merőlegesek. Minden elrendezésnél visszavezethető a távolság valamelyik szakasz valamelyik végpontjának a másik szakasztól vett távolságára.
Buszjárat útvonalak Manhattan-távolsága
A lehetséges szakaszpárok távolságai közül a legrövidebb.
Útvonaltervezés legkevesebb gyaloglással
Az előzőekben definiált gráfon megkeressük a legrövidebb utat A-ból B-be, mondjuk Dijkstra algoritmusával.
Kódok
Most már jöhet az eredeti probléma
Az eddigiekben nem vettük figyelembe, hogy a buszozásért fizetni is kell, és a legolcsóbb megoldást szeretnénk megkeresni. Ha pénzben akarunk optimalizálni, akkor gyaloglásban nem kell a legrövidebb út, csak "elég" rövid.
Élsúlyozás költségekkel és szuper-gráf távolságokkal
Dinamikus programozás
Kódok
Kriván Bálint (java):
Trip.java (és az előző osztályok, a fenti megoldásból)
