[dijkstra algoritme] Routeplanner? *

[Verwijderd]

Stel je wilt een route planner maken, hoe doe je dit.....

Make je een database met de gegevens van elke straat, en geef je dan aan in welke straten die straat splits???
Bouw je dus op die manier een hele database op?
En laat je dan je programma alle wegen na-rekenen en dan de kortste berekenen?

Kortom, hoe pak je zoiets aan...

Niet dat ik het wil doen, maar wil wel eens weten hoe dat ongeveer in elkaar zit....

[chris]

wat mij het beste lijkt, is elke straat opsplitsen in rechte stukken/bochten. bijvoorbeeld een tabel met straatnamen, en een tabel met rechte stukken, en eentje met bochten. de rechte stukken en bochten worden begrensd door coördinaten, en in een bocht staat eventueel nog een hoek ofzo?

[MSalters]

http://carbon.cudenver.ed...kstra/DijkstraApplet.html

[Verwijderd]

MSalters schreef op 01 februari 2003 @ 17:13:
http://carbon.cudenver.ed...kstra/DijkstraApplet.html

Dit is inderdaad wat ik ongeveer bedoel, elke straat is een lijn, elk kruispunt een punt, elke lijn heeft een lengte en eigenschappen, en gaat naar een aantal punten, aan die punten zitten weer andere lijnen en zo kan je de snelste route bepalen....

Alleen het volgende probleem, als je het zo doet zal de pc alle mogelijke routes naar één punt gaan berekenen en dat kost volgens mij ontzettend veel tijd, dus hoe doe je zoiets snel....

[Soultaker]

Ik denk dat je een gerichte gewogen graaf opstelt en daar een standaardalgoritme op los laat om de kortste weg te vinden. Het applet dat hierboven stond demonstreert de werking van het algoritme van Dijkstra, dat de korste weg in een ongerichte gewogen graaf berekend.

Verwijderd schreef op 01 februari 2003 @ 17:17:
Alleen het volgende probleem, als je het zo doet zal de pc alle mogelijke routes naar één punt gaan berekenen en dat kost volgens mij ontzettend veel tijd, dus hoe doe je zoiets snel....

De complexiteit van Dijkstra's algoritme is O((V + E) log V), voor V punten en E verbindingen. Als je dus een miljoen kruispunten hebt, en tien miljoen straten, ben je met enkele tientallen miljoenen iteraties klaar. Een beetje moderne PC rekent dit in een paar seconde door.

[ Voor 52% gewijzigd door Soultaker op 01-02-2003 17:21 ]

[drm]

offtopic:
ff topictitle aangepast

[mbravenboer]

Je kan met allerlei heuristieken je zoekruimte beperken. Dat beperken van de zoekruimte is een belangrijk techniek bij alle zoek algoritmen. Ook het zo snel mogelijk vinden van een redelijke oplossing is een algemene techniek.

Stel dat je bijvoorbeeld al een weg hebt gevonden, dan kan je met een nieuwe mogelijke weg stoppen zodra die langer is. Je kan ook de voorkeur geven aan een weg die richting het doel gaat om zo zo snel mogelijk een korte weg te vinden.

Ze noemen dit ook wel kortste-pad algoritmen (zoek maar eens op single-source shortest path). Dijkstra heeft zo'n algoritme bedacht (wel meer overigens ), maar er zijn uiteraard vele oplossingen.

[D2k]

Er zijn idd veel algoritmen, maar het dijkstra algoritme is vrij eenvoudig volgens mij

[Verwijderd]

Heb met Dijkstra een aantal maanden geleden ook wat geknoeid, hier is 1 van mij test-files ervan:

code:

#include <iostream>
using namespace std;

int G[5][5];
int D[5];
int P[5];
bool S[5];

void Dijkstra(int sourceKnoop);
int zoekMinKnoop();
void printTussenResultaten();

