Kezdőoldal » Számítástechnika » Programozás » Hogyan működik egy útvonalkereső?

Hogyan működik egy útvonalkereső?

Figyelt kérdés

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?


2013. aug. 26. 21:10
1 2
 1/11 anonim ***** válasza:

Igen.

Esetleg más ötleted is van rá?

2013. aug. 26. 21:51
Hasznos számodra ez a válasz?
 2/11 A kérdező kommentje:
Nem igazán, csak gondoltam így nagyon lassú és erőforrás-igényes, mivel ez egy hatalmas gráf.
2013. aug. 26. 21:56
 3/11 anonim ***** válasza:
Többféle gráf algoritmus is létezik, illetve ők inkább adatbázis lekérésekkel operálnak talán. (Tárolt eljárások stb.)
2013. aug. 26. 22:28
Hasznos számodra ez a válasz?
 4/11 A kérdező kommentje:

És az adatbázisban mi van eltárolva?

Minden egyes pont minden ponttól való távolsága?

2013. aug. 26. 22:31
 5/11 iostream ***** válasza:
Nem olyan hatalmas feladat ez. Nézz meg akármilyen navigációt, rengeteg út van rajta. Ott persze vért izzadnak, hogy jó eredményt adjon értelmes időn belül, de alapvetően ilyen két oldalról indított keresésekről van szó.
2013. aug. 26. 23:06
Hasznos számodra ez a válasz?
 6/11 A kérdező kommentje:

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.

2013. aug. 26. 23:15
 7/11 Srapnel ***** válasza:
100%
Azért a Dijkstra algoritmus kb. az első 10 oldalban lenne benne a témáról szóló 300 oldalas könyvben. Számtalan gyorsítási módszer van, mint pl. a google maps által is használt ez: [link]
2013. aug. 27. 08:25
Hasznos számodra ez a válasz?
 8/11 iostream ***** válasza:

"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.

2013. aug. 27. 11:18
Hasznos számodra ez a válasz?
 9/11 anonim ***** válasza:

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.

2013. aug. 27. 13:19
Hasznos számodra ez a válasz?
 10/11 A kérdező kommentje:

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

2013. aug. 27. 21:36
1 2

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

A weboldalon megjelenő anyagok nem minősülnek szerkesztői tartalomnak, előzetes ellenőrzésen nem esnek át, az üzemeltető véleményét nem tükrözik.
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!