Hogyan működik egy útvonalkereső?
Gondolok itt például a BKV útvonalkeresőre.
Súlyozott gráfokkal ábrázolja a járatokat, és akkor küld rá egy Dijkstra-algoritmust?
Igen.
Esetleg más ötleted is van rá?
És az adatbázisban mi van eltárolva?
Minden egyes pont minden ponttól való távolsága?
Igen, azt értem, hogy rengeteg út van. Sőt mondjuk egy BKV közlekedésnél súlyozva is vannak gondolom, hisz a metró például gyorsabb, mint a busz.
Tömören ezt úgy kell elképzelni, hogy mondjuk mindkét pontból kiindul egy Dijkstra, és ahol összeérnek az a legrövidebb út? Mert ez így nem biztos, hogy a legrövidebb lesz szerintem.
Egyszer úgy megnézném egy ilyennek az algoritmusát.
"Mert ez így nem biztos, hogy a legrövidebb lesz szerintem."
Hát pedig ha nincs negatív él akkor a Dijkstra bizonyítottan a(z egyik) legrövidebbet adja (az egyik, ha több legrövidebb is van).
Számtalan módon lehet ezt gyorsítani, például ha két oldalról indítod az egy módszer. Sokféle heurisztika van, a budapesti tömegközlekedés egy kifejezetten kis méretű feladat, mert nagyon kötöttek az útvonalak, nagyon kevés az útvonal.
Tegyük fel, hogy saját kútföböl kell megoldanod ezt a problémát. Modellezd. Fogsz egy papírlapot, rajzolsz rá néhány pontot, egy párat összekötsz közülök, így kapsz egy gráfot. A vonalak mellé odaírod, hogy a két pont milyen távolságra van egymástól (hány méter vagy hány perc, stb.)
A megoldandó feladat, 2 tetszöleges pont között a legrövidebb utat megtalálni. A pontok közötti összeköttetést és távolságot tárolhatod egy táblában (pont1, pont2, távolság). Majd rekurzív lekérésekkel kiszámítod a legrövidebb útvonalat és az átívelendö pontok sorrendjét. A Dijkstra-algoritmus erre elsö lépésként nem rossz. Már csak ebböl kell SQL-t faragni.
Ha nem akarsz ennyit szenvedni (pedig néha jó, mert "edzed" magad vele...) vagy nincs idöd rá --> [link]
Nyilván nem akarod a kereket feltalálni, de minden problémára születhet egy új megoldás.
De adatbázisban eltárolva ez így nem túl erőforrásigényes?
n pont esetén: n*(n-1)/2 db rekord kellene.
1000 pontnál ez már közel 500.000
Kapcsolódó kérdések:
Minden jog fenntartva © 2025, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!