void main (void)
{
    int i, j;
    
    /* init */
    for (i = 0; i < 5; i++)
    {
        for (j = 0; j < 5; j++)
        {
            if (i != j)
                G[i][j] = 9999;
            else
                G[i][j] = 0;
        }

        P[i] = 0;
        
        S[i] = false;
    }

    G[0][3] = 30;
    G[0][4] = 100;
    G[0][1] = 10;
    G[1][2] = 50;
    G[2][4] = 10;
    G[3][2] = 20;
    G[3][4] = 60;

    /* dijkstra */  
    Dijkstra(0);

    /* print results */
//  for (i = 0; i < 5; i++)
//      printf("[Knoop %d]\tKost: %d \tVorige knoop: %d\n", i, D[i], P[i]);
}

void Dijkstra(int sourceKnoop)
{
    int i, j;
    int minKnoop;

    /* init */
    S[sourceKnoop] = true;
    
    for (i = 0; i < 5; i ++)
        D[i] = G[sourceKnoop][i];

    for (i = 0; i < 5-2; i++) /* n - 2 passes */
    {
        printTussenResultaten();
        
        /* zoek knoop buiten S waarvoor D[v] minimaal */
        minKnoop = zoekMinKnoop();

        /* voeg toe aan S */
        S[minKnoop] = true;

        /* bepaal eventueel kortere/goedkopere paden via minKnoop */
        for (j = 0; j < 5; j++)
            if (!S[j] && D[minKnoop] + G[minKnoop][j] < D[j])
            {
                D[j] = D[minKnoop] + G[minKnoop][j];
                P[j] = minKnoop;
            }
    }

    printTussenResultaten();
}

int zoekMinKnoop()
{
    int i;
    int minKnoop = -1;

    for (i = 0; i < 5; i++)
    {
        if (minKnoop == -1 && !S[i]) /* het minimum op het "eerste" element vastleggen */
            minKnoop = i;

        if (!S[i] && D[i] < D[minKnoop])
            minKnoop = i;
    }

    return minKnoop;
}

void printTussenResultaten()
{
    int i;
    
    printf("D: ");

    for (i = 0; i < 5; i++)
        printf("%d\t",D[i]);

    printf("\nP: ");

    for (i = 0; i < 5; i++)
        printf("%d\t",P[i]);

    printf("\n\n\n");
}

Bovenstaande implementatie is gemaakt ahv. adjacency matrix representatie (complexiteit n²). Best kan je het herschrijven/herwerken naar een adjecency list representatie, omdat deze implementatie de reeds genoemde complexiteit (zie post van mbravenboer, sneller!) haalt.

In google zoek je op: shortest-path single-source, shortest-path all-pairs, Dijkstra algorithm, Floyd algorithm, graphs algorithms. Hiermee zal je wel genoeg vinden denk ik

[ Voor 28% gewijzigd door Verwijderd op 01-02-2003 17:46 ]

[Verwijderd]

Kan iemand het makkelijk uitleggen wat hij werkelijk doet, ok hij berekend elke keer de kortste afstand tussen eind en begin punt, maar hoe werkt het eenvoudig...

[mbravenboer]

