Harta de rutare, un Hărți la Google?

voturi
19

Am fost mereu intrigat de Harta de rutare, dar nu am găsit nici o introducere bună (sau chiar avansat!), Nivel tutoriale pe ea. Are cineva orice indicii, sugestii, etc?

Actualizați: Sunt în primul rând în căutarea pentru indicii cu privire la modul în care este implementat un sistem de hartă (structuri de date, algoritmi, etc).

Întrebat 05/08/2008 la 21:24
sursa de către utilizator
În alte limbi...                            


9 răspunsuri

voturi
14

Aruncati o privire la proiect deschis harta din stradă pentru a vedea modul în care acest tip de lucru este abordată într - un proiect software gratuit , folosind numai cu adevărat de utilizator furnizat și licențiat de date și au un wiki care conține lucruri pe care le - ar putea găsi interesant .

Acum câțiva ani băieții implicați în cazul în care merge destul de ușor și a răspuns la o mulțime de întrebări am avut asa ca nu vad nici un motiv pentru care încă nu sunt un buchet frumos.

Publicat 05/08/2008 la 21:27
sursa de către utilizator

voturi
4

A * este de fapt mult mai aproape de algoritmi de mapare de producție. Este nevoie de destul de un pic mai puțin de explorare în comparație cu algoritmul inițial Dijikstra lui.

Publicat 25/09/2008 la 00:19
sursa de către utilizator

voturi
4

Barry Brumitt, unul dintre inginerii de la Google Maps caracteristica constatare traseu, a scris un post pe tema care ar putea fi de interes:

Drumul spre o mai bună cale de a găsi 11/06/2007 15:47:00

Publicat 17/09/2008 la 09:44
sursa de către utilizator

voturi
4

Prin Harta de rutare, vrei să spui găsirea calea cea mai scurtă de-a lungul unei rețele de stradă?

Dijkstra Algoritmul cel mai scurt-cale este cel mai cunoscut. Wikipedia nu are un intro rău: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Există un applet Java aici , unde puteți vedea în acțiune: http://www.dgp.toronto.edu/people/JamesStewart/270/9798s/Laffra/DijkstraApplet.html și Google vă vă duce la codul sursă , în doar despre orice limba.

Orice implementare reală pentru a genera rute de conducere va include destul de un pic de date cu privire la rețeaua stradală care descrie costurile asociate cu link-urile care traversează și ierarhia rețelei de noduri de teren, viteza medie, prioritate intersecție, care leagă semnal de trafic, se transformă interzise etc.

Publicat 15/08/2008 la 05:31
sursa de către utilizator

voturi
2

Din punct de vedere conceptual, imagina cădere o piatră într-un iaz și vizionarea valuri. Traseele ar reprezenta iaz și piatră poziția de pornire.

Desigur, algoritmul ar trebui să caute o anumită proporție de n ^ 2 căi ca distanța n crește. Tu te-ar lua poziția de pornire și verificați toate căile disponibile din acel punct. Apoi suna recursiv pentru punctele de la sfârșitul acestor căi și așa mai departe.

Puteți crește performanța, prin faptul că nu dublu-suport pe o cale, prin faptul că nu reverificarea rutele într-un punct în cazul în care a fost deja acoperite și prin renunțarea pe căi care durează prea mult.

O modalitate alternativă este de a utiliza abordarea feromon furnică, în cazul în care furnicile se târască la întâmplare dintr-un punct de pornire și se lasă o urmă miros, care se acumulează mai multe furnici trec peste un drum dat. Dacă trimiteți (suficient) furnicile atât punctul de pornire și punctele de capăt, apoi în cele din urmă calea cu cel mai puternic mirosul va fi cel mai scurt. Acest lucru se datorează faptului că cea mai scurtă cale va fi vizitat de mai multe ori într-o anumită perioadă de timp, având în vedere că furnicile mers pe jos într-un ritm uniform.

EDIT @ Spikie

Ca o explicație a modului de punere în aplicare a algoritmului iaz - potențiale structuri de date necesare sunt evidențiate:

Veți avea nevoie pentru a stoca harta ca o rețea. Acest lucru este pur și simplu un set de nodesși edgesîntre ele. Un set de nodesconstituie route. O margine unește două noduri (eventual ambele același nod), și are un asociat , costcum ar fi distancesau de timea traversa margine. O margine poate fi fie fie bidirecțională sau uni-direcțională. Probabil mai simplu de a avea doar cele uni-direcționale și dubla pentru două sensuri între nodurile de deplasare ( de exemplu , o margine de la A la B și unul diferit pentru B la A).

Cu titlu de exemplu, imaginați-vă trei stații de cale ferată, aranjate într-un triunghi echilateral îndreptat în sus. Există, de asemenea, alte trei stații fiecare la jumătatea distanței dintre ele. Marginile se alăture toate stațiile adiacente împreună, diagrama finală va avea un triunghi inversat așezat în interiorul triunghiului mai mare.

noduri de etichete pornind de la stânga jos, merge la stânga la dreapta și în sus, ca A, B, C, D, E, F (F la partea de sus).

Să presupunem marginile pot fi traversate în orice direcție. Fiecare muchie are un cost de 1 km.

Ok, deci dorim să ruta din stânga jos de la A la stația de sus F. Există mai multe căi posibile, inclusiv cele care se dubleze din nou pe ei înșiși, de exemplu, ABCEBDEF.

Avem un cuvânt de spus de rutină, NextNodecă acceptă o nodeși costi se solicită pentru fiecare nod poate călători.

