Routeplanner?

[Explore]

Er is geen 'algoritme' forum aanwezig en dit is ook geen 'source request' ofzo, maar een algoritme request.

Ik wil een routeplanner maken, maar breek m'n hoofd over het algoritme. Ik ruik recursiviteit van een afstand en natuurlijk een grote database met straat-gegevens er in, maar hoe zou je zoiets verder aanpakken? Iemand ideeen?

[Skinny]

And the man of the match is ! ... roffel...

G o o g l e : http://www.google.com/search?q=shortest+path+algorithm&hl=nl&lr=

[Aetje]

Je kunt met coordinaten werken voor loodrechte afstanden. Als je van plaats A naar plaats B moet en dat niet loodrecht kunt, zul je dat waarschijnlijk in een afstandentabel moeten zetten.

[Explore]

Aaah... Dijkstra's algoritme! Ik had al op google gekeken naar bv. 'routeplanner algoritme', maar dat leverde 0 resultaten. Ik zal de berg links eens doornemen.

De data opslag is ook een probleem. Er zullen inderdaad afstandstabellen in moeten, maar bijvoorbeeld ook voorkeurswegen. Grote doorgangswegen hebben een voorkeur voor kleine binnendoorweggetjes/steegjes. Dat soort info moet ook worden verwerkt, om nog maar niet te spreken van een-richtingverkeer, etc...

[Verwijderd]

Rechte lijn van A naar B.
Wegen zoeken die zoveel mogelijk aansluiten bij rechte lijn.
En zo kom je van A naar B.

En dit alles moet idd. recursief want stel dat je bezig bent met een route te berekenen en die blijkt niet uit te komen op het aankomstpunt dan zul je opnieuw terug moeten keren naar een bepaald punt en van daar uit weer alternatieve route bedenken.

Wil je ook nog rekening gaan houden met provinciale wegen, snelwegen etc dan wordt het nog even wat moeilijker.

Als we het over DB hebben, Oracle wordt meestal voor dit soort 'GIS'-zaken gebruikt. Hiermee schijn je spatial queries uit te kunnen voeren. Dit is een term die ik eens heb horen vallen in relatie tot GIS dus ik kan het helemaal vaud hebben.

Al met al lijkt me dit behoorlijk moeilijke maar zeer interessante materie.

[Pelle]

Pathfinding is best interessant ja. Denk dat je een heel eind komt door een soort van verbindingsmatrix te gaan bouwen, waarin je bijhoudt welke punten door middel van een weg met elkaar verbonden zijn, en wat de afstand ertussen is.
Als je zover bent, dan moet je inderdaad nog een keer een manier vinden om de kortste route te berekenen. Denk dat je bijvoorbeeld ook bij zult moeten houden wat de snelheid is die je op die weg mag rijden. Je gaat iemand niet 30 kilometer aan sluitproutes laten rijden terwijl er vlak in de buurt een snelweg ligt.

En daarnaast is recursie zeker weten je vriend; met brute force is het ook wel te doen maar dat gaat allemaal wat langer duren

[Verwijderd]

Volgens mij moet je het toch recursief doen met behulp van backtracking?? heeeel lang geleden dat ik dit gehad heb..

[dusty]

hehehe ik zie al heel veel mensen gaan werken aan een database met alle mogelijkheden aflopen

vanuit Gorinchem naar Breda ga je eerst alles naar "boven" af leggen, betekent dat je eerst 70% van nederland door gaat lopen aan de bovenkant en dan pas naar beneden, richting Breda
Natuurlijk ga je ook alle wegen proberen via de kleinste straatjes

[raptorix]

Gorinchem Breda is een makkie, er loopt 1 karrespoor

[dusty]

Op donderdag 10 januari 2002 16:19 schreef raptorix het volgende:
Gorinchem Breda is een makkie, er loopt 1 karrespoor

Nee, 1 File

[80000]

Heb er 1 gemaakt.

In zijn meest simpele vorm:
1 - kwalitatieve db van een gesloten netwerk (kan je kopen)
2 - Dijkstra algoritme welke O(n) is, met n het aantal
nodes in je netwerk.

