Routeplanner

[XoReP]

Voor een project waar ik aan wil gaan werken is het nodig dat ik weet volgens
welke strategie een routeplanner wordt gemaakt (bv Easy travel pro)
Wordt de kaart bv gescand van links naar rechts en dan van onder naar boven, of wordt er met coordinaten gewerkt.
Ik zou graag weten wat de basis- aanpak is bij het maken van een routeplanner.
Wie kan me dat vertellen?!

Alvast bedankt

[gorgi_19]

Bedoel je
Routeplanner?
[rml][ dijkstra algoritme] Routeplanner? *[/rml]

[ Voor 33% gewijzigd door gorgi_19 op 24-07-2003 15:09 ]

[djluc]

Hij heeft het over het scannen van een kaart. Ik denk dat hij meer bedoeld hoe ze de gegevens organiseren? Dus welke bron van informatie ze gebruiken?

[OZ-Gump]

Beide links van gorgi_19 zijn relevant, aangezien het Dijkstra algoritme (altijd?) voor een routeplanner gebruikt wordt. Door gebruik te maken van grafen wordt berekend wat de kortste weg is. De kaart wordt dus voorgesteld als graaf en deze wordt bekeken met het Dijkstra algoritme. De gegevens zijn dus aan de hand van coordinaten opgeslagen en worden onderling verbonden om zo een graaf te kunnen vormen.

Een kaart wordt dus niet gescand, omdat deze puur een grafische voorstelling is van de graaf, om het voor de gebruiker begrijpbaar te houden.

Tenminste, dat is wat ik me er nog van herinner

[Soultaker]

OZ-Gump schreef op 24 July 2003 @ 17:00:
Beide links van gorgi_19 zijn relevant, aangezien het Dijkstra algoritme (altijd?) voor een routeplanner gebruikt wordt.

NOFI, maar als je de thread gelezen had, dan had je kunnen vertellen dat de conclusie was dat hoewel Dijkstra de theoretisch optimale oplossing oplevert, het niet praktisch is om dit algoritme op een (zeer) uitgebreide graaf toe te passen. Een heuristisch zoekalgoritme levert in de praktijk veel betere prestaties en, afhankelijk van de parameters, bijna altijd de optimale oplossing.

[OZ-Gump]

Ik heb inderdaad niet allebei de links helemaal gelezen. Maar dan nog zijn deze draadjes wel nuttig voor de TS lijkt me. De discussie daar gaan immers over deze vraag, voor zover ik begrijp... Een grafische voorstelling van een kaart wordt immers nooit 'gescand' op mogelijke wegen, tenzij de TS iets heel anders bedoelde, dan houd ik gewoon mijn mond dicht verder

[ Voor 16% gewijzigd door OZ-Gump op 24-07-2003 17:25 ]

[djluc]

tenzij de TS iets heel anders bedoelde, dan houd ik gewoon mijn mond dicht verder

Dat vroeg ik mij dus ook af aangezien hij een kaart wil scannen. Hij wil toch niet de kaart van Nederland gaan scannen en dan automatisch de wegen laten herkennen... Even voor als je dat van plan bent, pak dan een vector tekenproggie en ga overtrekken want dat werkt niet. Net zoals dat overtrekken trouwens maar dat ter zijde

[ Voor 8% gewijzigd door djluc op 24-07-2003 18:10 ]

[Verwijderd]

Sorrie, maark had ff nie door dat ik op mijn zoons account zat. Hij stond namelijk nog ingelogd op deze computer. Ik sta nu weer onder mijn eigen account.

Sorrie voor de verwarring (het was dus geen opzettelijke acount sharing)

[Verwijderd]

JE kan het beste gebruik maken van het A of A* algoritme.

Ik heb het in een boek staan, ik zal ff zoeken of ik het ook op internet kan vinden.

Ik mijn boek Dudek - Computational Principals of Mobile Robotics staat het ongeveer zo:

code:

Proc Search(s, goal)
OPEN = {s}
CLOSED = {}
while (OPEN != 0) and (!found) do
    select a node n from open  <- gebruik hier de heuristiek
    OPEN = OPEN - {n}
    CLOSED = CLOSED + {n}
    if n == goal 
        found = true;
    else
        M = All nodes accessible from n that are not in CLOSED
        OPEN = OPEN + {M}
end while

In CLOSED zit het korste pad

Het lijkt iig een beetje op het dijkstra algoritme.
De afstand wordt vermeerderd met een heuristiek, meestal de afstand hemelsbreed tot het eindpunt

[ Voor 46% gewijzigd door Verwijderd op 24-07-2003 18:47 ]