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

J’ai un graphique non dirigé avec environ 100 nœuds et environ 200 arêtes. Un nœud est étiqueté «start», l’un est «end» et une douzaine d’entre eux sont étiquetés «mustpass».

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

( http://3e.org/local/maize-graph.png / http://3e.org/local/maize-graph.dot.txt est le graphique en question – il représente un labyrinthe de maïs à Lancaster, PA)

Tout le monde comparant cela au problème du voyageur voyageur n’a probablement pas lu votre question avec attention. Dans TSP, l’objective est de trouver le cycle le plus court qui visite tous les sumts (un cycle hamiltonien) – cela correspond à avoir chaque nœud étiqueté «mustpass».

Dans votre cas, étant donné que vous n’avez qu’une douzaine d’étiquettes étiquetées «mustpass», et que 12! est assez petit (479001600), vous pouvez simplement essayer toutes les permutations des seuls nœuds ‘mustpass’ et regarder le plus court chemin de ‘start’ à ‘end’ qui visite les nœuds ‘mustpass’ dans cet ordre être la concaténation des chemins les plus courts entre deux nœuds consécutifs dans cette liste.

En d’autres termes, trouvez d’abord la distance la plus courte entre chaque paire de sumts (vous pouvez utiliser l’algorithme de Dijkstra ou d’autres, mais avec ces petits nombres (100 nœuds), même l’ algorithme Floyd-Warshall le plus simple sera exécuté). Ensuite, une fois que vous avez cela dans une table, essayez toutes les permutations de vos nœuds “mustpass”, et le rest.

Quelque chose comme ça:

//Precomputation: Find all pairs shortest paths, eg 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 du vrai code, et si vous voulez le chemin réel, vous devrez garder une trace de la permutation qui donne la distance la plus courte, et aussi ce que sont les chemins les plus courts, mais vous avez l’idée.)

Il fonctionnera au plus quelques secondes sur n’importe quel langage raisonnable 🙂
[Si vous avez n nœuds et k nœuds ‘mustpass’, son temps d’exécution est O (n 3 ) pour la partie Floyd-Warshall, et O (k! N) pour la partie toutes permutations, et 100 ^ 3 + (12! ) (100) est pratiquement une cacahuète sauf si vous avez des contraintes vraiment ressortingctives.]

Exécutez l’algorithme de Djikstra pour trouver les chemins les plus courts entre tous les nœuds critiques (start, end et must-pass), puis un parcours en profondeur devrait vous indiquer le chemin le plus court dans le sous-graphe résultant qui touche tous les nœuds. . mustpasses … fin

En fait, le problème que vous avez posté est similaire à celui du voyageur de commerce, mais je pense à un problème de cheminement simple. Plutôt que de devoir visiter chaque nœud, il vous suffit de visiter un ensemble de nœuds particulier dans les plus brefs délais (distances).

La raison en est que, contrairement au problème des vendeurs itinérants, un labyrinthe de maïs ne vous permettra pas de voyager directement d’un point à un autre sur la carte sans avoir à passer par d’autres nœuds pour vous y rendre.

Je recommanderais réellement A * pathfinding comme technique à considérer. Vous définissez cela en décidant quels nœuds ont directement access aux autres nœuds, et quel est le “coût” de chaque saut d’un nœud particulier. Dans ce cas, il semble que chaque “saut” pourrait avoir le même coût, car vos nœuds semblent relativement espacés. Un * peut utiliser cette information pour trouver le chemin le moins cher entre deux points. Puisque vous devez aller d’un point A à un point B et visiter environ 12 entre deux, même une approche en force brute utilisant le pathfinding ne ferait pas de mal du tout.

Juste une alternative à considérer. Il ressemble remarquablement au problème des vendeurs itinérants, et ce sont de bons documents à lire, mais regardez de plus près et vous verrez que ce n’est que des choses compliquées. ^ _ ^ Cela vient de l’esprit d’un programmeur de jeux vidéo qui a déjà eu affaire à ce genre de choses.

Ceci est deux problèmes … Steven Lowe l’a souligné, mais n’a pas accordé assez de respect à la seconde partie du problème.

Vous devriez d’abord découvrir les chemins les plus courts entre tous vos nœuds critiques (début, fin, mustpass). Une fois ces chemins découverts, vous pouvez construire un graphique simplifié, où chaque arête du nouveau graphique est un chemin d’un nœud critique à un autre dans le graphique original. Il existe de nombreux algorithmes de recherche de chemin que vous pouvez utiliser pour trouver le chemin le plus court ici.

Une fois que vous avez ce nouveau graphe, vous avez exactement le problème du commercial itinérant (enfin, presque … Pas besoin de revenir à votre sharepoint départ). N’importe lequel des messages concernant ceci, mentionnés ci-dessus, s’appliquera.

Andrew Top a la bonne idée:

1) Algorithme de Djikstra 2) Quelques heuristiques de TSP.