Oracle spatial en haar spatial query levert alleen
maar de euclidische afstand.

[Verwijderd]

Op donderdag 10 januari 2002 15:46 schreef Explore het volgende:
Aaah... Dijkstra's algoritme! Ik had al op google gekeken naar bv. 'routeplanner algoritme', maar dat leverde 0 resultaten. Ik zal de berg links eens doornemen.

De data opslag is ook een probleem. Er zullen inderdaad afstandstabellen in moeten, maar bijvoorbeeld ook voorkeurswegen. Grote doorgangswegen hebben een voorkeur voor kleine binnendoorweggetjes/steegjes. Dat soort info moet ook worden verwerkt, om nog maar niet te spreken van een-richtingverkeer, etc...

Hehe, heel ambitieus plan hoor ik hier, een routeplanner maken. Dijkstra is inderdaad je vriend ja, maar niet brute force, dat ga je namelijk never nooit trekken om *alle* mogelijkheden na te lopen (trust me on this one....). Voorkeurswegen kun je wel doen door lage kosten toe te kennen aan dit soort wegen (en wegen waar je liever niet langs wil gaan geef je uiteraard hoge kosten). Eenrichtingsverkeer kun je afvangen tijdens het bouwen van je graaf, dus dat is het probleem niet. Ik denk dat je het best eens kunt zoeken op het A*-algoritme (Soort dijkstra) en mocht je meer willen weten over dijkstra, dan hoor ik het graag hoor

[RickN]

Op vrijdag 11 januari 2002 23:26 schreef Stoned-cow het volgende:

[..]

Hehe, heel ambitieus plan hoor ik hier, een routeplanner maken.
[..]

[opschep mode]
Mwa, da's nog niet echt ambitieus hoor... Dit is ambiteus:

Van de website van mijn voormalige stage bedrijf:
Combinatie Module voor Taxis 2000.

De Combinatie Module voor Taxis 2000 automatiseert de arbeidsintensieve taak van het samenstellen van routes. Het vinden van de voordeligste verzameling routes bij een gegeven verzameling ritten staat in wiskundige kringen bekend als een zéér complex probleem dat zelfs op de snelste computers letterlijk jaren kan duren om op te lossen. Onze Combinatie Module maakt gebruik van geavanceerde technieken om toch al binnen enkele minuten een verzameling routes te vinden met een aanmerkelijke besparing op het aantal te rijden kilometers.

Ritten die voor combinatie in aanmerking komen worden uit de database gelezen en vervolgens in routes verwerkt, die weer naar de database worden geschreven en in de Taxis 2000 Client zichtbaar worden. U heeft zelf invloed op de gegenereerde routes door b.v. in te stellen hoeveel maximaal mag worden afgeweken van de gewenste aankomsttijd op een bepaalde locatie en met hoeveel de de reistijd van een klant maximaal mag worden verlengt als zijn rit in een route wordt geplaats. Verder wordt ook rekening gehouden met wensen (eisen) van klanten om b.v. voorin te mogen zitten, in een specifiek type vervoersmiddel te worden vervoerd, of om niet per bus te worden vervoerd. Ook kunt u instellen of klanten van verschillende vervoerstypen mogen worden gecombineerd en van welke wagensoorten een vervoerstype gebruik mag maken. De Combinatie Module voor Taxis 2000 biedt uitgebreide print mogelijkheden waarmee onder andere de te combineren ritten en de uiteindelijk gegenereerde routes kunnen worden afgedrukt. Ook rapporteerd de module over de benodigde hoeveelheid wagens van een type gedurende de dag, waarbij onderscheid wordt gemaakt tussen routes die verplicht door een bepaald type wagen moet worden gereden en routes waarvoor geen wagentype eis geldt. In de praktijk laat de Combinatie Module kilometerbesparingen zien tot wel 20% en dat na slechts 1 minuut rekenen. U kunt zich wel voorstellen hoeveel u dat, met de huidige benzineprijzen, in uw portemonee kan schelen!

