Trouver le plus court chemin dans un graphe dont les visites de certains noeuds
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)
Vous devez vous connecter pour publier un commentaire.
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 tous les sommets (un cycle Hamiltonien) -- il correspond à avoir 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:
(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(n3) pour le 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.]
a
àc
parb
. Il se peut que les chemins les plus courts deb
àa
etc
partagent une arête. Dans ce cas, le bord devrait être répété deux fois. L'un des deux chemins aurait besoin d'être pire que l'optimum afin de ne pas générer des cycles.exécuter L'Algorithme de Djikstra pour trouver les plus courts chemins entre tous les nœuds critiques (début, fin, et qui doit passer), puis en profondeur d'abord la traversée devrait vous indiquer le chemin le plus court grâce à la naissance de sous-graphe qui touche tous les noeuds de commencer ... mustpasses ... fin
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.
Seulement 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.
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.
Andrew Haut a la bonne idée:
1) l'Algorithme de Djikstra
2) Quelques c. à thé heuristique.
Je recommande le Lin-Kernighan heuristique: c'est l'un des meilleurs de tous les NP problème Complet. La seule autre chose à retenir est que après avoir élargi le graphe de nouveau après l'étape 2, vous pouvez avoir des boucles dans votre chemin d'accès étendu, de sorte que vous devrait aller autour de court-circuit (de regarder le degré des sommets le long de votre chemin).
Je ne suis vraiment pas sûr de savoir comment bien cette solution par rapport à l'optimum. Il y a probablement quelques cas pathologiques à voir avec le court-circuit. Après tout, ce problème ressemble BEAUCOUP à Steiner Tree: http://en.wikipedia.org/wiki/Steiner_tree et vous avez certainement ne pouvez pas approximative Steiner Arbre juste en contractant votre graphique et l'exécution de Kruskal par exemple.
C'est pas une c. à thé de problème et pas de problème NP-difficile, car la question d'origine n'exige pas que qui doit passer les nœuds sont visité qu'une seule fois. Cela rend la réponse beaucoup, beaucoup plus simple pour la force brute après avoir compilé une liste des plus courts chemins entre tous doit passer nœuds via l'algorithme de Dijkstra. Il peut y avoir une meilleure façon d'aller, mais un simple serait tout simplement de travailler un arbre binaire vers l'arrière. Imaginez une liste de nœuds [start,a,b,c,fin]. Somme de la simple distance [démarrer->a->b->c->fin] c'est votre nouvelle cible à distance à battre. Maintenant, essayez [démarrer->a->c->b->end] et si c'est mieux d'en faire la cible (et rappelez-vous qu'il est venu à partir de ce schéma de nœuds). Travail vers l'arrière sur les permutations:
L'un de ceux qui vont être les plus courts.
(où sont les "visité plusieurs fois "nœuds", le cas échéant? Ils sont juste cachés dans le chemin le plus court étape d'initialisation. Le chemin le plus court entre a et b peut contenir c ou même le point de fin. Vous n'avez pas besoin de soins)
Compte tenu de la quantité de nœuds et d'arêtes est relativement limité, vous pouvez probablement calculer chaque chemin possible et de prendre le plus court.
Généralement connu comme le problème du voyageur de commerce, et a un non-déterministe polynomial d'exécution, quelle que soit l'algorithme que vous utilisez.
http://en.wikipedia.org/wiki/Traveling_salesman_problem
Comment sur l'utilisation de la force brute sur la douzaine de "doit visiter "nœuds". Vous pouvez couvrir toutes les combinaisons possibles de 12 nœuds assez facilement, et cela vous laisse avec une optimale circuit que vous pouvez suivre pour les couvrir.
Maintenant, votre problème est simplifié afin de trouver des routes optimales à partir du nœud de départ pour le circuit, ce qui permet ensuite de suivre jusqu'à ce que vous avons couverts, et ensuite trouver la route à partir de ce à la fin.
Chemin Final est composé de :
démarrer -> chemin d'accès au circuit* -> circuit de visite incontournable de nœuds -> chemin d'accès à la fin* -> fin
Vous trouver les chemins que j'ai marqué avec * comme ce
Faire Un* recherche à partir du nœud de départ de chaque point sur le circuit
pour chacun de ces ne un Un* recherche à partir de la prochaine et nœud précédent sur le circuit à la fin (parce que vous pouvez suivre le circuit de ronde dans les deux sens)
Ce que vous finissez avec est un mal de chemins de recherche, et vous pouvez choisir celui avec le plus bas coût.
Il y a beaucoup de place pour l'optimisation en cache les recherches, mais je pense que cela va générer de bonnes solutions.
Il n'est pas aller n'importe où près de la recherche d'une solution optimale si, parce que cela pourrait impliquer de quitter la visite incontournable du circuit à l'intérieur de la recherche.
Une chose qui n'est mentionné nulle part, est de savoir si c'est ok pour le même sommet, à être visité plus d'une fois dans le chemin d'accès. La plupart des réponses ici suppose que c'est ok pour visiter le bord même plusieurs fois, mais de mon point de vue la question étant de savoir (un chemin d'accès ne devraient pas visiter le même sommet, plus d'une fois!) c'est qu'il est pas ok pour visiter deux fois le même sommet.
Donc une approche par force brute continuerait de s'appliquer, mais vous seriez obligé de supprimer les sommets déjà utilisé lorsque vous essayez de calculer, pour chaque sous-ensemble de la trajectoire.