Er staan denk ik genoeg goede Google hints in dit topic . Uitleggen hoe alles precies werkt is een beetje onzinnig als er zoveel goede bronnen het web zijn te vinden. Het is overigens wel goed om eerst in het algemeen wat kennis van grafen en graaf-algoritmen op te doen voordat je hier aan begint (alhoewel Dijkstra's ideeen in dit geval wel heel erg toegankelijk zijn).

[D2k]

hmmz beetje jammer dat je dat nou zo post

der is echt wel voldoende info over te vinden hoor
http://members.lycos.nl/epoppe/scriptie9.htm

[D2k]

op verzoek van DiEana:

---

Kort gezegd:

· Je begint met het voorstellen (hier ahv. adjacency matrix) van al de objecten waartussen al dan niet verbindingen bestaan. In jouw geval zijn dat dus steden. Elke verbinding heeft een kost (waarschijnlijk in jouw geval: kost = tijd). Indien er geen rechstreekste (!) verbinding bestaat, is die kost in principe oneindig. Ik stel dit voor door het getal 999. (Ik dacht dat je in C ook een define had in de aard van MAX_INT?)


· Het algoritme van Dijkstra berekent de korste paden naar alle andere steden, beginnende van 1 stad, je beginstad (zie sourceKnoop als parameter). Vandaar de term single-source shortest-path


· Het algoritme nu zelf: Eerst leggen we een lege verzameling S vast. Deze verzameling bevat de knopen (steden) die reeds beschouwd zijn. De verzaming D bevat de goedkoopste kost van beginknoop (beginstad) naar elke andere stad.

Vervolgens gaan we telkens de goedkoopste boog (korste afstand) van een knoop (stad) toevoegen en S en daarna (uiteraard) controleren of het geen beter plan is om via de net-toegevoegd knoop te gaan (ipv. een duurdere omweg te nemen dus).


Teken eens gewoon 5 steden op een papier, maak verbindingen tussen de steden (of geen verbindingen, geef de verbinding dan kost 999) en geef elke verbinding een kost. Maak dan een tabelletje S en D van 5 (= het aantal steden) lang en probeer vervolgens het algoritme te volgen. Het is echt simpel


Meer tijd heb ik niet, sorry, succes ermee.

[drm]

iom D2k weer open

offtopic:
stiekem toch wel interessant

[Verwijderd]

Ik probeer dit in mijn hoofd naar PHP om te zetten, ik beheers helaas geen java enzo...

Maar ik vind het zo wonderlijk, ik kan PHP gerust wel dingen laten berekenen, maar dit gaat mijn petje te boven, ik begrijp precies wat er gebeurd en wat er moet gebeuren, maar om dit in PHP te vertalen......

Om het ff in blokschema te tekenen als ik het tenminste goed begrijp:

1-2=4
1-3=5
2-4=8
3-4=4

Je laat hem nu de weg 1-4 berekenen...

1-2-4
of
1-3-4

Wat ik dus zo wonderlijk vind, is dat je hem de uiteindelijke uitslag moet laten bepalen....

Neem het grote voorbeeld: Je wilt van Emmen naar Alkmaar, je kan dan twee kanten op, Afsluitdijk of onderlangs (kan ook nog via Enkhuizen zelfs).
maar ik begin met een klein pleuris straatje in Emmen, dan ga je helemaal uitrekenen hoe hij via de meest achterlijke kleine weggetjes in Alkmaar komt... Sorry dat gaat mijn pet te boven, dat moet een pc toch uren kosten......

[Verwijderd]

Indien je wilt dat bepaalde 'wegen' meer gebruikt zullen worden, zal je hem een lagere kost moeten geven, als je gebruik wilt maken van het algoritme van Dijkstra. Het is aan jou om een overkoepelende kost te maken per weg, die rekening houdt met alle factoren die er in realiteit optreden als die weg zich op je reisweg bevindt. Je kan ook verschillende soorten wegen (hiermee bedoel ik niet straten, ik bedoel verbindingen) beschouwen, waarvan een weg onderdeel is van een andere weg (en dus meerdere keren Dijkstra toepassen). Een soort hiërarchie dus.

Een poging: deel je kaart op in vierkante gebieden (rasters), en zoek alleen tussen steden/dorpen/... die zich in die rasters bevinden indien je een rechte lijn van start-stad naar eind-stad zou trekken (+ eventueel de gebieden ernaast)?

[ Voor 19% gewijzigd door Verwijderd op 01-02-2003 19:28 ]

[mbravenboer]

Keesjes: Sorry dat gaat mijn pet te boven, dat moet een pc toch uren kosten......

Het Dijkstra algoritme werkt best aardig op leuke voorbeeldjes, maar je gaat zo natuurlijk geen routeplanner implementeren op de volledige kaart van Nederland, laat staan op nog veel grotere schaal. Het simpele algoritme berekent in feite de korste weg vanuit welke elke plaats op de kaart naar de oorsprong!

Dat is natuurlijk helemaal niet wat je nodig hebt als je van A naar B wilt. Dijkstra gebruikt als enige heuristiek om een nieuwe route te gaan kiezen de knoop die het dichst bij de huidige knoop ligt (let op dat 'dichtbij' hier niet percee afstand hoeft te betekenen!). Meer is hier ook niet nodig omdat het doel van algoritme nu eemaal is om de kortste route naar elk punt te berekenen.

Als je van A naar B wilt kan je natuurlijk nog veel meer nuttige selectie methoden voor verzinnen om niet de meest onzinnige kortste paden te gaan berekenen. De meest voor de hand liggende oplossing is om met behulp van heurstieken (richting bijvoorbeeld) zo snel mogelijk een mogelijke route te krijgen. Als je eenmaal een mogelijke route hebt kan je stoppen met elke route die al langer is dan de oplossing die je al kent.

Zo kan je nog veel meer technieken gebruiken om de zoekruimte te verkleinen. Lees nog maar eens wat ik daar eerder over schreef.

Als je hier overigens echt mee aan de slag wilt moet je gewoon een goed boek kopen. Dit red je niet met wat prutsen in PHP.

[Verwijderd]

mbravenboer schreef op 01 februari 2003 @ 19:43:
[...]
Als je hier overigens echt mee aan de slag wilt moet je gewoon een goed boek kopen. Dit red je niet met wat prutsen in PHP.

K, laat dan maar, het leek me wel leuk om in PHP iets te prutsen, maar je hebt idd gelijk, het is nogal complex...

[Verwijderd]

[mbravenboer]

Op zich wel jammer dat je zelf niet bereid bent om dit uit te gaan zoeken met behulp van boeken en bronnen op het web en afhaakt als het probleem toch wel wat lastig lijkt, maar wel onze tijd vraagt en bereidheid misbruikt om het je uit te leggen ...

(ik denk dat dit ongeveer uitlegt wat hierboven bedoeld wordt met ... )

[Verwijderd]

mbravenboer schreef op 01 februari 2003 @ 20:25:
Op zich wel jammer dat je zelf niet bereid bent om dit uit te gaan zoeken met behulp van boeken en bronnen op het web en afhaakt als het probleem toch wel wat lastig lijkt, maar wel onze tijd vraagt en bereidheid misbruikt om het je uit te leggen ...

(ik denk dat dit ongeveer uitlegt wat hierboven bedoeld wordt met ... )

Ik wilde gewoon globaal weten hoe het werkte, en dat antwoord heb ik gekregen, daarvoor mijn dank. Ik hoef toch niet persee er meteen helemaal in te duiken, ik heb wel andere dingen te doen......
Het kwam ineens in me op, en ik wilde dus wel eens weten hoe het in elkaar zat en of ik dan een simpel iets ff in PHP kan schrijven.

[chris]

precies, het is niet verspilde moeite. Ik heb de thread ook zo half gevolgd en begon het toch wel interessant te vinden. Er zijn heel veel forum-lurkers die het vast wel heel interessant vinden. Alleen: het is natuurlijk wel een beetje jammer dat de ts afhaakt. Dit zijn juist de interessante problemen van het programmeren. En dit is toch op dit moment een van de betere topics op P&W....

[Verwijderd]

Idd mbravenboer.

Trouwens, wat ik mij afvraag: Als je zo'n programma (routeplanner) moet maken, dan zorg je toch gewoon () dat je alle steden, straten, verbindingen, .. hebt, je laat daar Floyd op los (all-pairs shortest-path), je slaat deze resultaten op in een goede bestandsstructuur, en je geeft dat mee met je programma? Dan is het alleen een kwestie van de files te doorlopen, ipv. de gebruikers (eventueel) lange algoritmes laten uit te voeren.

[RickN]

Verwijderd schreef op 02 February 2003 @ 10:09:
Idd mbravenboer.

Trouwens, wat ik mij afvraag: Als je zo'n programma (routeplanner) moet maken, dan zorg je toch gewoon () dat je alle steden, straten, verbindingen, .. hebt, je laat daar Floyd op los (all-pairs shortest-path), je slaat deze resultaten op in een goede bestandsstructuur, en je geeft dat mee met je programma? Dan is het alleen een kwestie van de files te doorlopen, ipv. de gebruikers (eventueel) lange algoritmes laten uit te voeren.

Heb jij een hardeschijf van enkele terabytes? Het aantal paren op N punten is 1/2 N². Natuurlijk laat je je algoritme wél on the fly die algoritmes uitvoeren. Dat stelt je ook in staat de gebruiker andere criteria dan alleen afstand op te geven en je kunt b.v. ook file informatie en wegwerkzaamheden in je berekening verwerken.

[mbravenboer]

Ik heb nooit aan een praktische routeplanner meegewerkt of het ontwerp ervan bekenen, dus ik kan alleen maar gissen naar de methode die ze gebruiken om de theorie te mappen naar de praktijk.

Ik denk niet dat het erg opschiet om alle routes in feite al van te voren te berekenen en simpelweg deze database te raadplegen. De hoeveelheid benodigde data zal niet gering zijn omdat ze natuurlijk ook de route op moeten slaan. Daarnaast zijn de meeste routeplanners een stuk flexibeler en hebben ze bijvoorbeeld mogelijkheid om blokkades op te werpen, onderscheid te maken tussen transport methode en ook weleens op vrijwel exacte huisnummers kunnen werken. Dit zou zoveel varianten opleveren dat het mij vrij onpraktisch lijkt. Met het gebruik van goede heuristieken moet het qua rekenkracht helemaal niet zo'n probleem zijn ...

edit:
Hum, RickN was me net voor

[ Voor 4% gewijzigd door mbravenboer op 02-02-2003 11:03 ]

[80000]

Soultaker schreef op 01 February 2003 @ 17:17:

De complexiteit van Dijkstra's algoritme is O((V + E) log V), voor V punten en E verbindingen. Als je dus een miljoen kruispunten hebt, en tien miljoen straten, ben je met enkele tientallen miljoenen iteraties klaar. Een beetje moderne PC rekent dit in een paar seconde door.

Het probleem is niet zo zeer de berekening, maar de hoeveelheid data die in memory gelezen moet worden wat tijd kost. Over het algemeen wil je de zoekruimte beperken (zoals mbravenboer aangeeft), door alleen maar delen van het netwerk in geheugen te laden die nodig zijn.

Verwijderd schreef op 01 February 2003 @ 19:26:
Een poging: deel je kaart op in vierkante gebieden (rasters), en zoek alleen tussen steden/dorpen/... die zich in die rasters bevinden indien je een rechte lijn van start-stad naar eind-stad zou trekken (+ eventueel de gebieden ernaast)?

Zeker geen slechte poging hoor . Als je hier een index overgooit ben je al goed begonnen. Zoek in Google op: Quad tree. Jouw rasters moeten alleen maar delen van het netwerk bevatten. Er zijn trouwens beter indexen hiervoor, maar om het principe te begrijpen is een Quad tree heel eenvoudig.

Verwijderd schreef op 02 February 2003 @ 10:09:
Trouwens, wat ik mij afvraag: Als je zo'n programma (routeplanner) moet maken, dan zorg je toch gewoon () dat je alle steden, straten, verbindingen, .. hebt, je laat daar Floyd op los (all-pairs shortest-path), je slaat deze resultaten op in een goede bestandsstructuur, en je geeft dat mee met je programma? Dan is het alleen een kwestie van de files te doorlopen, ipv. de gebruikers (eventueel) lange algoritmes laten uit te voeren.

Een nadeel lijkt mij de onderhoudbaarheid van het geheel. Als het wegennetwerk verandert (hee dit is de overheid), mag je alles opnieuw gaan berekenen.

[djluc]

Een nadeel lijkt mij de onderhoudbaarheid van het geheel. Als het wegennetwerk verandert (hee dit is de overheid), mag je alles opnieuw gaan berekenen.

Dat zal niet echt lekker gaan nee, dan kun je een paar dagen wachten als alles overnieuw moet. Een kleiner deel kan ook niet want dan kloppen de andere routes ook allemaal niet meer, of zou je wel een klein deel kunnen herberekenen. Of misschien alleen de routes waar deze weg in voorkomt, dan valt het wel mee.

[drm]

DiEana:

offtopic:
Hou dergelijke replies voor je, of onderbouw ze zelf, en houd dan ook de eer aan jezelf, ajb