La seule différence à laquelle j'ai pu penser pour la question est que dans le Problème du Voyageur de Commerce (TSP) je dois trouver une permutation minimale de tous les sommets du graphe et dans le problème des Plus Courts Chemins il n'est pas nécessaire de considérer tous les sommets nous pouvons rechercher l'espace des états pour des routes de longueur minimale, est-ce que quelqu'un peut suggérer d'autres différences.
Réponses
Trop de publicités?
Vous avez déjà souligné la différence essentielle : le TSP vise à trouver un chemin qui contient une permutation de chaque nœud du graphe, tandis que dans le problème du plus court chemin, tout chemin le plus court donné peut, et le plus souvent, contenir un sous-ensemble des nœuds du graphe.
D'autres différences comprennent :
- La solution du TSP nécessite que sa réponse soit un cycle.
- La solution du TSP répètera nécessairement un nœud dans son chemin, alors qu'un plus court chemin ne le fera pas (à moins que l'on ne cherche le chemin le plus court d'un nœud à lui-même).
- Le TSP est un problème NP-complet et le plus court chemin est connu en temps polynomial.
Si vous recherchez une déclaration précise de la différence, je dirais que vous devez simplement remplacer votre idée de "permutation" par le terme technique et précis de "cycle simple visitant chaque nœud du graphe", ou mieux encore, "cycle Hamiltonien" :
Le TSP nécessite de trouver le cycle simple couvrant chaque nœud du graphe avec le poids le plus faible (alternativement, le cycle Hamiltonien avec le poids le plus faible). Le problème du plus court chemin nécessite de trouver le chemin entre deux nœuds donnés avec le poids le plus faible. Les plus courts chemins n'ont pas besoin d'être Hamiltoniens, ni d'être des cycles.
Jens Schauder
Points
23468
Avec le problème du plus court chemin, vous considérez les chemins entre deux nœuds. Avec le TSP, vous considérez les chemins entre tous les nœuds. Cela rend ce dernier beaucoup plus difficile.
Considérez deux chemins entre les nœuds A et B. L'un passant par D et l'autre par C. Supposons que celui passant par C soit le chemin le plus long. Dans le problème du plus court chemin, ce chemin peut être immédiatement éliminé. Dans le TSP, il est tout à fait possible que ce chemin fasse partie de la solution globale, car vous devrez visiter C et le visiter plus tard pourrait même être plus coûteux.
Par conséquent, vous ne pouvez pas diviser le TSP en des sous-problèmes similaires mais plus petits.
Mahesh Karthu
Points
1058
Chemin le plus court a juste la source et la cible. Nous devons trouver le chemin le plus court entre eux, évidemment la sortie doit être un arbre en temps polynomial.
Recherche du chemin le plus court:-
-
Graphes non orientés : Algorithme de Dijkstra avec liste O(V^2)
-
Graphes orientés avec des poids arbitraires sans cycles négatifs : Algorithme de Bellman–Ford Complexité temporelle O(VE)
-
L'algorithme de Floyd–Warshall est utilisé pour trouver les chemins les plus courts entre tous les paires
Le Problème du Voyageur de Commerce (TSP) n'est pas comme ça, nous devons parcourir chaque nœud depuis la source et finalement revenir à la source avec le coût minimum. Finalement, il doit y avoir un cycle. TSP est un problème NP-complet
Référence:
https://fr.wikipedia.org/wiki/Problème_du_chemin_le_plus_court
https://fr.wikipedia.org/wiki/Problème_du_voyageur_de_commerce
http://www.geeksforgeeks.org/travelling-salesman-problem-set-1/
http://www.geeksforgeeks.org/greedy-algorithms-set-6-dijkstras-shortest-path-algorithm/
https://www.hackerearth.com/practice/algorithms/graphs/shortest-path-algorithms/tutorial/
Tobbe
Points
782
