L'algorithme de Dijsktra appliqué au problème du voyageur de commerce

Je suis un novice (débutant total à la théorie de la complexité computationnelle) et j'ai une question.

Disons que nous avons un «problème du voyageur de commerce», l'application suivante des algorithmes de Dijkstra le résoudra-t-elle?

À partir d'un point de départ, nous calculons la distance la plus courte entre deux points. Nous allons au point. Nous supprimons le point source. Ensuite, nous calculons le prochain point le plus court à partir du point actuel et ainsi de suite ...

À chaque étape, nous réduisons le graphique pendant que nous déplaçons le prochain point de distance le plus court disponible. Jusqu'à ce que nous visitions tous les points.

Cela résoudra-t-il le problème du voyageur de commerce?

L'algorithme de Dijkstra renvoie un arbre de chemin le plus court, contenant le chemin le plus court d'un sommet de départ à l'autre sommet, mais pas nécessairement les chemins les plus courts entre les autres sommets, ou un itinéraire le plus court qui visite tous les sommets.

Voici un contre-exemple où l'algorithme gourmand que vous décrivez ne fonctionnera pas:

À partir de , l'algorithme gourmand choisira l'itinéraire , mais l'itinéraire le plus court commençant et se terminant à est . Étant donné que la route TSP n'est pas autorisée à répéter les sommets, une fois que l'algorithme gourmand choisit , il est obligé de prendre le bord le plus long pour revenir à la ville de départ.[ a , b , c , d , a ] a [ a , b , d , c , a ] a , b , c , d d , $a$$[a,b,c,d,a]$$a$$[a,b,d,c,a]$$a,b,c,d$$d,a$

Comme cela s'est déjà avéré dans les autres réponses, votre suggestion ne résout pas efficacement le problème du voyageur de commerce, permettez-moi d'indiquer la meilleure façon connue dans le domaine de la recherche heuristique (car je vois l'algorithme de Dijkstra quelque peu lié à ce domaine de l'intelligence artificielle) .

Un algorithme heuristique peut renvoyer des solutions optimales (bien que les tailles qu'il puisse gérer sont en fait relativement petites) et la méthode suivante a été suggérée par Richard Korf dans les années 90. Bien qu'il fonctionne parfaitement pour le problème des vendeurs itinérants symétriques (où le coût du bord est égal au coût du même bord lorsqu'il est traversé dans la direction opposée ), il peut être facilement adapté à l'alternative cas de la version asymétrique.( v , u $(u,v)$$(v,u)$

La meilleure approche (que je connaisse) consiste à exécuter un algorithme de recherche heuristique de profondeur et de branchement et de liaison où l'heuristique est le coût de l' arbre couvrant minimal (MST). Étant donné que le MST peut être calculé en temps polynomial avec l' algorithme de Prim ou l' algorithme de Kruskal , on peut s'attendre à ce qu'il renvoie des solutions dans un laps de temps raisonnable. Pour une merveilleuse discussion de ces deux algorithmes, je vous suggère fortement de jeter un œil au manuel de conception d'algorithmes

En fait, permettez-moi de souligner que, puisque cette approche a été suggérée, peu de progrès ont été constatés dans le domaine de la détermination des limites optimales de ce problème, de sorte que je considère que c'est une question brûlante dans le domaine de la recherche combinatoire.

J'espère que cela t'aides,

Je ne sais pas comment quelqu'un ici n'a pas remarqué que l'application de l'algorithme de Dijkstra serait totalement inutile dans ce cas? Vous pouvez implémenter cet algorithme gourmand en sélectionnant simplement le nœud le plus proche, qui est connu apriori. L'algorithme de Dijkstra est utilisé pour découvrir les chemins, mais vous ne faites qu'une seule étape à chaque fois. Cela ne trouve évidemment pas la solution optimale au TSP, mais de nombreuses très bonnes approches ne la trouvent pas non plus. Tous les chercheurs de solutions optimales pour TSP sont très exigeants en termes de calcul.

La réponse est non, ce n'est pas un bon moyen de résoudre le problème TSP. Un bon exemple de compteur est celui où tous les points sont sur une ligne, comme suit:

--5 ------------------ 3 ----- 1--0 --- 2 ---------- 4

en utilisant l'algorithme de Dijsktra, le pauvre vendeur commencerait au point 0, passer d'abord à 1 puis à 2 puis à 3 ect. ce qui n'est pas optimal.

J'espère que cela pourra aider. Jetez un œil au premier chapitre de l'excellent livre de Steven S. Skiena intitulé "The Algorithm Design", il explique cet exemple plus en détail.

Le problème du TSP n'est pas de trouver le chemin le plus court entre deux points, mais de faire un itinéraire entre tous les points qui sont optimaux. Lorsque vous avez l'itinéraire optimal, vous pouvez utiliser Dijsktra pour trouver le chemin le plus court entre chaque point de l'itinéraire.