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

Question

J'ai un graphe non orienté avec environ 100 nœuds et environ 200 arêtes. Un nœud est étiqueté «début», un autre est «fin» et il y a environ une douzaine étiquetée «mustpass».

Je dois trouver le chemin le plus court à travers ce graphique qui commence par "début", se termine par "fin", et passe par tous les nœuds "mustpass" (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, en Pennsylvanie)

Answer 1

Tous ceux qui comparent cela au problème du voyageur de commerce n’ont probablement pas lu votre question attentivement. Dans TSP, l’objectif est de trouver le cycle le plus court qui visite tous les sommets (un cycle hamiltonien) - cela correspond à avoir tous les nœuds étiquetés 'mustpass'.

Dans votre cas, étant donné que vous n’avez qu’une douzaine d’étiquettes étiquetées 'mustpass', et que 12! est plutôt petit (479001600), vous pouvez simplement essayer toutes les permutations des seuls nœuds 'mustpass' et regarder le chemin le plus court allant de 'début' à 'fin' qui visite les nœuds 'mustpass' dans cet ordre - il vous suffira simplement soit la concaténation des chemins les plus courts entre deux nœuds consécutifs de cette liste.

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

Quelque chose comme ça:

//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 du vrai code, et si vous voulez le chemin réel, vous devez savoir quelle permutation donne la distance la plus courte, ainsi que les chemins les plus courts de toutes les paires, mais vous avez l'idée. )

Il s'exécutera en quelques secondes au maximum sur toute langue raisonnable :)
[Si vous avez n nœuds et k 'mustpass', son temps d'exécution est de O (n ³ ) pour la partie Floyd-Warshall et de O (k! N) pour la partie de toutes les permutations, et 100 ^ 3 + (12!) (100) est pratiquement une cacahuète sauf si vous avez des contraintes très restrictives.]

Answer 2

exécutez Algorithme de Djikstra pour trouver le chemin le plus court entre tous les nœuds critiques (début, fin). , et must-pass), une traversée en profondeur d'abord devrait vous indiquer le chemin le plus court à travers le sous-graphe résultant qui touche tous les nœuds début ... mustpasses ... end

Answer 3

En fait, le problème que vous avez signalé est similaire à celui du vendeur itinérant, mais je pense être plus proche d’un simple problème de parcours. Plutôt que de devoir visiter chaque nœud, il vous suffit de visiter un ensemble particulier de nœuds dans les plus brefs délais (distance) possible.

La raison en est que, contrairement au problème du voyageur de commerce, un labyrinthe de maïs ne vous permettra pas de vous rendre directement d’un point à un autre de la carte sans devoir passer par d’autres nœuds pour vous y rendre.

En fait, je recommanderais A * pathfinding comme technique à envisager. Vous définissez cette option en décidant quels nœuds ont directement accès à quels autres nœuds et quel est le "coût". de chaque saut d'un noeud particulier est. Dans ce cas, cela ressemble à chaque "saut". pourrait être de coût égal, car vos nœuds semblent relativement proches. A * peut utiliser cette information pour trouver le chemin le moins coûteux entre deux points quelconques. Etant donné que vous avez besoin d'aller d'un point A à un point B et de visiter environ 12 heures entre les deux, même une approche par force brute utilisant la recherche de trajectoire ne ferait pas de mal.

Juste une alternative à considérer. Cela ressemble remarquablement au problème du vendeur voyageur, et ce sont de bons papiers à lire, mais regardez de plus près et vous verrez que ce n’est que compliquer les choses. ^ _ ^ Cela vient de l'esprit d'un programmeur de jeu vidéo qui a déjà traité de ce genre de choses.

Answer 4

Ce sont deux problèmes ... Steven Lowe l'a signalé, mais n'a pas suffisamment respecté la deuxième partie du problème.

