[PHP] Dijkstra's algoritme

[Kaastosti]

Huh Dijkstra? Wie is dat dan weer? Wie het precies was ga ik verder niet op in, maar hij heeft in ieder geval een algoritme geschreven voor het berekenen van het aantal kortste (of goedkoopste) routes door een object met nodes.

Stel je hebt een 6-dimensionaal object (probeer dat niet te tekenen). Deze heeft coordinaten van 0,0,0,0,0,0 t/m 6,6,6,6,6,6 . Nou wil ik weten hoeveel mogelijke kortste routes er zijn van 0,0,0,0,0,0 naar een willekeurige coordinaat, bijvoorbeeld 3,2,3,2,4,2 .

van allemaal 0 naar allemaal 6 is het totaal aantal kortste routes 720. Dit heb ik gevonden met een beetje hulp van deze site. Maar daarmee kom ik niet zo ver. Ik heb hier een aantal A4'tjes vol berekeningen, waar ik uiteindelijk niets aan heb. Ik heb geprobeerd Dijkstra's algoritme zelf te schrijven, maar ik kom niet zo ver met m'n recursieve functie. Dat zelf schrijven ga ik nog wel verder over nadenken, want het moet natuurlijk kunnen, maar op het moment heb ik daar wat weinig tijd voor helaas.

Heeft iemand toevallig dit algoritme in php liggen (ik heb geen trek in andere compilers installeren) of weet iemand een andere manier om dit te berekenen?

[.oisyn]

Heeft iemand toevallig dit algoritme in php liggen

nee, want dan is het een scriptrequest en dan gaat je topic op slot

[sjroorda]

Is redelijk recent langsgeweest, even zoeken op Dijkstra

[Kaastosti]

Hmmmz net kon ik nog niets vinden iig.. zal nog eens zoeken, search is af en toe niet helemaal lekker

[curry684]

http://search.gathering.t...ta%5BxFILTERS%5D=XF14---A

[Kaastosti]

Mjah het enige wat ik daar vind ik dat de goede man vorig jaar is overleden en een aantal voorbeelden van Dijkstra's algoritme. Ik begin er alleen aan te twijfelen of het algoritme ook het _aantal_ kortste (of goedkoopste) routes berekend, of alleen _de_ kortste (of goedkoopste) route.

Als ik de posts hier doorlees zou dat maar 1 route opleveren, terwijl ik op Google ook dingen heb gelezen over het tellen van het aantal mogelijke kortste routes. Misschien komt het dan toch weer neer op zelf schrijven, al weet ik dus niet precies hoe ik dat ga doen. Alle paden hebben in mijn object namelijk dezelfde waarde (1), aangezien het gewoon 1 stap verder is. Het tellen van het aantal stappen is daarin het probleem niet, gewoon per recursie er 1 bij optellen.

het wordt alleen een stukje lastiger op het moment dat je de mogelijkheden per coordinaat wilt gaan bekijken. Dan zou je zoiets moeten hebben als een verhoudingendiagram of in ieder geval iets waaraan het programma kan 'vragen' (als een functie oid) welke nodes deze als buren heeft. Ik wil serieus geen tekening of schets proberen te maken van een 6-dimensionaal object :x

[SWfreak]

Het standaard Dijkstra algoritme berekend alleen het kortste pad (of de lengte ervan). Als je het aantal kortste paden wilt berekenen is dat in jouw geval redelijk eenvoudig: je kijkt namelijk zodra je de doelknoop hebt bereikt gewoon naar het aantal buren dat al in de cloud zit. Ik weet niet wat je precies met die 6 dimensies wil, maar volgens mij is dat niet nodig.

[curry684]

Volgens mij kun je dit met een heel simpele A* (A-star) engine ook zo oplossen.

edit:

En A* kun je wel zo implementeren dat ie het aantal kortste paden teruggeeft Het kost wat geheugen maar in je voorbeeld gaat het over kilobytes geen terabytes.

[ Voor 54% gewijzigd door curry684 op 11-06-2003 17:40 ]

[curry684]

Extra leesvoer over A* ivm Dijkstra: http://www-cs-students.st...mitp/Articles/AStar1.html

[Kaastosti]

A* lijkt me ook leuk om even door te lezen, maar ik lees hier ook dat dit dezelfde functie heeft als Dijkstra's algoritme, alhoewel hij veel minder geheugen eist. Als ik hiermee inderdaad het aantal paden terug kan krijg ben ik klaar bedankt voor de links!

