1. Accueil
  2. Question et réponse
  3. Chemin total le plus court parmi l'ensemble des Latitude/Longitudes

Chemin total le plus court parmi l'ensemble des Latitude/Longitudes

2009-11-01 2 views
2

J'ai un ensemble de 52 paires de latitude/longitude. J'ai simplement besoin de trouver le chemin le plus court à travers chacun d'eux; Peu importe où est le point de départ ou le point de fin.Chemin total le plus court parmi l'ensemble des Latitude/Longitudes

J'ai implémenté l'algorithme de Dijkstra à la main plusieurs fois auparavant et je n'ai pas vraiment le temps de le refaire. J'ai trouvé quelques choses qui se rapprochent, mais la plupart exigent des graphiques bruts avec des poids pré-calculés pour chaque arête. Connaissez-vous des bibliothèques ou des scripts/applications existants qui calculeront le chemin le plus court de cette manière? Le code/les bibliothèques utiliseraient de préférence Python ou Clojure, mais cela n'a pas vraiment d'importance.

Merci

Source

2009-11-01 Brian Gianforcaro

Répondre

3

Si c'est un chemin fermé, il est le voyageur de problème, et d'une manière sous-optimale, mais très efficace pour le résoudre est d'utiliser Simulated Annealing

Source

2009-11-01 02:12:35 Mathias

+1

TSP ne nécessite pas de chemin fermé. Sans chemin fermé, le problème est le même, seule la mesure de la longueur totale du chemin est différente. Sur un chemin fermé, le meilleur chemin est celui où la somme de tous les bords est minimale. Si le chemin ne doit pas se fermer, c'est la somme de tous les bords - le plus long bord –

+0

@ THC4k Je sais que ce n'était pas du tout la question, mais ce commentaire m'a permis de terminer mon code de la manière la plus simple . J'avais déjà résolu TSP avec le chemin fermé. Merci! –

0

est-ce pas le Traveling Salesman Problem, et donc il n'y a pas moyen efficace de résoudre?

Source

2009-11-01 02:08:19

+0

C'est le TSP sans la stipulation de terminer où vous avez commencé, donc vous devriez en théorie obtenir une distance totale beaucoup plus courte. –

+0

Pish! TSP est O (n!) N'est-ce pas? Il n'a que 52 paires = quelque chose comme 8.07e + 67 possibilités, non? : p – mpen

+4

Pas de moyen efficace pour trouver la solution _optimal_ peut-être ... mais il y a des solutions _fairly good_. –

2

En python, la meilleure bibliothèque de gestion graphique j'ai pu mettre mes mains sur est networkx. Il prend en charge une large gamme d'algos différents pour short path search.

Allez-y. C'est vraiment complet et bien conçu.

Source

2009-11-01 07:43:09

Questions connexes

 Questions connexes