Problème du voyageur de commerce : Python, C++ Algorithme
Qu’est-ce que le problème du voyageur de commerce (TSP) ?
Le problème du voyageur de commerce (TSP) est un problème combinatoire classique de l'informatique théorique. Le problème demande de trouver le chemin le plus court dans un graphe avec la condition de visiter tous les nœuds une seule fois et de revenir à la ville d'origine.
L'énoncé du problème donne une liste de villes ainsi que les distances entre chaque ville.
Objectif: Pour partir de la ville d'origine, visitez les autres villes une seule fois et revenez à nouveau à la ville d'origine. Notre objectif est de trouver le chemin le plus court possible pour réaliser l’itinéraire aller-retour.
Exemple de TSP
Ici, un graphique est donné où 1, 2, 3 et 4 représentent les villes, et le poids associé à chaque arête représente la distance entre ces villes.
Le but est de trouver le chemin le plus court possible pour le circuit qui part de la ville d'origine, traverse le graphique en ne visitant qu'une seule fois les autres villes ou nœuds et revient à la ville d'origine.
Pour le graphique ci-dessus, l’itinéraire optimal consiste à suivre le chemin du coût minimum : 1-2-4-3-1. Et ce trajet le plus court coûterait 10+25+30+15 =80
Différentes solutions au problème du voyageur de commerce
Le problème du voyageur de commerce (TSP) est classé comme un problème NP-difficile en raison de l'absence d'algorithme de temps polynomial. La complexité augmente de façon exponentielle avec l’augmentation du nombre de villes.
Il existe plusieurs façons de résoudre le problème du voyageur de commerce (tsp). Certaines solutions populaires sont :
L'approche par force brute est la méthode naïve pour résoudre les problèmes des voyageurs de commerce. Dans cette approche, nous calculons d’abord tous les chemins possibles, puis nous les comparons. Le nombre de chemins dans un graphe composé de n villes est n! Il est très coûteux en termes de calcul de résoudre le problème du voyageur de commerce dans cette approche par force brute.
La méthode branch-and-bound : Le problème est décomposé en sous-problèmes dans cette approche. La solution de ces sous-problèmes individuels fournirait une solution optimale.
Ce didacticiel démontrera une approche de programmation dynamique, la version récursive de cette méthode de branchement et de liaison, pour résoudre le problème du voyageur de commerce.
Programmation dynamique est une telle méthode pour rechercher des solutions optimales en analysant tous les itinéraires possibles. C'est l'une des méthodes de solution exactes qui résolvent les problèmes des voyageurs de commerce grâce à un coût relativement plus élevé que le méthodes gourmandes qui fournissent une solution presque optimale.
La complexité informatique de cette approche est O(N^2 * 2^N) qui est abordé plus loin dans cet article.
La méthode du voisin le plus proche est une approche gloutonne basée sur des heuristiques où nous choisissons le nœud voisin le plus proche. Cette approche est moins coûteuse en calcul que l’approche dynamique. Mais cela ne garantit pas une solution optimale. Cette méthode est utilisée pour des solutions presque optimales.
Algorithme pour le problème du voyageur de commerce
Nous utiliserons l’approche de programmation dynamique pour résoudre le problème du voyageur de commerce (TSP).
Avant de démarrer l'algorithme, faisons connaissance avec quelques terminologies :
- Un graphe G=(V, E), qui est un ensemble de sommets et d'arêtes.
- V est l'ensemble des sommets.
- E est l'ensemble des arêtes.
- Les sommets sont reliés par des arêtes.
- Dist(i,j) désigne la distance non négative entre deux sommets, i et j.
Supposons que S soit le sous-ensemble des villes et appartient à {1, 2, 3,…, n} où 1, 2, 3…n sont les villes et i, j sont deux villes de ce sous-ensemble. Maintenant, le coût (i, S, j) est défini de telle manière que la longueur du nœud de visite du chemin le plus court dans S, qui a exactement une fois le point de départ et le point d'arrivée comme i et j respectivement.
Par exemple, le coût (1, {2, 3, 4}, 1) désigne la longueur du chemin le plus court où :
- La ville de départ est 1
- Les villes 2, 3 et 4 ne sont visitées qu'une seule fois
- Le point final est 1
L'algorithme de programmation dynamique serait :
- Fixez cost(i, , i) = 0, ce qui signifie que nous commençons et terminons à i et que le coût est 0.
- Quand |S| > 1, nous définissons cost(i, S, 1) = ∝ où i !=1 . Car au départ, on ne connaît pas le coût exact pour rejoindre la ville i jusqu'à la ville 1 en passant par d'autres villes.
- Maintenant, nous devons commencer à 1 heure et terminer le tour. Nous devons sélectionner la prochaine ville de telle manière-
coût(i, S, j)=min coût (i, S−{i}, j)+dist(i,j) où i∈S et i≠j
Pour la figure donnée, la matrice de contiguïté serait la suivante :
dist(i,j) | 1 | 2 | 3 | 4 |
1 | 0 | 10 | 15 | 20 |
2 | 10 | 0 | 35 | 25 |
3 | 15 | 35 | 0 | 30 |
4 | 20 | 25 | 30 | 0 |
Voyons comment fonctionne notre algorithme :
Étape 1) Nous envisageons notre voyage commençant à la ville 1, visitant d'autres villes une fois et retournant à la ville 1.
Étape 2) S est le sous-ensemble des villes. D'après notre algorithme, pour tout |S| > 1, nous fixerons le coût de la distance (i, S, 1) = ∝. Ici, cost(i, S, j) signifie que nous commençons par la ville i, visitons une fois les villes de S, et maintenant nous sommes dans la ville j. Nous fixons le coût de ce chemin à l'infini car nous ne connaissons pas encore la distance. Les valeurs seront donc les suivantes :
Coût (2, {3, 4}, 1) = ∝ ; la notation indique que nous commençons à la ville 2, traversons les villes 3, 4 et atteignons 1. Et le coût du chemin est infini. De la même manière-
coût(3, {2, 4}, 1) = ∝
coût(4, {2, 3}, 1) = ∝
Étape 3) Maintenant, pour tous les sous-ensembles de S, nous devons trouver ce qui suit :
coût(i, S, j)=min coût (i, S−{i}, j)+dist(i, j), où j∈S et i≠j
Cela signifie le chemin à coût minimum pour commencer à i, traverser une fois le sous-ensemble de villes et revenir à la ville j. Considérant que le voyage commence à la ville 1, le coût optimal du trajet serait = coût(1, {autres villes}, 1).
Voyons comment nous pourrions y parvenir :
Maintenant S = {1, 2, 3, 4}. Il y a quatre éléments. Par conséquent, le nombre de sous-ensembles sera de 2 ^ 4 ou 16. Ces sous-ensembles sont-
1) |S| = Nul :
{Φ}
2) |S| = 1 :
{{1}, {2}, {3}, {4}}
3) |S| = 2 :
{{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}}
4) |S| = 3 :
{{1, 2, 3}, {1, 2, 4}, {2, 3, 4}, {1, 3, 4}}
5) |S| = 4 :
{{1, 2, 3, 4}}
Comme nous partons de 1, nous pourrions supprimer les sous-ensembles contenant la ville 1.
Le calcul de l'algorithme :
1) |S| = Φ :
coût (2, Φ, 1) = dist(2, 1) = 10
coût (3, Φ, 1) = dist(3, 1) = 15
coût (4, Φ, 1) = dist(4, 1) = 20
2) |S| = 1 :
coût (2, {3}, 1) = dist(2, 3) + coût (3, Φ, 1) = 35+15 = 50
coût (2, {4}, 1) = dist(2, 4) + coût (4, Φ, 1) = 25+20 = 45
coût (3, {2}, 1) = dist(3, 2) + coût (2, Φ, 1) = 35+10 = 45
coût (3, {4}, 1) = dist(3, 4) + coût (4, Φ, 1) = 30+20 = 50
coût (4, {2}, 1) = dist(4, 2) + coût (2, Φ, 1) = 25+10 = 35
coût (4, {3}, 1) = dist(4, 3) + coût (3, Φ, 1) = 30+15 = 45
3) |S| = 2 :
coût (2, {3, 4}, 1) = min [ dist[2,3]+Cost(3,{4},1) = 35+50 = 85,
dist[2,4]+Coût(4,{3},1) = 25+45 = 70 ] = 70
coût (3, {2, 4}, 1) = min [ dist[3,2]+Cost(2,{4},1) = 35+45 = 80,
dist[3,4]+Coût(4,{2},1) = 30+35 = 65 ] = 65
coût (4, {2, 3}, 1) = min [ dist[4,2]+Cost(2,{3},1) = 25+50 = 75
dist[4,3]+Coût(3,{2},1) = 30+45 = 75 ] = 75
4) |S| = 3 :
coût (1, {2, 3, 4}, 1) = min [ dist[1,2]+Cost(2,{3,4},1) = 10+70 = 80
dist[1,3]+Coût(3,{2,4},1) = 15+65 = 80
dist[1,4]+Coût(4,{2,3},1) = 20+75 = 95 ] = 80
La solution optimale serait donc 1-2-4-3-1
Pseudo-code
Algorithm: Traveling-Salesman-Problem Cost (1, {}, 1) = 0 for s = 2 to n do for all subsets S belongs to {1, 2, 3, … , n} of size s Cost (s, S, 1) = Infinity for all i Є S and i ≠ 1 Cost (i, S, j) = min {Cost (i, S – {i}, j) + dist(i, j) for j Є S and i ≠ j} Return min(i) Cost (i, {1, 2, 3, …, n}, j) + d(j, i)
Implémentation en C/C++
Voici la mise en œuvre dans C++:
#include <bits/stdc++.h> using namespace std; #define V 4 #define MAX 1000000 int tsp(int graph[][V], int s) { vector<int> vertex; for (int i = 0; i < V; i++) if (i != s) vertex.push_back(i); int min_cost = MAX; while(next_permutation(vertex.begin(), vertex.end())) { int current_cost = 0; int j = s; for (int i = 0; i < vertex.size(); i++) { current_cost += graph[j][vertex[i]]; j = vertex[i]; } current_cost += graph[j][s]; min_cost = min(min_cost, current_cost); return min_cost; } } int main() { int graph[][V] = { { 0, 10, 15, 20 },{ 10, 0, 35, 25 },{ 15, 35, 0, 30 },{ 20, 25, 30, 0 } }; int s = 0; cout << tsp(graph, s) << endl; return 0; }
Sortie :
80
Mise en œuvre dans Python
from sys import maxsize from itertools, import permutations V = 4 def tsp(graph, s): vertex = [] for i in range(V): if i != s: vertex.append(i) min_cost = maxsize next_permutation=permutations(vertex) for i in next_permutation: current_cost = 0 k = s for j in i: current_cost += graph[k][j] k = j current_cost += graph[k][s] min_cost = min(min_cost, current_cost) return min_cost graph = [[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]] s = 0 print(tsp(graph, s))
Sortie :
80
Solutions académiques au TSP
Les informaticiens ont passé des années à rechercher un algorithme de temps polynomial amélioré pour le problème du voyageur de commerce. Jusqu’à présent, le problème est toujours NP-difficile.
Bien que certaines des solutions suivantes aient été publiées ces dernières années, elles ont réduit la complexité dans une certaine mesure :
- Le TSP symétrique classique est résolu par la méthode du suffixe zéro.
- L'algorithme d'optimisation basé sur la biogéographie est basé sur la stratégie de migration pour résoudre les problèmes d'optimisation qui peuvent être planifiés en tant que TSP.
- L'algorithme évolutif multi-objectifs est conçu pour résoudre plusieurs TSP basés sur NSGA-II.
- Le système multi-agents résout le TSP de N villes avec des ressources fixes.
Application du problème du voyageur de commerce
Le problème du voyageur de commerce (TSP) est appliqué dans le monde réel sous ses formes les plus pures et modifiées. Certains d'entre eux sont :
- Planification, logistique et fabrication de puces électroniques: Les problèmes d'insertion des puces surviennent naturellement dans l'industrie des micropuces. Ces problèmes peuvent être planifiés comme des problèmes de voyageur de commerce.
- Le séquençage d'ADN: Une légère modification du problème du voyageur de commerce peut être utilisée dans le séquençage de l'ADN. Ici, les villes représentent les fragments d'ADN et la distance représente la mesure de similarité entre deux fragments d'ADN.
- Astronomie: Le problème du voyageur de commerce est appliqué par les astronomes pour minimiser le temps passé à observer diverses sources.
- Problème de contrôle optimal: La formulation du problème du voyageur de commerce peut être appliquée à des problèmes de contrôle optimal. Plusieurs autres contraintes pourraient être ajoutées.
Analyse de complexité du TSP
- Complexité temporelle: Il y a un total de 2N sous-problèmes pour chaque nœud. Le nombre total de sous-problèmes serait donc N*2N. Chacun des sous-problèmes nécessite un temps linéaire pour être résolu. Si le nœud d'origine n'est pas spécifié, nous devons exécuter des boucles pour N nœuds.
Ainsi, la complexité temporelle totale pour une solution optimale serait le nombre de nœuds * Nombre de sous-problèmes * Temps nécessaire pour résoudre chaque sous-problème. La complexité temporelle peut être définie comme O(N2 * 2^N).
- Complexité de l'espace: L'approche de programmation dynamique utilise la mémoire pour stocker C(S, i), où S est un sous-ensemble de l'ensemble des sommets. Il y a un total de 2N sous-ensembles pour chaque nœud. Ainsi, la complexité spatiale est O(2^N).
Ensuite, vous en apprendrez davantage Algorithme du tamis d'Eratosthène