Dit was dus mijn stageopdracht en daar is best iets goeds uitgekomen al zeg ik het zelf

[/opschep mode]

[Verwijderd]

Op zaterdag 12 januari 2002 01:01 schreef RickN het volgende:

[..]

[opschep mode]
Mwa, da's nog niet echt ambitieus hoor... Dit is ambiteus:
[..]

Dit was dus mijn stageopdracht en daar is best iets goeds uitgekomen al zeg ik het zelf

[/opschep mode]

Dit was eigenlijk wat ik ook voor ogen had , maaruh, die planner werkt ongetwijfeld niet in minuten wanneer heel nederland in ogenschouw genomen wordt. (of je moet iets met lokale en globale planners doen) Kan me herinneren dat er een softwareproject was aan UU waarin dit geimplementeerd moest worden...

[Explore]

Ik heb inmiddels een uitgebreid plan opgesteld, maaruh hierin ga ik wel uit van een brute-force methode. Dit omdat het probleem nog wel te overzien valt. Maar ik zal zeker Dijkstra of A* (hoe zoek je dat in google? ) nog eens nauwkeurig onder de loep nemen alvorens ik aan de implementatie begin...

[80000]

Door Explore - zaterdag 12 januari 2002 03:02
Ik heb inmiddels een uitgebreid plan opgesteld, maaruh
hierin ga ik wel uit van een brute-force methode.

Oef, mag ik je raad geven dat je zowel een performance
als een memory probleem dan hebt.
Een beetje wegennetwerk zoals nederland heeft dacht ik
1,5 miljoen nodes, duitsland het 10 voudige (weet het niet
zeker meer uit mijn hoofd, pin me er niet op vast, kan het nazoeken) en een x voudige aan links.
Ook hierop gaat dijkstra (en A*) kapot en zul je hier bovenop slimmere dingen moeten verzinnen.

Succes!

[Verwijderd]

Op zaterdag 12 januari 2002 10:44 schreef 80000 het volgende:
Oef, mag ik je raad geven dat je zowel een performance
als een memory probleem dan hebt.

Idd, tis niet dat we de topicstarter willen ontmoedigen hoor , maar feit is gewoon dat dit soort problemen heel erg snel heel erg uit de klauwen loopt qua memory-usage en rekentijd..

[80000]

Cow, je hebt gelijk, sorry. Het hangt allemaal af van
de doelstellingen die de starter in
zijn plan heeft staan.

[RickN]

Op zaterdag 12 januari 2002 01:18 schreef Stoned-cow het volgende:

[..]

Dit was eigenlijk wat ik ook voor ogen had , maaruh, die planner werkt ongetwijfeld niet in minuten wanneer heel nederland in ogenschouw genomen wordt.

Jawel, sterker nog, in pricipe wordt die planner alleen gebruikt voor interregionaal verkeer.

Aantekening: mijn planner had niks te maken met een kortste pad algoritme, de routes die ik moest maken waren meer van pik hier iemand op, pik er daar nog een op, zet er hier een af, pik er daar een op...enz. Door welke straten er vervolgens van A naar B werd gereden hoefde ik niet te bepalen, dat heeft ook geen zin want taxichauffeurs vinden toch altijd dat ze het beter weten. Dit is een zogenaamd Dial-a-Ride probleem met multiple capacities, multiple vehicles en time windows en dat is een subset van de zogenaamde scheduling problemen. Die problemen los je niet op met simpele graaf algoritmes, ik heb het opgelost met een heuristische zoekmethode.

[Verwijderd]

Het is in principe een zoekboom-probleem, je kunt dat oplossen met simpele zoekmethoden als depth-first-search of breadth-first-search, maar waarschijnlijk zal je boom te complex zijn, waardoor het te veel tijd-geheugen gaat kosten.
Je zult dus een heuristische zoekmethode nodig hebben, waarbij je het nut van het gaan naar een andere plaats berekent, bijv. d.m.v. het gebruik van hemelsbrede afstanden o.i.d.
Dit si echter erg ingewikkeld, en je moet niet vergeten dat een heuristische zoekmethode niet in alle gevallen een oplossing oplevert.

