Trouver le chemin le plus court dans un graphe qui visite certains nœuds

Question

J'ai un graphe non-dirigé, avec environ 100 nœuds et environ 200 bords. Un nœud est étiqueté "start", on est "fin", et il y a environ une douzaine de étiquetés "mustpass'.

J'ai besoin de trouver le chemin le plus court à travers ce graphique qui commence à "démarrer", se termine à la fin, et passe à travers tous les mustpass "nœuds" (dans n'importe quel ordre).

( http://3e.org/local/maize-graph.png / http://3e.org/local/maize-graph.dot.txt est le graphe en question - il s'agit d'un labyrinthe de maïs à Lancaster, PA)

Answer 1

Tout le monde la comparant au Problème du voyageur de commerce n'a probablement pas lu votre question attentivement. Dans TSP, l'objectif est de trouver le plus court cycle de visites de tous les sommets (un cycle Hamiltonien) -- il correspond à l'avoir de chaque nœud étiqueté "mustpass'.

Dans votre cas, étant donné que vous avez seulement une douzaine portant la mention "mustpass', et étant donné que 12! est plutôt de petite taille (479001600), vous pouvez simplement essayer de toutes les permutations de la 'mustpass " nœuds", et de regarder le chemin le plus court à partir de "start" à " fin "que les visites de la "mustpass" nœuds " dans l'ordre -- il sera simplement la concaténation des plus courts chemins entre deux nœuds consécutifs dans la liste.

En d'autres termes, tout d'abord trouver la distance la plus courte entre chaque paire de sommets (vous pouvez utiliser l'algorithme de Dijkstra ou autres, mais avec ces petits nombres (100 nœuds), même la plus simple-à-code de Floyd-Warshall algorithme sera exécuté dans le temps). Ensuite, une fois que vous avez cela dans un tableau, essayez toutes les permutations de votre "mustpass " nœuds", et le reste.

Quelque chose comme ceci:

//Precomputation: Find all pairs shortest paths, e.g. using Floyd-Warshall
n = number of nodes
for i=1 to n: for j=1 to n: d[i][j]=INF
for k=1 to n:
    for i=1 to n:
        for j=1 to n:
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])
//That *really* gives the shortest distance between every pair of nodes! :-)

//Now try all permutations
shortest = INF
for each permutation a[1],a[2],...a[k] of the 'mustpass' nodes:
    shortest = min(shortest, d['start'][a[1]]+d[a[1]][a[2]]+...+d[a[k]]['end'])
print shortest

(Bien sûr, ce n'est pas vrai code, et si vous voulez le chemin que vous aurez à garder une trace de la permutation donne la distance la plus courte, et aussi ce que toutes les paires de chemins les plus courts sont, mais vous voyez l'idée).

Il sera exécuté en quelques secondes sur n'importe quel raisonnable de la langue :)
[Si vous avez n nœuds et k 'mustpass " nœuds", son temps d'exécution est O(n³) pour la Floyd-Warshall partie, et O(k!n) pour l'ensemble des permutations de la partie, et 100^3+(12!)(100) est pratiquement arachides, sauf si vous avez vraiment des contraintes restrictives.]

Answer 2

lancez l'algorithme de Djikstra pour trouver les chemins les plus courts entre tous les noeuds critiques (début, fin, et doit-passer), puis une traversée en profondeur en premier devrait vous indiquer le chemin le plus court passant par le sous-graphe résultant et touchant tous les noeuds. doit passer ... fin

Answer 3

C'est deux problèmes... Steven Lowe a souligné, mais ne lui donne pas assez de respect pour la seconde moitié du problème.

Vous devez d'abord découvrir les chemins les plus courts entre tous vos nœuds critiques (début, fin, mustpass). Une fois ces chemins sont découverts, vous pouvez construire un graphique simplifié, où chaque arête dans le nouveau graphe est un chemin d'accès à partir d'un nœud à un autre dans le graphique d'origine. Il y a beaucoup de pathfinding des algorithmes que vous pouvez utiliser pour trouver le chemin le plus court ici.

Une fois que vous avez ce nouveau graphe, même si, vous avez exactement les Voyages Vendeur problème (enfin, presque... Pas besoin de retourner à votre point de départ). L'un des postes à ce sujet, mentionné ci-dessus, seront applicables.

Answer 4

En fait, le problème que vous avez posté est similaire pour le voyageur de commerce, mais je pense de plus pour un simple problème de pathfinding. Plutôt que d'avoir besoin de visiter chaque et chaque noeud, il vous suffit de visiter un ensemble de nœuds dans le temps le plus court (distance) possible.

La raison pour cela est que, contrairement au problème du voyageur de commerce, un labyrinthe de maïs ne vous permettra pas de voyager directement à partir d'un point quelconque avec un autre point sur la carte sans avoir besoin de passer par d'autres nœuds pour y arriver.

En fait, je peux vous recommander Un* pathfinding comme une technique à prendre en compte. Ce faire, vous devez en décidant dont les nœuds ont accès à qui les autres nœuds directement, et ce que le "coût" de chaque saut à partir d'un nœud particulier est. Dans ce cas, il ressemble à chaque "hop" pourrait être de l'égalité de coût, puisque les nœuds semblent relativement rapprochées. Un* peuvent utiliser cette information pour trouver le plus bas coût de chemin entre deux points. Puisque vous avez besoin pour vous rendre du point A au point B et visite d'environ 12 inbetween, même une approche par force brute à l'aide de pathfinding ne ferait pas de mal à tous.

Juste une alternative à considérer. Il n'a pas l'air remarquablement comme le problème du voyageur de commerce, et ce sont de bons papiers à lire, mais à y regarder de plus près et vous verrez que son seul de compliquer à l'excès des choses. ^_^ Cette venue de l'esprit d'un jeu vidéo programmeur qui a traité ces sortes de choses avant.

Answer 5

La peu enviable du voyageur de commerce un ensemble de problèmes devrait ouvrir vos yeux.

Extrait:

La solution la plus directe serait de essayez toutes les permutations (commandé combinaisons) et de voir que l'on est moins cher (en utilisant la force brute de la recherche), mais étant donné que le nombre de permutations est n! (la factorielle de le nombre de villes, n), ce la solution devient rapidement impraticable. En utilisant les techniques de dynamique la programmation, on peut résoudre le problème en temps O(n^2 * 2^n)[4]. Bien que ce soit exponentielle, il est encore beaucoup mieux que O(n!).

D'autres approches consistent à:

• Divers branch-and-bound algorithmes, qui peut être utilisé pour traiter les Fst contenant de 40 à 60 villes.
• L'amélioration Progressive des algorithmes qui utilisent des techniques qui rappelle de programmation linéaire. Fonctionne bien pour les 200 villes.
• Les implémentations de branch-and-bound et spécifiques au problème de coupe de la génération; c'est la méthode de choix pour résoudre les grandes instances. Cette approche détient le record actuel, la résolution d'une instance avec 85,900 villes.