Recherche algorithme du plus court chemin

minirop > Je suis bien d'accord. Si le problème est effectivement NP hard et si l'OP doit impérativement trouver la solution optimale, alors le mieux qu'on puisse faire c'est effectivement de trouver des optimisations/heuristiques pour réduire le temps de calcul en pratique. Mais on restera probablement toujours avec une complexité exponentielle dans le pire des cas.

elegance > On peut voir ton algorithme comme le fait de relancer une instance de A* à chaque rencontre d'un point de contrôle, mais avec une file de priorité partagée par toutes les instances. En pratique c'est probablement plus rapide que de réellement jouer avec plusieurs instances de A*, mais en termes de complexité algorithmique ça revient au même.

Mon algorithme ? J'ai posté un message dimanche 13h29. Dans mon jargon à moi, c'était un algorithme.

Certes, pas conventionnel, pas normé, mais je ne sais pas faire mieux. L'étape suivante, c'est le code.

@elegance: Relis bien le message de SimSonic, tu as du lire uniquement les premiers mots de sa phrase.

@SimSonic: En effet, je ne vois pas d'autres solution que de réperter autant de fois A* ou Dijkstra qu'il y a de noeuds "intérupteurs". Même en modifiant le graphe, au on ferra autant d'appel à Dijkstra qu'il y a de noeuds problématiques. Cependant, ça ne fait pas une complexité exponentiel. Juste polynomiale. Je ne comprend pas pourquoi ça ferait du $k!$ dans le cas d'un prétraitement.

ache > En fait, je crois qu'on fera autant d'appels à Dijkstra qu'il y a d'ordres de rencontrer les points de contrôle, d'où le $k!$.

En lançant Dijkstra une première fois sur un graphe avec $k$ points de contrôle, on peut se retrouver à lancer l'algorithme $k$ fois. Chacune des nouvelles instances de l'algorithme se retrouve maintenant dans un graphe inexploré avec $k - 1$ points de contrôle. Donc chaque instance peut se retrouver à relancer Dijkstra $k - 1$ fois. On continue ainsi en se retrouvant, dans le pire des cas, avec $k(k - 1)(k - 2) \ldots 1 = k!$ relances.

J'espère que cette explication est plus claire que dans mes précédents messages. Un prétraitement peut certainement réduire le nombre de relances en pratique, mais je ne vois pas comment réduire la complexité dans les cas pathologiques. À quels genres de prétraitement penses-tu ? J'ai lu ton message suggérant de rajouter des noeuds intermédiaires, mais j'avoue que je ne vois pas comment l'appliquer en général.

@ache

@elegance: Relis bien le message de SimSonic, tu as du lire uniquement les premiers mots de sa phrase.

Exact. Mauvaise lecture de ma part.

Vous avez ce site : http://qiao.github.io/PathFinding.js/visual/ Si vous avez besoin de visualiser les algorithmes. Le site met à disposition 8 algorithmes dont le A*, le Breadth-First-Search et le Dijkstra.