[WildernessChild]

Maar ff terug naar het probleem: is dit wel Dijkstra's? Stel je even voor dat er maar 2 dimensies zijn: dan hebben we het over een 'huizenblok' van 5 bij 5 huizen (dus 6 bij 6 straten). Dan zijn er 6 over 12 = (6+6)! / (6! * 6!) mogelijkheden voor een kortste route (van 12 stappen). Dit kun je zo doorvoeren naar hogere dimensies en dan kom je (in jouw voorbeeld) uit op (3+2+3+2+4+2)! / (3! * 2! * 3! * 2! * 4! * 2!) = 3027024000 mogelijkheden. Of zie ik dit nu verkeerd...?

[Kaastosti]

Hmmm ja je hebt gelijk... dat klopt. Dit is precies de formule die ik in de site van m'n eerste post vond...

Ik kon dat ding alleen voor mezelf niet omzetten naar het idee van die losse gegevens, ik weet niet waarom, want ik heb er toch al gauw 2,5 uur mee zitten worstelen

[jurri@n]

Dijkstra's algoritme is een algoritme om de beste route over "gewogen" verbindingen te vinden (het gewicht kan afstand, tijd, geld, enc. zijn. Het algoritme kiest dan dus de snelste, goedkoopste, enz.). Dit wordt onderandere toegepast in routers...

ik zal even zoeken... volgens mij zag ik hier pas iets over op howstuffworks.com

edit: gevonden! op http://computer.howstuffworks.com/routing-algorithm3.htm staat een stukje over dijkstra's algoritme, met uitleg en een stukje C-code.

[ Voor 25% gewijzigd door jurri@n op 11-06-2003 20:15 ]

[Kaastosti]

Okee dan nuttige informatie

[Knutselsmurf]

WildernessChild schreef op 11 juni 2003 @ 19:46:
Maar ff terug naar het probleem: is dit wel Dijkstra's? Stel je even voor dat er maar 2 dimensies zijn: dan hebben we het over een 'huizenblok' van 5 bij 5 huizen (dus 6 bij 6 straten). Dan zijn er 6 over 12 = (6+6)! / (6! * 6!) mogelijkheden voor een kortste route (van 12 stappen). Dit kun je zo doorvoeren naar hogere dimensies en dan kom je (in jouw voorbeeld) uit op (3+2+3+2+4+2)! / (3! * 2! * 3! * 2! * 4! * 2!) = 3027024000 mogelijkheden. Of zie ik dit nu verkeerd...?

Je mogelijkheden zijn een stuk beperkter. Als je je huizenblok op een stukje ruitjespapier tekent en van linksonder naar rechtsboven wilt bewegen, heb je op een willekeurig kruispunt maar 2 mogelijkheden: naar rechts of naar boven.

Een methode om dit in 2D op te lossen is de volgende:

- eerst krijgen de punten die langs de assen liggen de waarde 1. Deze punten kunnen immers maar op 1 manier bereikt worden, langs die as. dus P(x,0)=1 en P(0,y)=1
- Vervolgens kun je voor alle andere punten de volgende relatie gebruiken: P(x,y)=P(x-1,y)+P(x,y-1)

Matrix vullen en aflezen