Succes ermee

[Verwijderd]

Op zaterdag 12 januari 2002 12:00 schreef RickN iets wat véél verschil uitmaakte.

[..]

Ja hé, zo kan ik het ook , maar daarbij laat je het computationeel moeilijke werk over aan de chauffeur, terwijl dat nu juist is wat de topicstarter mbv de computer wil doen. En 'simpele graafalgoritme'... gevaarlijke uitspraak hoor

[RickN]

Op zaterdag 12 januari 2002 13:53 schreef Stoned-cow het volgende:

[..]

Ja hé, zo kan ik het ook , maar daarbij laat je het computationeel moeilijke werk over aan de chauffeur, terwijl dat nu juist is wat de topicstarter mbv de computer wil doen. En 'simpele graafalgoritme'... gevaarlijke uitspraak hoor

Bwhaaaaahahahahaha!!! Grapjas Ik zou er echt nog maar wat boekjes op na slaan voordat je zoiets zegt Het "single source shortest path"-probleem in een graaf is dus echt niet "computationeel moeilijk", sterker nog: het is, met een goeie implementatie niet eens kwadratisch in het aantal punten van de graaf!!! Het dial-a-ride probleem daarentegen ( ) is gewoon KEIHARD NP-compleet (net als vrijwel alle andere scheduling problemen) Daarvoor hebt je dus echt een heuristische zoekmethode nodig (om überhaupt OOIT een oplossing te kunnen geven) voor een shortest path problem zou ik daar niet aan beginnen, of anders hooguit een heuristiekje waarmee je de route binnen een bepaalde circel houdt b.v.

En over mijn opmerking dat graafalgoritmen simpel zijn: Nou ja, qua rekentijd zijn het niet de meest intensieve problemen en qua implementatie tja, een echt heel efficiente implementatie zal niet makkelijk zijn, maar er is al ZOOO VEEEEL over geschreven dat je zelf nog maar nauwelijks hoeft na te denken. Ik raad de topic starter aan een boek te lenen (Introduction to Algorithms van Cormen) want daar staat precies in hoe je zoiets aanpakt.

[Verwijderd]

Op zaterdag 12 januari 2002 14:34 schreef RickN het volgende:
Bwhaaaaahahahahaha!!! Grapjas Ik zou er echt nog maar wat boekjes op na slaan voordat je zoiets zegt

Ik weet zelf dondersgoed waarover het gaat, in beeld(be/ver)werking worden dit soort algoritmen veelvuldig toegepast (ja ja ) en daar ben ik vrij veel mee bezig...

Het "single source shortest path"-probleem in een graaf is dus echt niet "computationeel moeilijk", sterker nog: het is, met een goeie implementatie niet eens kwadratisch in het aantal punten van de graaf!!!

true.

Het dial-a-ride probleem daarentegen ( ) is gewoon KEIHARD NP-compleet (net als vrijwel alle andere scheduling problemen) Daarvoor hebt je dus echt een heuristische zoekmethode nodig (om überhaupt OOIT een oplossing te kunnen geven) voor een shortest path problem zou ik daar niet aan beginnen, of anders hooguit een heuristiekje waarmee je de route binnen een bepaalde circel houdt b.v.

Juist daar ben ik ook van op de hoogte; ik refereerde aan het feit, dat hoe fantastisch de heuristieke methode bij dail-a-ride mag werken, de topicstarter daar absoluut _NIETS_ aan heeft, gewoon omdat het probleem zich daar niet voor leent. (immers, van den helder naar groningen zonder de afsluitbrug, daar is geen heuristiek voor te vinden)