În mod clar dacă vom lăsa acest lucru rula rutina va descoperi acest lucru în cele din urmă toate rutele, inclusiv cele care sunt potențial infinit în lungime ( de exemplu , ABABABAB , etc). Ne oprim aceasta prin verificarea împotriva cost. Ori de câte ori vom vizita un nod care nu a fost vizitat niciodată, am pus atât costul și nodul am venit împotriva acel nod. În cazul în care un nod a fost vizitat înainte de a verifica împotriva costurilor existente și dacă suntem mai ieftin , atunci vom actualiza nodul și continuați (recursiune). Dacă suntem mai scumpe, atunci vom sări peste nodul. În cazul în care toate nodurile sunt ignorate , atunci vom ieși din rutina.

Dacă ne-am lovit nodul țintă, atunci vom ieși din rutina de asemenea.

În acest fel toate rutele viabile sunt verificate, dar crucial numai cele cu cel mai mic cost. Până la sfârșitul procesului de fiecare nod va avea cel mai mic cost pentru a ajunge la acel nod, inclusiv nodul țintă.

Pentru a obține traseul lucrăm înapoi de la nodul țintă. Din moment ce am memorat nodul am venit de-a lungul cu costul, trebuie doar să ne hop înapoi construirea traseului. De exemplu, ne vom termina cu ceva de genul:

Nod A - (Total) Cost 0 - De la Nod Nici unul
Nod B - Cost 1 - De la nodul A
Nod C - Cost 2 - De la Nod B
Nod D - Cost 1 - De la nodul A
Nod E - Cost 2 - De la Nod D / cost 2 - de la Nod B (aceasta este o excepție , deoarece există costuri egale)
Nod F - Cost 2 - de la Nodul D

Deci, cel mai scurt traseu este ADF.

Publicat 26/09/2008 la 15:05
sursa de către utilizator

voturi
2

Am încă pentru a găsi un bun tutorial pe rutare, dar există o mulțime de cod pentru a citi:

Există aplicații de rutare GPL care utilizează date OpenStreetMap, de exemplu , Gosmore care funcționează pe Windows (+ mobil) și Linux. Există o serie de interesante [aplicații folosind aceleași date, dar Gosmore are unele misto foloseste de exemplu de interfață cu site - uri web .

Cea mai mare problemă cu rutare este rău de date, și niciodată nu obține date suficient de bune. Deci, dacă doriți să încercați să-l păstrați testul foarte local, astfel încât să puteți controla mai bine datele.

Publicat 17/09/2008 la 09:34
sursa de către utilizator

voturi
2

În loc de API - uri de învățare pentru fiecare furnizor de servicii hartă (cum ar fi Gmaps, Ymaps api) bun pentru a învăța sa Mapstraction

„Mapstraction este o bibliotecă care oferă o interfață comună pentru diverse API-uri de cartografiere JavaScript“

Aș sugera să mergeți la URL-ul și să învețe un API generală. Există o cantitate bună de Cum-tos prea.

Publicat 06/08/2008 la 14:35
sursa de către utilizator

voturi
1

Din experienta mea de a lucra în acest domeniu, A * face treaba foarte bine. Este (așa cum sa menționat mai sus) mai repede decât algoritmul lui Dijkstra, dar este încă destul de simplu pentru un programator obișnuit competent să pună în aplicare și să înțeleagă.

Construirea rețelei de rute este cea mai grea parte, dar care pot fi defalcate într-o serie de pași simpli: obține toate drumurile; sorta punctele în ordine; face grupuri de puncte identice pe drumuri diferite în intersecții (noduri); se adaugă arce în ambele direcții, în cazul în care nodurile se conectează (sau într-o singură direcție pentru un drum cu sens unic).

Algoritmul A * în sine este bine documentat pe Wikipedia . Locul cheie pentru a optimiza este selectarea cel mai bun nod din lista deschisă, pentru care aveți nevoie de o coadă de prioritate de înaltă performanță. Dacă utilizați C ++ puteți utiliza adaptorul STL priority_queue.

Personalizarea algoritmului de a rutei peste diferite părți ale rețelei (de exemplu, pietonal, auto, transport public, etc.) de viteză favoare, distanța sau alte criterii este destul de ușor. Puteți face acest lucru prin scris filtre pentru a controla sunt disponibile segmente de rută, atunci când construirea rețelei, și care greutatea este atribuit fiecăruia.

Publicat 15/07/2012 la 22:13
sursa de către utilizator

voturi
1

Un alt gând are loc pentru mine în ceea ce privește costul fiecărui parcurgeri, dar ar crește timpul și puterea de procesare necesară pentru a calcula.

Exemplu: Există 3 moduri pot lua (unde locuiesc) pentru a merge de la punctul A la B, în conformitate cu GoogleMaps. Unități Garmin oferă fiecare dintre aceste 3 căi în Quickestcalcularea traseului. După traversarea fiecare dintre aceste rute de multe ori și o medie (evident , vor exista erori în funcție de momentul zilei, cantitatea de cofeina , etc), mă simt algoritmii ar putea lua în considerare numărul de coturi în drum pentru nivelul ridicat de precizie , de exemplu , drum drept de 1 mile va fi mai rapid decât un drum 1 mile cu curbe ascuțite în ea . Nu este o sugestie practică , dar cu siguranță o folosesc pentru a îmbunătăți rezultatul set de naveta mea de zi cu zi.

Publicat 18/09/2011 la 22:34
sursa de către utilizator

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more