Voor 3D wordt de boel iets ingewikkelder. Dan moet je eerst 3 assen initialiseren, dus P(x,0,0)=1 en P(0,y,0)=1 en P(0,0,z)=1.
Voor de overige punten moet je dan de volgende relatie gebruiken (P(x,y,z)=P(x,1,y,z)+P(x,y-1,z)+P(x,y,z-1)

4D, 5D, 6D kan je nu zelf wel uitzoeken ....

[WildernessChild]

Knutselsmurf: je doet ingewikkeld. Wat je probeert is in feite de hele driehoek van Pascal uit te schrijven, en dan niet voor 2, maar gelijk ook maar voor 6 dimensies. Werkt wel, maar kost een hoop geheugen en tijd, en met mijn formule ben je er in een keer. Misschien toch maar eens een wiskundeboek openslaan?

[Knutselsmurf]

WildernessChild schreef op 12 June 2003 @ 09:12:
Knutselsmurf: je doet ingewikkeld. Wat je probeert is in feite de hele driehoek van Pascal uit te schrijven, en dan niet voor 2, maar gelijk ook maar voor 6 dimensies. Werkt wel, maar kost een hoop geheugen en tijd, en met mijn formule ben je er in een keer. Misschien toch maar eens een wiskundeboek openslaan?

Wiskunde is nooit mijn sterkste punt geweest De reden dat ik het zo opschreef, is dat ik zelf ooit iets dergelijks heb opgelost, maar toe zaten er gaten in het raster. En dan wordt mijn methode, hoewel uiteraard trager dan 1 formule, wel interessanter.....

[curry684]

Mwah ik had ook niet echt opgelet bij het originele probleem, maar zolang je kunt voorspellen wat de afstand tussen 2 willekeurige punten is (dus geen handelsreizigersprobleem) is A* veel beter, sneller en resourcevriendelijker dan Dijkstra. Bij gaten in het raster moet je dus gewoon A* pakken

(Mental note: alle RTS spellen gebruiken A* voor real-time pathfinding om bomen/meren/etc. I have a point )

[Soultaker]

Wat voor wegen heb je? Een beetje een kubus-idee, dus dat er uitsluitend een weg bestaat tussen locaties waarvan 1 coordinaat precies 1 eenheid verschilt? Dan lijkt de oplossing me vrij makkelijk, want je weet dan altijd precies uit welke stappen een kortste weg bestaat en hoef je alleen maar het aantal mogelijke volgordes voor die stappen te berekenen.

Om dit in te zien, kun je er prima een 2D-probleem van maken. Bedenk daarbij dat je met naar rechts stappen en vervolgens naar boven, je op hetzelfde punt terecht komt, als wanneer je eerst naar boven zou stappen, en vervolgens naar rechts.

off-topic:

curry684 schreef op 12 June 2003 @ 12:22:
(Mental note: alle RTS spellen gebruiken A* voor real-time pathfinding om bomen/meren/etc. I have a point )

Vind je? Ik weet wel dat ik me altijd dooderger aan de brakke pathfinding in spellen als C&C en Warcraft III (hoewel StarCraft wel weer prima ging, waarschijnlijk vanwege de eenvoudigere maps), dus wat dat betreft is een handiger algoritme wel op z'n plaats.

Overigens zijn de problemen die daarbij optreden vooral problemen met groepsgedrag (of beter gezegd: het gebrek daaraan), waardoor eenheden elkaar voor de voeten lopen en legers zich ongewild opsplitsen in kleine groepjes die verschillende paden kiezen.

[ Voor 39% gewijzigd door Soultaker op 12-06-2003 14:33 ]

[80000]

curry684 schreef op 11 June 2003 @ 17:38:
Volgens mij kun je dit met een heel simpele A* (A-star) engine ook zo oplossen.

curry684 schreef op 12 June 2003 @ 12:22:
Mwah ik had ook niet echt opgelet bij het originele probleem, maar zolang je kunt voorspellen wat de afstand tussen 2 willekeurige punten is (dus geen handelsreizigersprobleem) is A* veel beter, sneller en resourcevriendelijker dan Dijkstra. Bij gaten in het raster moet je dus gewoon A* pakken

Het dijkstra algoritme geeft je de kortste route van node A naar een node B binnen een gewogen netwerk. Het geeft tevens alle korte routes van node A naar alle andere nodes in het netwerk.
Dit allemaal met redelijke complexiteit en redelijk berekenbaar op huidige computers zolang het aantal nodes binnen de perken blijft.

Het A* algortime is gebaseerd op het dijkstra algoritme, het is een heuristiek die een "richtingsfunctie" gebruikt om een beperkt aantal nodes te evalueren om van node A naar node B te gaan. Aangezien dit een heuristiek is zal het ook niet alle kortste routes naar alle andere nodes vinden. Vandaar de mindere resource eisen dan Dijkstra.

Om A* te begrijpen kan je beter de basis begrijpen: Dijkstra algoritme. Het is dus niet "simpeler" dan Dijkstra en niet expliciet beter dan Dijkstra. Zolang het aantal nodes beperkt blijven, voldoet Dijkstra ruim voldoende. Heb je performance of resource problemen, dan kan je je Dijkstra implementatie verbeteren met A*.

[xerix]

Ik heb een tijdje geleden een pathfinding algoritme bedacht (zal waarschijnlijk vast wel iets soortegelijks bestaan) voor een simpel RTS spelletje. Het werkt op basis van een 2D matrix en houdt geen rekening met afstanden. De afstand tussen elk punt is 1.
De werking is als volgt

De werking van het algoritme is als volgt, stel men wil van positie (0, 0) naar positie (4, 4)
Er wordt in een array die dezelfde grootte als het complete landschap heeft op het startpunt (0, 0) een 1 gezet.



Bij de volgende stap wordt, waar mogelijk, rondom de positie van de vorige stap een 2 gezet. Een grijs vlak is in dit voorbeeld een punt waar de unit niet over heen kan, dit kan dus water of een boom of iets dergelijks zijn.



De vorige stap wordt herhaalt totdat er een getal op het eindpunt wordt gezet.



Uiteindelijk zal het er in geval van dit voorbeeld zo uit komen te zien.



Als de eindpositie is bereikt wordt er vanaf het eindpunt teruggegaan naar het begin punt. Dit gebeurt door te kijken op welke positie de stap zit van de huidige positie – 1.
Op de eindpositie staat in dit geval een 9, er wordt dus gekeken waar het getal 8 staat. Dit kan links, rechts, boven of onder zijn. Als de positie gevonden is wordt deze onthouden en wordt er weer de zelfde procedure uitgevoerd. Dit wordt herhaalt totdat er weer op het beginpunt is aangekomen.

In dit voorbeeld zijn er twee routes met dezelfde lengte mogelijk. Door een bepaalde volgorde te kiezen in het algoritme zal de uiteindelijk route uitkomen op het volgende.

Misschien heb je er wat aan. Heb eventueel implementatie in C++

[Soultaker]

80000 schreef op 12 June 2003 @ 20:06:
Het A* algortime is gebaseerd op het dijkstra algoritme, het is een heuristiek die een "richtingsfunctie" gebruikt om een beperkt aantal nodes te evalueren om van node A naar node B te gaan. Aangezien dit een heuristiek is zal het ook niet alle kortste routes naar alle andere nodes vinden. Vandaar de mindere resource eisen dan Dijkstra.

Wanneer je kunt aantonen (of gewoon aanneemt) dat je heuristiek een optimale strategie is (zoals volgens mij ook in het geval van de topic starter het geval is), dan zijn de resultaten van het A* algoritme hetzelfde als die van Dijkstra's algoritme en is de implementatie minstens net zo makkelijk. In het algemeen gaat dit naturlijk niet op, maar dat spreekt voor zich.

Om A* te begrijpen kan je beter de basis begrijpen: Dijkstra algoritme. Het is dus niet "simpeler" dan Dijkstra en niet expliciet beter dan Dijkstra. Zolang het aantal nodes beperkt blijven, voldoet Dijkstra ruim voldoende. Heb je performance of resource problemen, dan kan je je Dijkstra implementatie verbeteren met A*.

Ik vind A* toch echt veel makkelijker te begrijpen, hoor. Zeker de complexiteitsbewijzen bij Dijkstra's algoritme vind ik lang niet eenvoudig. Dat kan aan mij liggen, maar dat betekent tenminste dat wat "simpeler" is, niet zomaar objectief vast te stellen is.

[Mithrandir]

xerix schreef op 12 juni 2003 @ 20:28:
Ik heb een tijdje geleden een pathfinding algoritme bedacht (zal waarschijnlijk vast wel iets soortegelijks bestaan) voor een simpel RTS spelletje. Het werkt op basis van een 2D matrix en houdt geen rekening met afstanden. De afstand tussen elk punt is 1.
De werking is als volgt


[...]


Misschien heb je er wat aan. Heb eventueel implementatie in C++

het is een vereenvoudigde A* lijkt mij. op www.gameskool.nl staat een goede tutorial/uitleg over A* en dijkstra's algoritme. (je moet deel 2 van 2d games hebben geloof ik)

A* houdt o.a. 2 variabelen bij: een hemelsbrede afstand van een punt naar het punt waar je heen wilt (even a genoemd hier), en de afstand van het startpunt naar het punt waar de pointer nu staat. Iedere volgende die gepakt wordt is het punt waar a + b het laagst is.

Verdere info staat op gameskool.nl dus

[80000]

[quote]Soultaker schreef op 12 June 2003 @ 20:36:

Ik vind A* toch echt veel makkelijker te begrijpen, hoor. Zeker de complexiteitsbewijzen bij Dijkstra's algoritme vind ik lang niet eenvoudig. Dat kan aan mij liggen, maar dat betekent tenminste dat wat "simpeler" is, niet zomaar objectief vast te stellen is.

A* zat zo ongeveer in elkaar:

code:

f = g + h

met
f de schattingsfunctie binnen het A* algoritme
g de tot nu toe werkelijke route tot current node (x,y)
h de schatting afstand tot doel node(x,y)

h wordt meestal geschat door de absolute waarde te nemen tussen de current node en doelnode. g +h bepaalt welke volgende node je wil evalueren, echter omdat je schatting h fout kan zijn, kun je te snel een node op de stack stoppen die niet het kortste pad is. Dus wil je perse optimaal zijn dan kan je beter h = 0 kiezen om alle nodes te evalueren => maar dan heb je Dijkstra.

Dus Dijkstra is eigenlijk hetzelfde als A* met een schattingsfunctie die een ondergrens 0 heeft.

A* heeft vrijwel dezelfde basis implementatie qua datastructuren nodig als een Dijkstra, aangezien ze vrijwel hetzelfde zijn. Het lijkt me dus niet simpeler (of moeilijker) en als iemand zich echt wil verdiepen kortste route theorie, is mijn advies nog steeds beginnen met Dijkstra, zoals de topic starter deed.

[curry684]

Soultaker schreef op 12 juni 2003 @ 14:30:
Vind je? Ik weet wel dat ik me altijd dooderger aan de brakke pathfinding in spellen als C&C en Warcraft III (hoewel StarCraft wel weer prima ging, waarschijnlijk vanwege de eenvoudigere maps), dus wat dat betreft is een handiger algoritme wel op z'n plaats.

A* kun je zo goed of slecht maken als je wilt, afhankelijk van je available resources. WC3 vind ik zelf eigenlijk knap goed, die heb ik geprobeerd te misleiden.

Inspiratie: AI Game Programming Wisdom, edited by Steve Rabin. Diverse advanced artikelen over A*, waaronder de technieken om ze zo snel en intelligent mogelijk te maken

[curry684]

80000 schreef op 12 juni 2003 @ 20:06:
Het A* algortime is gebaseerd op het dijkstra algoritme, het is een heuristiek die een "richtingsfunctie" gebruikt om een beperkt aantal nodes te evalueren om van node A naar node B te gaan. Aangezien dit een heuristiek is zal het ook niet alle kortste routes naar alle andere nodes vinden. Vandaar de mindere resource eisen dan Dijkstra.

Dank voor het moeilijker uitleggen wat ik erboven zei Zolang je een x-dimensioneel grid hebt is A* vrijwel per definitie de beste methode omdat de 'voorspelling' of 'heuristiek' erg simpel en 'goedkoop' dmv de Manhattan-afstand (verschillen van alle assen optellen).

Om A* te begrijpen kan je beter de basis begrijpen: Dijkstra algoritme. Het is dus niet "simpeler" dan Dijkstra en niet expliciet beter dan Dijkstra. Zolang het aantal nodes beperkt blijven, voldoet Dijkstra ruim voldoende. Heb je performance of resource problemen, dan kan je je Dijkstra implementatie verbeteren met A*.

Uhm A* is echt wel stukken simpeler zodra je 'm doorhebt. Zie ook Soultaker

[80000]

curry684 schreef op 13 June 2003 @ 00:04:

Dank voor het moeilijker uitleggen wat ik erboven zei Zolang je een x-dimensioneel grid hebt is A* vrijwel per definitie de beste methode omdat de 'voorspelling' of 'heuristiek' erg simpel en 'goedkoop' dmv de Manhattan-afstand (verschillen van alle assen optellen).

Klinkt zeer logisch.

Uhm A* is echt wel stukken simpeler zodra je 'm doorhebt. Zie ook Soultaker

Ik ben waarschijnlijk te theoretisch bezig. Als je Dijkstra (eerst) begrijpt zul je (volgens mij) zonder moeite A* begrijpen aangezien ze hetzelfde zijn.
Doe je het andersom, tja dan is alle hoop eigenlijk al verloren.
Ik hou al op

[curry684]

80000: Lees dat boek eens wat ik aanwees Je kunt diverse heel goede en 'goedkope' optimalisaties uitvoeren op A* waardoor je zeer goede resultaten krijgt. Moderne A* engines maken de volgende 3 paths: Quick Path, Full Path en Spline Path. Op het moment van 'klik' wordt een cheap&dirty path halfwassen path berekent zodat de unit kan gaan lopen. De Full Path wordt vervolgens 'Load Balanced' berekend terwijl de unit loopt. Zodra het Full Path definitief is wordt er een nieuwe Quick Path gemaakt van huidige positie tot op x% van het Full Path. Met deze techniek wordt ook ruim om meren e.d. gelopen, en worden de benodigde resources verspreid.