Page 1 of 2 12 Last
  1. #1
    [E.I]Magic's Avatar
    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  

  2. #2

    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  

  3. #3
    [E.I]Magic's Avatar
    Registered
    23/05/04
    Location
    Madrid
    Posts
    140
    iTrader
    2 (100%)
    Mentioned
    0 Post(s)
    Reputation
    0/0
    Quote Originally Posted by killgore View Post
    This quote is hidden because you are ignoring this member. Show
    edit: en mssch is jouw dijkstra implementatie ook gewoon vrij traag .
    Kan heel goed zijn

    Waar vind ik wat meer info rond dat algoritme?

    Gr
    no votes  

  4. #4

    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  

  5. #5
    Radiance's Avatar
    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  

  6. #6

    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  

  7. #7
    [E.I]Magic's Avatar
    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!!

    B
    no votes  

  8. #8
    [E.I]Magic's Avatar
    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:

    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;	
    		}
    	}
    }
    Ik zie het bos niet meer door de bomen. Ik denk dat ik me heel even met iets anders bezig hou..

    Als iemand me verder op weg kan helpen.. Heel graag!!

    Gr,
    B
    no votes  

  9. #9

    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  

  10. #10
    [E.I]Magic's Avatar
    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  

  11. #11

    Registered
    12/10/02
    Location
    mars
    Posts
    14,319
    iTrader
    2 (100%)
    Mentioned
    0 Post(s)
    Reputation
    0/0
    Quote Originally Posted by [E.I]Magic View Post
    This quote is hidden because you are ignoring this member. Show
    Inderdaad killgore,
    maar om de route correct te kunnen berekenen moet een record aangepast worden, en adhv die aanpassingen kan de volgende berekend worden...
    kzal vanavond of morgen eens naar de code kijken, normaal moet je het niet-mysql gerelateerd kunnen hoor.
    no votes  

  12. #12
    [E.I]Magic's Avatar
    Registered
    23/05/04
    Location
    Madrid
    Posts
    140
    iTrader
    2 (100%)
    Mentioned
    0 Post(s)
    Reputation
    0/0
    Quote Originally Posted by killgore View Post
    This quote is hidden because you are ignoring this member. Show
    kzal vanavond of morgen eens naar de code kijken, normaal moet je het niet-mysql gerelateerd kunnen hoor.
    Dat zou heel fijn zijn

    In ieder geval al bedankt voor je tijd!!

    Gr
    no votes  

  13. #13
    Radiance's Avatar
    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  

  14. #14
    [E.I]Magic's Avatar
    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  

  15. #15
    Radiance's Avatar
    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  

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  

Log in

Log in