En over mijn opmerking dat graafalgoritmen simpel zijn: Nou ja, qua rekentijd zijn het niet de meest intensieve problemen en qua implementatie tja, een echt heel efficiente implementatie zal niet makkelijk zijn, maar er is al ZOOO VEEEEL over geschreven dat je zelf nog maar nauwelijks hoeft na te denken. Ik raad de topic starter aan een boek te lenen (Introduction to Algorithms van Cormen) want daar staat precies in hoe je zoiets aanpakt.

Het daadwerkelijk doorzoeken van de graaf is niet intensief, echter belangrijker dan is de stap daaraan vooraf: de kostengraaf. Theoretisch zou je dit ding voor de hele map moeten berekenen: niet spannend rekenkundig, maar lastig doordat het aantal punten zo giga-groot wordt. Wat je dan typisch wil is een manier om alleen in 'zinvolle omgevingen' die kostenmap berekenen.

Verder is bij dit soort problemen is niet eens zozeer het algoritme cruciaal (dat kun je echt belabberd schrijven, ), maar veel meer de datastructuur die erachter hangt (ter verduidelijking: Dijkstra vraagt vaak het punt met de laagste kosten tot nu toe op tijdens het berekenen van kosten en geloof me, dat wil je niet implementeren met een gewone enkel gelinkte lijst )

In dit geval: topicstarter: hoe groot is / wordt je map?

[80000]

[quote]
RickN - zaterdag 12 januari 2002 14:34

[..]
Het dial-a-ride probleem daarentegen ( ) is gewoon KEIHARD NP-compleet (net als vrijwel alle andere scheduling problemen)
[\quote]

Dat is waar, werk ook aan een scheduling probleem welke
ook nog een shortest path probleem in zich heeft.

[quote]
RickN - zaterdag 12 januari 2002 14:34

[..]
Nou ja, qua rekentijd zijn het niet de meest intensieve problemen en qua implementatie tja, een echt heel efficiente implementatie zal niet makkelijk zijn, maar er is al ZOOO VEEEEL over geschreven dat je zelf nog maar nauwelijks hoeft na te denken.
[\quote]

En dat is nou het verschil tussen theorie en praktijk,
want de boekjes (zoals dijkstra met complexiteit O(n), n de nodes in je graaf), lost de praktijk
problemen waarbij n > 1.5 miljoen nog steeds niet
in een redelijke performance op.
Daar komt echt nog wel wat meer om de hoek kijken, zoals
verschillende mensen al aangeven.

[Verwijderd]

met

code:

 [quote] ... [/quote]

ziet het er wat overzichtelijker uit

[80000]

Oeps, gewend aan latex, Thanks!

[RickN]

Op zaterdag 12 januari 2002 15:08 schreef 80000 het volgende:
[..]

En dat is nou het verschil tussen theorie en praktijk,
want de boekjes (zoals dijkstra met complexiteit O(n), n de nodes in je graaf), lost de praktijk
problemen waarbij n > 1.5 miljoen nog steeds niet
in een redelijke performance op.
Daar komt echt nog wel wat meer om de hoek kijken, zoals
verschillende mensen al aangeven.

Dijkstra's kortste pad algoritme is niet O(V), maar O(V log V + E). Dit vereist wel een heel efficiente datastructuur zoals stoned-cow terecht opmerkte. Dat dit algoritme voor bepaalde zeer grote instanties toch nog te veel tijd kost zou ik geen verschil tussen theorie en praktijk noemen, dat is gewoon een triviale consequentie van het feit dat je V en E zo groot mag maken als je zelf wil. Ook in de praktijk zal de running time van een algoritme met theoretische running time O(N) nooit groter zijn dan O(N), lijkt me toch duidelijk. (Als ie namelijk wel groter is, dan is je algoritme gewoon niet O(N))

[Verwijderd]

kijk op www.gis.nl anders mail je hunnie

[80000]

RickN - zondag 13 januari 2002 12:49:

Dijkstra's kortste pad algoritme is niet O(V), maar O(V log V + E)

Je zal wel gelijk hebben, het is 10 jaar geleden. Nu je het zo zegt, volgens mij heb ik dan de verkeerde complexiteit in mijn hoofd, zoiets van in O(n) het minimum pad naar alle andere nodes.
Heb mijn boeken niet bij me. Het is in ieder geval niet kwadratisch en dat is voor mij al belangrijk genoeg.