Vous devez d’abord découvrir les chemins les plus courts entre tous vos nœuds critiques (début, fin, passage obligé). Une fois que ces chemins sont découverts, vous pouvez construire un graphe simplifié, dans lequel chaque arête du nouveau graphe est un chemin d’un nœud critique à un autre du graphe d’origine. 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 graphique, cependant, vous avez exactement le problème du voyageur de commerce (enfin, presque ... inutile de revenir à votre point de départ). Tous les articles concernant ce sujet, mentionnés ci-dessus, s'appliqueront.

Answer 5

Andrew Top a la bonne idée:

1) Algorithme de Djikstra 2) Une heuristique TSP.

Je recommande l'heuristique de Lin-Kernighan: c'est l'un des problèmes les plus connus pour tous les problèmes NP Complete. La seule autre chose à retenir est qu’après avoir développé le graphique à la fin de l’étape 2, il se peut que votre chemin étendu comporte des boucles; vous devez donc court-circuiter celles-ci (regardez le degré de sommets le long de votre chemin).

En fait, 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://fr.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.

Answer 6

Ceci n'est pas un problème de TSP et non de NP-difficile car la question initiale n'exige pas que les nœuds à passage obligatoire soient visités une seule fois. Cela rend la réponse beaucoup, beaucoup plus simple, après avoir compilé une liste des chemins les plus courts entre tous les nœuds incontournables via l’algorithme de Dijkstra. Il y a peut-être une meilleure façon de faire, mais une solution simple serait simplement de faire fonctionner un arbre binaire à l'envers. Imaginez une liste de nœuds [début, a, b, c, fin]. Somme des distances simples [début- > a- > b- > c- > end], voici votre nouvelle distance cible à battre. Maintenant, essayez [start- > a- > c- > b- > end] et si cela vaut mieux, définissez-le comme cible (et rappelez-vous qu'il provient de ce modèle de nœuds). Travailler à l'envers sur les permutations:

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

L'un de ceux-ci sera le plus court.

(où sont les nœuds 'visités plusieurs fois', le cas échéant? Ils sont simplement masqués lors de 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. besoin de soins)

Answer 7

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

Généralement, ce problème est connu sous le nom de voyageur de commerce et a un temps d’exécution polynomial non déterministe, quel que soit l’algorithme que vous utilisez.

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

Answer 8

Pourquoi ne pas utiliser la force brute sur les douze nœuds «doit visiter»? Vous pouvez couvrir assez facilement toutes les combinaisons possibles de 12 nœuds, ce qui vous laisse un circuit optimal à suivre pour les couvrir.

Votre problème est maintenant simplifié: vous recherchez des itinéraires optimaux du nœud de départ au circuit, que vous suivez jusqu'à ce que vous les ayez couverts, puis recherchez l'itinéraire de ce point à la fin.

Le chemin final est composé de:

démarrer - > chemin du circuit * - > circuit de doit visiter les nœuds - > chemin d'accès à la fin * - > fin

Vous trouvez les chemins que j'ai marqués avec * comme ceci

Effectuez une recherche A * depuis le nœud de départ vers chaque point du circuit. pour chacun de ces derniers, effectuez une recherche A * du nœud suivant et du nœud précédent sur le circuit jusqu'à la fin (car vous pouvez suivre le circuit dans les deux sens) Vous vous retrouvez avec beaucoup de chemins de recherche, et vous pouvez choisir celui qui a 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.

Cependant, cela ne va pas loin de chercher une solution optimale, car cela pourrait impliquer de quitter le circuit indispensable dans la recherche.

Answer 9

Une chose qui n’est mentionnée nulle part est de savoir s’il est acceptable que le même sommet soit visité plus d’une fois dans le chemin. La plupart des réponses ici supposent qu'il est correct de visiter le même bord plusieurs fois, mais si je pose la question (un chemin ne devrait pas visiter le même sommet plus d'une fois!), C'est qu'il n'est pas ok visiter le même sommet deux fois.

Donc, une approche par force brute s'appliquerait toujours, mais vous devrez supprimer les sommets déjà utilisés lorsque vous essayez de calculer chaque sous-ensemble du chemin.