TSP (problema del commesso viaggiatore) solver Utilizzo di Google Map

Question

Si stanno sviluppando un'applicazione, in cui mostreremo alcune case disponibili per la vendita in Google Map. L'utente può selezionare qualsiasi case dalla mappa e riesce a trovare il percorso di guida più breve tra tutte le case che lui / lei selezionato.

Può qualunque prego dirmi come possiamo trovare il percorso più breve e in grado di dimostrare che sulla mappa? C'è qualche PHP basato biblioteca TSP, che ci può aiutare a raggiungere quello che stiamo cercando?

Answer 1

Un ricerca di Google mostra molti risultati.

• http://scrivna.com/blog/travelling-salesman-problem/ - implementazione bruta forza PHP garantito per ottenere la risposta ottimale. Adatto solo per un numero limitato di nodi.

• http://www.renownedmedia.com/ implementazione genetica algoritmo di PHP che si avvicinerà la risposta - / blog / genetica-algoritmo-viaggiare-venditore-php. Adatto per un gran numero di nodi.

Si potrebbe probabilmente combinare le due cose, la scelta di cui eseguire in base alle dimensioni del grafico.

Come @Barbar sottolinea nei commenti, v'è un esistente app che fa quello che si' ri di tentare. C'è un post sul blog che spiega href="http://gebweb.net/blogpost/2007/07/05/behind-the-scenes-of-optimap/" come funziona .

Answer 2

Il suo vecchio ma può essere utile per le persone: https://developers.google.com/maps/documentation/javascript/v2 / servizi # RoutesAndSteps

basta creare waypoints per ogni casa e lasciare che Google fare i calcoli per te ...

Answer 3

Se il problema di soddisfare la disuguaglianza triangolare si può provare l'algoritmo Christofides.