Recherche algorithme du plus court chemin

Bonjour,

Je suis à la cherche d'un algorithme qui donne LE plus court "chemin", entre deux sommets, sur un graphe où certaines arêtes ne sont accessibles uniquement qu'en passant sur certaines sommets. Le graphe peut présenter des cycles et il est possible qu'il faille retourner sur ses pas suite à l'ouverture de nouvelles arêtes. (Un peu comme des interrupteurs qui ouvriraient des passages). Le poids des arêtes n'a pas réellement d'importance, c'est plus le nombre de sommets qui importe.

J'ai pensé à faire un backtracking (sorte de depth-first search avec stack pour sauvegarder le chemin) mais la complexité va être élevée … Existe-t-il mieux ?

Merci

A* est un bon point de départ non ?

Tu veux dire qu'en passant sur certains sommets, d'autres arrêtes deviennent disponibles ?

Si oui j'en sais rien, Si non il me semble que Dijkstra devrait correspondre

Salut, Il a vraisemblablement plus efficace, mais il y a plus simple que A* et Dijsktra (dans le cas où le poids des arêtes n'ont « pas d'importance »). Tu peux notamment réfléchir à comment résoudre ton problème en « simplifiant » le paramètre distance. Par exemple, comment pourrais-tu obtenir efficacement l'ensemble des cases se situant à une distance minimale $d$ du sommet source ?

J'ai aussi un peu de mal à comprendre le problème posé. Il y'aura moyen d'avoir un schema du graphe ?

Mais dans l'absolu, Dijsktra devrait largement faire l'affaire.

Je vais peut-être dire une connerie, mais je crois que le problème est NP hard.

Considérons un graphe $G$. On cherche le plus court chemin entre deux sommets $s$ et $t$. $G$ est construit tel qu'il n'y a qu'une seule arête qui mène vers $t$, et cette arête n'est "débloquée" que lorsque tous les autres sommets ont été visités. Le problème est donc maintenant de trouver le plus courts chemin qui visite tous les sommets de $G - t$. Le problème de trouver le plus court chemin qui visite tous les sommets d'un graphe peut être réduit à celui de déterminer s'il y existe un chemin hamiltonien (qui est NP hard).

Bonjour,

Tout d'abord merci pour vos réponses et je m'excuse de répondre si tardivement. J'ai finalement résolu mon problème par backtracking mais je reste convaincu que ce n'est pas la meilleure solution. Mais je ne trouve rien d'autre pour le moment, le problème avec Dijkstra est qu'on retire les sommets qu'on a déjà rencontrés pour ne garder que ceux potentiels de la frange. Or, chez moi, il risque d'y avoir des retours en arrière comme présenté sur ce schéma:

Dijkstra, va nous faire aller de 0 à 7 en passant par 3 et 4. Alors que le plus court chemin est d'aller jusqu'à 2, retourner en 1 et rejoindre directement 6 par l'arête nouvellement créée. Chemin de longueur 8 contre chemin de longueur 6.

J'espère que mon problème est plus clair, merci beaucoup de m'aider.

Et est-ce que en passant sur une case cela peut supprimer une arrête ? Si non, et que tu sais en passant sur une case qu'il y à de nouvelles arrêtes, en recommençant dijkstra quand tu passe sur ces cases, tu devrais trouver

Le problème avec Dijkstra ici, c'est que le plus court chemin pourrait nécessiter de d'abord atteindre un sommet quelconque par un chemin non-optimal qui passerait par des sommets qui "débloqueraient" les arêtes qui vont bien. Dijkstra donnerait directement le plus court chemin vers ce sommet, ce qui pourrait ne pas être optimal dans le contexte.

Bonsoir,

Dans le schéma que tu donnes, tu peux calculer une distance de 'Manhattan' entre n'importe quel point et le point d'arrivée. Par exemple, entre le point 2 et le point 7, SI TOUT VA BIEN, il faudra au mieux 1 mouvement vertical + 2 mouvements horizontaux.

Dans ton application pratique, est-ce qu'on a aussi cette possibilité : Calculer une distance minimum théorique entre n'importe quel point et le point d'arrivée ?

Bonjour,

Si le poids des arêtes n'a pas d'importance, je recommanderais plutôt l'algo Breadth First Search pour calculer le plus court chemin.

Et dans l'exemple donné plus haut, si lors du passage au sommet 2 une arête s'ouvre entre 2 autres sommets, le plus logique me semble-t-il serait de:

1 - mémoriser le chemin parcouru entre 0 et 2 (C1)

2 - recommencer le BFS entre 2 et 7, on obtient un chemin C2

3 - concaténer C1 et C2

T'es sur de ton coup fromvega ? si l'interrupteur n'est pas sur le chemin mais dans une impadice? J'ai bien une idee mais vaut mieux que je pause ça sur papier.

Humm … Je pense que modifier le graphe est ce qu'il y a de plus simple … En rajoutant des noeuds intermediaires. Par exemple, tu peux transformer ton exemple en : En prenans dijkstra entre les 2 (Le 1 et le 6) sans les "intérupteurs".

Après, il faudrait représenter des situations plus complexe pour voir si cette solution est envisageable.

