I t ex Google maps. När förslag på färdväg mellan punkt A och B beräknas, hur sker detta? Jag menar, antalet möjliga vägar (utan att köra samma gata två gånger) är ju ofantligt många. Testar den sig fram eller beräknas rätt rutt på första försöket? Hur sker detta i så fall?
Algortimerna i ruttoptimeringsprogram är mycket komplexa och får nog beteckans som "hemliga". Men ja det handlar om att testa olika lösningar, jämföra dessa och välja ut den som passar de uppsatta prametrarna (ej betalvägar/kortast tid/kortast sträcka...)
För det mesta använder man grafteori. Det är vanligt - men inte nödvändigt, det finns alternativa metoder - att GIS-data är modellerat som grafer, t ex framgår detta av namnet på den vanliga kommersiella produkten ArcGis.
Innebär detta att den faktiskt testar 100 000-tals vägar under den lilla tid den laddar? Eller skalar den bort vägar som ligger för långt utanför fågelvägen?
Den som ar intresserad kan titta pa kallkoden till det optimeringsbibliotek som anvands av Google: http://code.google.com/p/or-tools/
Det innehaller inga fardiga exempel pa att hitta vagar i kartor, men grafalgoritmerna finns dar.
Har för mig jag läste om något företag försökte utveckla något liknande för sjöfart. Dvs ange vart du vill, så lägger plottern ut rutten själv. Har inte hört något på länge. Någon som vet om de lyckats få till detta? Lite mer komplext än bil-rutter :-)
Och i GPS:er för vägfordon kan man ändra viktningen på bågarna i grafen från uppmätta körtider under färd, så att GPS:en "tränas upp".
Mer bestämt så används antagligen den mycket snygga utvidningen A* (eller, eftersom Google är skrämmande, så har de utvecklat någon ofattbar metod som är betydligt snabbare).
