Thread: MYSQL: Routeplanner
-
08-10-2007, 15:28 #1Member
- Registered
- 23/05/04
- Location
- Madrid
- Posts
- 140
- iTrader
- 2 (100%)
- Mentioned
- 0 Post(s)
- Reputation
- 0/0
MYSQL: Routeplanner
Hallo,
ik ben aan het werken aan een systeempje die de kortste route van punt A naar punt B berekent. Dit mbv PHP & MySQL.
Het systeem maakt gebruikt van het Dijkstra-algoritme
http://hansolav.net:80/blog/Implemen...UsingTSQL.aspx
Ik heb de deze code omgezet zodat die werkt met PHP.
Het voorbeeldje in de link werkt dus ook perfect.
Nu, het probleem is niet werking ervan, maar wel de snelheid van berekenen..
Met 10 of 100 records in de database gaat alles vlot, maar nu heb ik mn database aangevuld met 3000 locaties en het duurt tot 30 seconden om een route te berekenen.
Iemand een idee hoe ik dit sneller kan laten gaan, of zou ik misschien beter een ander systeem overwegen?
Alvast bedankt!no votes
-
-
08-10-2007, 16:05 #2Member
- Registered
- 12/10/02
- Location
- mars
- Posts
- 14,319
- iTrader
- 2 (100%)
- Mentioned
- 0 Post(s)
- Reputation
- 0/0
A* algoritme wordt vaak gebruikt in games (en die zijn vrij tijdskritisch).
maar dat is EEN padberekening, niet steeds perfect optimaal (hangt af van implementatie & eisen).
edit: en mssch is jouw dijkstra implementatie ook gewoon vrij traag
.
no votes
-
08-10-2007, 16:09 #3Member
- Registered
- 23/05/04
- Location
- Madrid
- Posts
- 140
- iTrader
- 2 (100%)
- Mentioned
- 0 Post(s)
- Reputation
- 0/0
no votes
-
08-10-2007, 21:04 #4Member
- Registered
- 12/10/02
- Location
- mars
- Posts
- 14,319
- iTrader
- 2 (100%)
- Mentioned
- 0 Post(s)
- Reputation
- 0/0
http://en.wikipedia.org/wiki/A_Star
en gamedev.net ofzo
dnno voor de rest hoor, mijn resources daarvan zijn men gameprogramming gems boeken
.
no votes
-
08-10-2007, 21:15 #5Verwarmingselement
- Registered
- 01/07/02
- Location
- Brussel
- Posts
- 3,810
- iTrader
- 14 (100%)
- Mentioned
- 1 Post(s)
- Reputation
- 0/22
Post de code voor uw Dijkstra algoritme eens zou ik dan zeggen.
Of er betere algoritmes zijn, geen idee, ik ben geen wiskundige, maar aangezien een aantal routing protocols Dijkstra gebruiken veronderstel ik dat het vrij optimaal is.
Edit : als je wil, post het dan evt met volledige source en SQL files zodat we er wat mee kunnen spelen, ik vind zoiets wel een leuke uitdaging
no votes
-
08-10-2007, 21:42 #6Member
- Registered
- 12/10/02
- Location
- mars
- Posts
- 14,319
- iTrader
- 2 (100%)
- Mentioned
- 0 Post(s)
- Reputation
- 0/0
dijkstra = N² in pure vorm iirc (lang geleden dat ik het nog geïmplementeerd heb).
Dus met 3000 records zit je toch al gauw aan een 9000000 iteraties, wat al kan tellen als je datastructuur niet goed is opgesteld
. Dus idd, uw code is posten kan wel handig zijn
.
er bestaan wel iets optimalere hoor
. A* in bepaalde vormen is gelijk aan dijkstra trouwens radiance.
no votes
-
09-10-2007, 09:18 #7Member
- Registered
- 23/05/04
- Location
- Madrid
- Posts
- 140
- iTrader
- 2 (100%)
- Mentioned
- 0 Post(s)
- Reputation
- 0/0
Hoi gasten,
alvast bedankt voor je reacties! Ik moet er wel bij zeggen dat mijn kennis niet ZO groot is.
Ik ga gewoon mijn files uploaden zodat je die kan downloaden. Er zit ook een txt-bestand in met de DB tabellen.
---> RAR-file
Het script bestaat uit verschillende stappen.
1) Selecteren van een type voertuig, om zo verschillende kosten mogelijk te maken. Bijvoorbeeld tussen punt B en C moet je €10 tol betalen met een vrachtwagen. (Er staan 9 velden in de database, 1 per voertuig) (Dankjewel voor de content, Stijn
)
2) Selecteren van de start- en eindlocatie
3) Selecteren van een volgende locatie, ofwel de route bewerken of berekenen.
Een woordje uitleg over de database misschien.
Er zijn 3 tabellen, nl:
Voertuigen: specificaties per voertuig, zuiver indicatief
City: een lijst van de verschillende punten
Road: de verbindingen tussen de punten.
Alle bewerkingen gebeuren op de table 'City'
Momenteel kan je testen door van 'Oostende' naar 'Jabbeke' te gaan.
Dat is de enige actieve route
Die berekening duurt ongeveer 25 á 30 seconden!
Hoe ik te werk ga:
1) Voertuig selecteren (verplicht)
2) Startpunt en eindpunt ingeven en controle op de ingave (zijn er dezelfde postcodes in de database? een soort van auto-aanvullen etc)
Er word ook automatisch een 'record' bijgevoegd met de route terug naar huis.
3)Berekenen en filteren van de route. Bij het filteren van de records begin ik bij de eindlocatie en ga ik zo op zoek naar de startlocatie.
Alle resultaten worden bewaard in een array. Eenmaal de startlocatie werd gevonden, wordt de array uitgelezen.
Het belangrijkste stuk (en het stuk die het meeste tijd in beslag neemt) is de berekening van de route.
De meeste berekeningen staan in het bestand 'functions.php'.
De berekening van de route begint op lijn 170.
Ik hoop dat alles een beetje duidelijk is.
Als je nog iets wilt vragen ofzo, doe gerust.
Ik ben er zo al een beetje blind op gestaard en ik hoop echt dat iemand me kan verderhelpen...
Heel hartelijk bedankt iig!!
Bno votes
-
09-10-2007, 10:10 #8Member
- Registered
- 23/05/04
- Location
- Madrid
- Posts
- 140
- iTrader
- 2 (100%)
- Mentioned
- 0 Post(s)
- Reputation
- 0/0
Het probleem (tijdrovend gedeelte) is zeker deze functie:
Ik zie het bos niet meer door de bomen. Ik denk dat ik me heel even met iets anders bezig hou..Code:function bereken_route($StartCity){ include ('../config/dbconfig.php'); //Fill the table with initial data $sql = "UPDATE City SET Estimate = '2147483647', Predecessor = 'NULL', Done = '0'"; mysql_query($sql); //Set the estimate for the city we start in to be 0. $sql = "UPDATE City SET Estimate = 0 WHERE CityID = '$StartCity'"; mysql_query($sql); //Run the algorithm until we decide that we are finished while(1==1){ //Reset the variable, so we can detect getting no records in the next step. $FromCity = ''; //Select the CityID and current estimate for a city not done, with the lowest estimate. $query = "SELECT CityID, Estimate FROM City WHERE Done = 0 AND Estimate < 2147483647 ORDER BY Estimate LIMIT 1"; $result = mysql_db_query($dbname2, $query); $aanwezig = mysql_num_rows($result); if ($aanwezig != 0){ while($r = mysql_fetch_array($result)){ $FromCity = $r['CityID']; $CurrentEstimate = $r['Estimate']; //We are now done with this city. $sql = "UPDATE City SET Done = 1 WHERE CityID = $FromCity"; mysql_query($sql); //Update the estimates to all neighbour cities of this one (all the cities //there are roads to from this city). Only update the estimate if the new //proposal (to go via the current city) is better (lower). $sql = "UPDATE City INNER JOIN Road ON City.CityID = Road.ToCity SET City.Estimate = $CurrentEstimate + Road.Distance, City.Predecessor = $FromCity WHERE Road.FromCity = $FromCity AND ($CurrentEstimate + Road.Distance) < City.Estimate"; mysql_query($sql); } } else { break; } } }

Als iemand me verder op weg kan helpen.. Heel graag!!
Gr,
Bno votes
-
09-10-2007, 11:33 #9Member
- Registered
- 12/10/02
- Location
- mars
- Posts
- 14,319
- iTrader
- 2 (100%)
- Mentioned
- 0 Post(s)
- Reputation
- 0/0
oh nee nee nee
.
Fout bezig, je gaat NIET tijdelijke tables in mysql aanmaken. Je maakt tijdelijke stacks, tables, whatever in PHP aan, mysql queries zijn immers immense bottlenecks op sites . Als je ze dan nog eens gaat loopen krijg je idd wel immense execute times.
De truc die je echt zééér veel tijd gaat besparen is dus alles binnen de loop in php te doen en daarna 1 of 2 grote update/insert queries uit te voeren
.
Last edited by killgore; 09-10-2007 at 15:04.
no votes
-
09-10-2007, 14:50 #10Member
- Registered
- 23/05/04
- Location
- Madrid
- Posts
- 140
- iTrader
- 2 (100%)
- Mentioned
- 0 Post(s)
- Reputation
- 0/0
Inderdaad killgore,
maar om de route correct te kunnen berekenen moet een record aangepast worden, en adhv die aanpassingen kan de volgende berekend worden...no votes
-
09-10-2007, 15:04 #11Member
- Registered
- 12/10/02
- Location
- mars
- Posts
- 14,319
- iTrader
- 2 (100%)
- Mentioned
- 0 Post(s)
- Reputation
- 0/0
no votes
-
09-10-2007, 15:25 #12Member
- Registered
- 23/05/04
- Location
- Madrid
- Posts
- 140
- iTrader
- 2 (100%)
- Mentioned
- 0 Post(s)
- Reputation
- 0/0
no votes
-
10-10-2007, 00:27 #13Verwarmingselement
- Registered
- 01/07/02
- Location
- Brussel
- Posts
- 3,810
- iTrader
- 14 (100%)
- Mentioned
- 1 Post(s)
- Reputation
- 0/22
Algemene opmerkingen :
- mysql_db_query() vervangen door mysql_query() waardoor ook de nutteloze includes van dbconfig doorheen uw functions.php wegkunnen, die zullen overigens telkens een nieuwe mysql connectie opzetten, bad performance

- gebruik de superglobals correct, $_GET, $_POST en $_SESSION, uw manier van werken is prehistorisch

- Cost1, Cost2 etc. in uw DB is een big no no, hiervoor maak je een aparte tabel waarbij je elke cost linkt naar een road
En dan was ik begonnen aan de oplossing, om net te beseffen dat je telkens diepere arrays moet maken om te voorkomen dat je oneindig blijft doorzoeken of markeren dat een pad al berekend is ofzoiets. Zal mijn code er bij zetten, misschien is iemand er nog iets mee om aan de oplossing te beginnen
PHP Code:function fromInPath($path, $from, $nextHop)
{
if($path['from'] == $from && $path['from'] != $nextHop)
{
return 0;
}
return 1;
}
////////////////////////////////////////BEREKENEN ROUTE & OPSLAAN IN DB
function berekenRoute($startCity)
{
//beginnen bij startlocatie
$destinations[$row['CityID']] = array(
'cost' => 0, // destination unreachable waarde
'nextHop' => 0
);
// alle paden ophalen
$paths = array();
$query = "SELECT Id, FromCity, ToCity, Distance FROM road";
$result = mysql_query($query);
while ($row = mysql_fetch_assoc($result))
{
$path = array(
'from' => $result['FromCity'],
'to' => $result['ToCity'],
'distance' => $result['Distance']
);
$paths[] = $path;
$path = array(
'from' => $result['ToCity'],
'to' => $result['FromCity'],
'distance' => $result['Distance']
);
$paths[] = $path;
}
// mogelijke paden berekenen naar alle volgende hops
$nextPaths = array();
foreach($destinations as $destination => $properties)
{
$nextPaths[] = array_uintersect($paths, $destination, $properties['nextHop'], "fromInPath");
}
//enkel goedkoopste paden houden
/* verwijder paden uit nextPaths die duurder zijn dan andere paden naar dezelfde hop */
}
no votes
-
10-10-2007, 14:04 #14Member
- Registered
- 23/05/04
- Location
- Madrid
- Posts
- 140
- iTrader
- 2 (100%)
- Mentioned
- 0 Post(s)
- Reputation
- 0/0
Dus eigenlijk zijn we op zoek naar een systeem die de aangepaste waardes onthoud (en er dan ook rekening mee houdt) zonder ze te moeten schrijven naar de database?
no votes
-
10-10-2007, 15:02 #15Verwarmingselement
- Registered
- 01/07/02
- Location
- Brussel
- Posts
- 3,810
- iTrader
- 14 (100%)
- Mentioned
- 1 Post(s)
- Reputation
- 0/22
Yep, je wil eenmalig alle nodige data uit de DB halen en dan alle berekeningen in PHP uitvoeren bij het opvragen van een route.
Als dit nu echt een "kritische" applicatie is die super regelmatig gebruikt wordt maar zelden veranderd, dan zou je er voor kunnen opteren om bij een wijziging aan een road of bestemming de routing te berekenen. En je kan dan bv. het resultaat (een serieuze array) als platte tekst in uw tabel met steden opslaan zodat je ze niet telkens moet herberekenen als ze opgevraagd worden. Maar da's dan EEN insert/update, geen 300 zoals uw code doet.no votes