Beaucoup de réponses très intéressantes, merci énormément. Fromvega, j'avais pensé à votre solution mais la preuve "du" chemin optimal ne m'a pas l'air trivial (en réalité, je cherche un contre-exemple mais je n'en trouve pas pour le moment, je pense un peu comme SimSonic). Ache, j'apprécie énormément votre solution parce que je n'y avais tout simplement pas pensé. Je vais encore laisser mûrir un peu.

Je repose la question : Est-ce que tu est dans un environnement type labyrinthe // Quadrillage. C'est à dire un environnement où les X et les Y sont des entiers, et où le chemin pour aller de (X1,Y1) à (X2,Y2) mesurera au mieux Abs(X1-X2)+Abs(Y1-Y2) pas.

Si tu es dans une telle configuration, le problème de chemin optimum est relativement simple. Si tu es dans une autre configuration, je passe la main.

Non je ne suis pas sûr de mon coup… Je pense que le BFS serait plutôt à relancer depuis chaque sommet à même distance de l'origine que 2 car le chemin optimal ne passera pas forcément par 2 au final. En considérant tous les sommets comme non visités à chaque relance bien sûr, pour pouvoir gérer les impasses et les allers-retours. On garderai le "meilleur" BFS seulement au final.

Mais cette solution n'est pas viable au niveau performance s'il y a beaucoup d'arêtes dynamiques.

Elegance, oui le problème se rapporte à une sorte de labyrinthe et donc le meilleur chemin serait dans le meilleur des cas de longueur Abs(X1-X2)+Abs(Y1-Y2).

Alors, voici un algorithme qui garantit de trouver le plus court chemin, avec une rapidité correcte.

1. tu déclares une structure de ce type , qui servira à décrire la situation à n'importe quel moment :

1
2
3
4
5
6
7
8

Struc 
  N0 : N1+N2 définis ci-dessous.    
  N1 : Nbre de pas parcourus
  N2 : Nbre de pas minimum restants entre le point atteint et l'arrivée
  CHEM1 : Chemin parcouru
  GRILL1 : Etat actuel de la grille 
  CHGT : 0 si la grille est la grille initiale, nombre positif si la grille a évolué (ouverture d'une porte)
Fin

1. Tu déclares un tableau TB de cette Structure. Chaque Structure STRUC est comme un scénario ; On a un tableau qui recense tous les scénarios, on fera en sorte de classer les scénarios du plus prometteur au moins prometteur ( tri sur N0 et N2 décroissants)

2. Tu insères dans ce tableau un seul enregistrement, qui correspond à la situation initiale : Donc pour cette grille particulière, N1=0, CHemin_parcouru=Vide, CHGT=0.

3. Tu boucles indéfiniment sur les instructions ci-dessous.

4.1 Prendre la Première ligne du Tableau TB ; Supprimer cette ligne du tableau TB

4.2 A partir de la situation décrite dans cette structure, recenser les 3 ou 4 mouvements possibles. Parmi les mouvements possibles, comment traiter les mouvements qui repassent sur une case où on est déjà passé ? La variable CHGT sert à gérer ce cas. Si on est déjà passé par la case C au pas n°P, et s'il n'y a plus eu d'ouverture de porte depus P (CHGT<P), alors on ne peut pas repasser par cette case C, cela créerait des boucles infinies. Par contre on peut repasser par cette case C, si dans l'intervalle, il y a eu au moins une porte ouverte.

4.3 Si on a atteint la case arrivée, Solution trouvée, FIN

4.4 Pour chacun de ces 3 ou 4 mouvements, batir la nouvelle grille (en particulier si le mouvement ouvre une porte) : Si le mouvement ouvre une porte, on fait : CHGT = N1. Et insérer une nouvelle ligne dans le tableau TB. Quand on insère une ligne, on fait en sorte que le tableau TB soit toujours trié sur N0 décroissant, et N2 décroissant. (Du scénario le plus prometteur au moins prometteur)

FIN

Si à un moment, le tableau TB est vide, c'est qu'il n'y a pas de solution.

elegance > Si je comprends bien cet algorithme, ça revient au même que l'idée de relancer Dijkstra chaque fois qu'on débloque une arête, sauf qu'ici on relance A*.

Dans les deux cas, on peut se retrouver à relancer l'algorithme autant de fois qu'il y a de façons de rencontrer les sommets qui débloquent de nouvelles arêtes. S'il y a $k$ de ces sommets, c'est potentiellement $k!$ relances de l'algorithme. La complexité (en temps comme en mémoire) devient donc exponentielle par rapport au nombre de sommets.

SimSonic, c'est le cas si effectivement, tous les "points de contrôles" sont obligatoires. Je pense qu'on pourrait évincer quelques trucs en testant le chemin entre le nœud "courant" (le départ ou le nœeud "ouvreur") et la fin, et si seulement il n'y en a pas, alors on part d'un des nœuds "ouvreurs" rencontrés en chemin (ça reste exponentiel, mais ça gère un peu mieux certaines configurations).

Bonsoir, Si on a une librairie avec A ou Dijkstra (que je ne connais pas du tout) et qu'on lance ces Algo comme une boite noire, sans interaction possible, alors oui, on doit être dans des trucs énormes. Ici je parle de bricoler une version 'ouverte' de A, certainement pas parfaite, mais que l'on peut faire tourner avec ce type d'aménagement

Je ne relance pas A à chaque étape, je lance A une fois et une seule, et à l'intérieur de A*, je fais ces aménagements.