Je recommande l’heuristique Lin-Kernighan: c’est l’une des mieux connues pour tout problème NP Complete. La seule autre chose à retenir est que, après avoir étendu le graphique à nouveau après l’étape 2, vous pouvez avoir des boucles dans votre chemin étendu, vous devriez donc les court-circuiter (regardez le degré des sumts le long de votre chemin).

Je ne suis pas sûr de la qualité de cette solution par rapport à l’optimum. Il existe probablement des cas pathologiques liés aux courts-circuits. Après tout, ce problème ressemble beaucoup à Steiner Tree: http://en.wikipedia.org/wiki/Steiner_tree et vous ne pouvez certainement pas approcher Steiner Tree en contractant simplement votre graphique et en exécutant Kruskal par exemple.

Étant donné que la quantité de nœuds et d’arêtes est relativement finie, vous pouvez probablement calculer tous les chemins possibles et prendre le plus court.

Généralement, cela s’appelle le problème des vendeurs itinérants et a un temps d’exécution polynomial non déterministe, quel que soit l’algorithme utilisé.

http://en.wikipedia.org/wiki/Traveling_salesman_problem

Ce n’est pas un problème de TSP et pas NP-hard, car la question d’origine ne nécessite pas que les nœuds à passage obligatoire ne soient visités qu’une seule fois. Cela rend la réponse beaucoup plus simple à la simple brute-force après avoir compilé une liste des plus courts chemins entre tous les nœuds à passer par l’algorithme de Dijkstra. Il y a peut-être une meilleure façon de faire mais un simple serait de simplement travailler un arbre binary à l’envers. Imaginez une liste de noeuds [début, a, b, c, fin]. Sommez les distances simples [start-> a-> b-> c-> end] ceci est votre nouvelle distance cible à battre. Maintenant, essayez [start-> a-> c-> b-> end] et si cela vaut mieux définir cela comme cible (et rappelez-vous que cela vient de ce modèle de nœuds). Travaillez en arrière sur les permutations:

  • [début-> a-> b-> c-> fin]
  • [début-> a-> c-> b-> fin]
  • [début-> b-> a-> c-> fin]
  • [début-> b-> c-> a-> fin]
  • [début-> c-> a-> b-> fin]
  • [début-> c-> b-> a-> fin]

L’un d’entre eux sera le plus court.

(où sont les noeuds “visités plusieurs fois”, le cas échéant? Ils sont juste cachés dans l’étape d’initialisation du plus court chemin. Le plus court chemin entre a et b peut contenir c ou même le point final. )

Il aurait été agréable de nous dire si l’algorithme devrait fonctionner environ une seconde, un jour, une semaine ou plus 🙂 Si une semaine est ok et que c’est une fois, vous pouvez écrire un logiciel en quelques heures et le forcer brutalement . Mais s’il est intégré dans une interface utilisateur et doit être calculé beaucoup de fois par jour … un autre problème je pense.

Que diriez-vous d’utiliser la force brute sur la douzaine de nœuds «à visiter». Vous pouvez couvrir toutes les combinaisons possibles de 12 nœuds assez facilement, ce qui vous laisse un circuit optimal que vous pouvez suivre pour les couvrir.

Maintenant, votre problème est simplifié pour trouver des itinéraires optimaux du nœud de départ au circuit, que vous suivez ensuite jusqu’à ce que vous les couvriez et que vous trouviez ensuite le chemin jusqu’à la fin.

Le chemin final est composé de:

start -> chemin vers le circuit * -> circuit de noeuds de visite obligatoire -> chemin vers la fin * -> fin

Vous trouvez les chemins que j’ai marqués avec * comme ça

Effectuez une recherche A * du nœud de départ à chaque point du circuit pour chacune d’elles, faites une recherche A * du nœud suivant et du nœud précédent du circuit jusqu’à la fin (car vous pouvez suivre le circuit dans un sens ou dans l’autre) finir avec beaucoup de chemins de recherche, et vous pouvez choisir celui avec le coût le plus bas.

Il y a beaucoup de place pour l’optimisation en mettant en cache les recherches, mais je pense que cela générera de bonnes solutions.

Cela ne va pas loin de chercher une solution optimale, car cela pourrait impliquer de laisser le circuit de visite obligatoire dans la recherche.

Une chose qui n’est mentionnée nulle part, est de savoir si le même sumt peut être visité plus d’une fois dans le chemin. La plupart des réponses ici supposent qu’il est possible de visiter le même bord plusieurs fois, mais ma réponse à la question (un chemin ne devrait pas visiter le même sumt plus d’une fois!) Est qu’il n’est pas acceptable de visiter le même sumt deux fois.

Une approche par force brute s’appliquerait toujours, mais vous devriez supprimer les sumts déjà utilisés lorsque vous tentez de calculer chaque sous-ensemble du chemin.