Dat dit algoritme voor bepaalde zeer grote instanties toch nog te veel tijd kost zou ik geen verschil tussen theorie en praktijk noemen, dat is gewoon een triviale consequentie van het feit dat je V en E zo groot mag maken als je zelf wil

Ok, laat ik anders proberen uit te leggen.
Ben het met je eens, het kortste pad probleem is uitgekauwd
tot en met al vanaf 1930 (prim's algoritme opgelost) en
bekend als dijkstra geworden. Een simpel gewogen graaf, met wat nachtwerk is een implementatie zeker te doen (jaren geleden gedaan).
Echter wat men in de praktijk tegenwoordig van een routeplanner verwacht is al lang niet meer een simpel gewogen graaf:
Kortste route rekening houden met
- Eenrichtingsverkeer
- gem. snelheden per timewindow gedurende een dag (denk aan filestroken zoals in de U.S.)
- Gerestricteerde access van wegen (links) per autotype
(denk aan max tunnelhoogte, maximale brug gewicht)
- tolwegen
- Restaturatie aan wegen
- real time file informatie
- etc.

Het anwoord moet ook nog eens binnen een seconde zijn.

Als jij mij bewijst dat dit niet een hard NP probleem is, trakteer ik je op een biertje en moeten wij eens lekker gaan ouwhoeren over scheduling.
Tot dan geloof ik niet, dat je met een algoritme uit de boeken dit probleem snel oplost. (Laten we zeggen dat ik hier ervaring mee heb)

theoretische running time O(N) nooit groter zijn dan O(N)

Tuurlijk is dat zo, maar daar gaat het niet om. Je kan niet
een netwerk met 1,5 miljoen nodes en een veelvoud van links, simpelweg even in memory laden, een algoritme uit de boeken er tegen aan gooien en verwachten dat je een antwoord hebt binnen een seconde.

Vroegere navigatie systemen moesten (zeg 300 Mb) van een 1 speed cdrom lezen. Om de performance te halen zullen ongetwijfeld heel slim geindexed hebben.

P.S. Ik vind het andere geslacht pas een keihard NP probleem

[Janoz]

Op zondag 13 januari 2002 15:36 schreef 80000 het volgende:


Ok, laat ik anders proberen uit te leggen.
Ben het met je eens, het kortste pad probleem is uitgekauwd
tot en met al vanaf 1930 (prim's algoritme opgelost) en
bekend als dijkstra geworden. Een simpel gewogen graaf, met wat nachtwerk is een implementatie zeker te doen (jaren geleden gedaan).
Echter wat men in de praktijk tegenwoordig van een routeplanner verwacht is al lang niet meer een simpel gewogen graaf:
Kortste route rekening houden met
- Eenrichtingsverkeer

gerichte graaf

- gem. snelheden per timewindow gedurende een dag (denk aan filestroken zoals in de U.S.)
- Gerestricteerde access van wegen (links) per autotype
(denk aan max tunnelhoogte, maximale brug gewicht)
- tolwegen

Kun je gewoon als eigenschappen bij een edge doen. Waneer het voertuig niet aan de eisen voldoet, wordt de edge genegeerd.

- Restaturatie aan wegen

Ook eigenschappen van een edge, amar deze hoef je pas te laten zien als je de route al bepaad hebt.

- real time file informatie

Dit is meer van belang als je de route bepaald tijdens het rijden. Je zou dan in het geheugen het relevante gedeelte (zie verder naar onderen) opslaan met de bijbehoorende scores. Er hoeft dan alleen bij een file(af)melding een stukje route te worden aangepast.

Tuurlijk is dat zo, maar daar gaat het niet om. Je kan niet
een netwerk met 1,5 miljoen nodes en een veelvoud van links, simpelweg even in memory laden, een algoritme uit de boeken er tegen aan gooien en verwachten dat je een antwoord hebt binnen een seconde.

Vroegere navigatie systemen moesten (zeg 300 Mb) van een 1 speed cdrom lezen. Om de performance te halen zullen ongetwijfeld heel slim geindexed hebben.

Het wegennet is redelijk goed onder te verdelen in verschillende lagen. Als je een route in maastricht plant hoef je geen karrespoor in friesland in je geheugen te zetten. Je zou het route bepalen kunnen opsplitsen in
1 Hoe kom ik het snelst van mijn startpunt op de snelweg
2 Hoe kom ik op de snelweg naar mijn bestemming
3 Hoe kom ik vanaf de snelweg op de bestemming aan.

Ik stel het idd een beetje simpel, maar je kunt je graaf behoorlijk uitdunnen, desnoods met uit de beeldbewerking beschikbare decimatie technieken, waardoor je een behoorlijk werkbare dataset overhoud.

[80000]

Janoz - zondag 13 januari 2002 18:01:

[.. Een prachtige implementatie weggeknipt ..]

Ik stel het idd een beetje simpel, maar je kunt je graaf

Nou ja, zonder iemand op zijn tenen te trappen, er was iemand die zei dat dit niet ambitieus was.

desnoods met uit de beeldbewerking beschikbare decimatie technieken, waardoor je een behoorlijk werkbare dataset overhoud.

Ken decimatie niet, maar goed, er komt dus een heleboel interessante andere technieken naar boven drijven (GIS kent er nog wel wat).

[RickN]

Op zondag 13 januari 2002 18:01 schreef Janoz iets wat ik zelf had willen schrijven.

Die punten die je daar opsomt die had ik dus ook zo bedacht .

80000:
In het ergste geval kun je geen statische kosten matrix maken, maar moet je de kosten voor een edge telkens runtime berekenen. Maar zelfs dan, als dat berekenen polynomiaal blijft, is het probleem niet NP-hard, wel inefficient dus, maar niet NP-hard. Hoe je het ook wend of keert en wat voor restricties je ook toevoegd (binnen redelijke grenzen) het onderliggende probleem blijft hier gewoon een kortste pad probleem en dat is gewoon niet NP-hard. Het feit dat al die restricties het probleem nog lastiger maken en het in de praktijk voor 1.5 miljoen knopen niet efficient op te lossen valt doet daar niets aan af. Vergelijk ook ff met een ECHT NP-compleet probleem als het Traveling Salesman Probleem: dat is met een super inteligente oplossing al bij een paar honderd knopen niet meer efficient op te lossen en bij een simpele naïeve oplossing bij +/- 20 knopen al niet meer!!!!

80000 schreef:
Als jij mij bewijst dat dit niet een hard NP probleem is, trakteer ik je op een biertje en moeten wij eens lekker gaan ouwhoeren over scheduling.

Mmm, ik lust geen bier.... bacardi breezer ook goed

[Verwijderd]

[Verwijderd]

Op maandag 14 januari 2002 12:08 schreef hill het volgende:

[Verwijderd]

Hmmm een half jaar geleden heeft mijn oom toevallig uitgelegd hoe het werkte aan mij maar ik ben het effe kwijt ik had het nog wel opgeschreven effe kijken of ik het kan vinden. Maar ik weet wel dat ie gewoon elke mogelijke oplosing probeert van a naar b te gaan maar hij begint aan beide kanten te gelijk.

[Explore]

Op vrijdag 11 januari 2002 23:26 schreef Stoned-cow het volgende:

[..]

Hehe, heel ambitieus plan hoor ik hier, een routeplanner maken. Dijkstra is inderdaad je vriend ja, maar niet brute force, dat ga je namelijk never nooit trekken om *alle* mogelijkheden na te lopen (trust me on this one....).

Ik wou het toch even zeker weten, ennuh... Ja, je hebt gelijk.

Ik denk dat je het best eens kunt zoeken op het A*-algoritme (Soort dijkstra) en mocht je meer willen weten over dijkstra, dan hoor ik het graag hoor

Ja, vertel eens wat meer over Dijkstra...