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 (PVC) est un problème classique d'optimisation combinatoire en informatique théorique. Étant donné un graphe de villes, le PVC consiste à trouver le plus court chemin qui visite chaque ville une seule fois et retourne à la ville de départ.

L'énoncé du problème fournit une liste de villes ainsi que les distances entre chaque paire de villes.

Objectif: Partez de la ville de départ, visitez chaque autre ville une seule fois, puis retournez à la ville de départ. Le but est de trouver le trajet aller-retour le plus court possible.

Exemple de TSP

Considérons le graphique ci-dessous où 1, 2, 3 et 4 représentent les villes, et le poids sur chaque arête représente la distance entre ces villes.

L'objectif est de trouver le circuit le plus court possible qui part de la ville de départ, visite chaque autre ville une seule fois et retourne à la ville de départ.

Pour le graphique ci-dessus, le trajet optimal est 1-2-4-3-1Le coût du trajet le plus court est de 10 + 25 + 30 + 15 = 80.

Différentes solutions au problème du voyageur de commerce

Le problème du voyageur de commerce est classé comme NP-difficile car aucun algorithme polynomial connu ne le résout exactement. Sa complexité croît exponentiellement avec le nombre de villes.

Il existe plusieurs façons d'attaquer le problème du voyageur de commerce (TSP). Les approches les plus courantes sont :

Approche par force brute : La méthode naïve calcule tous les circuits possibles et les compare. Le nombre de circuits dans un graphe à n villes est n!ce qui rend le calcul par force brute très coûteux pour tout ce qui dépasse une dizaine de villes.

Méthode de séparation et d'évaluation : Le problème est décomposé en sous-problèmes, et les solutions de ces sous-problèmes se combinent pour former une solution optimale. Un élagage efficace élimine les circuits partiels dont le coût est inférieur au meilleur coût actuel.

Ce tutoriel présente les approche de programmation dynamique, qui est la version mémorisée de la méthode par séparation et évaluation et correspond à l'algorithme de Bellman-Held-Karp.

Programmation dynamique: Il s'agit d'une méthode exacte qui recherche la solution optimale en réutilisant les zones de chevauchement.ping résultats du sous-problème. Il est plus lent que le résultat quasi optimal. méthodes gourmandesmais elle renvoie toujours un circuit globalement optimal.

La complexité informatique de cette approche est O(N² × 2^N), que nous aborderons plus loin dans cet article.

Méthode du plus proche voisin : Une approche heuristique gloutonne qui se dirige systématiquement vers la ville non visitée la plus proche. Bien moins coûteuse que la programmation dynamique, elle ne garantit cependant pas un circuit optimal et est donc utilisée pour des solutions quasi optimales, lorsque la rapidité prime sur l'obtention d'un minimum exact.

Algorithme pour le problème du voyageur de commerce

Nous utilisons la programmation dynamique pour résoudre le problème du voyageur de commerce (TSP). Avant de présenter l'algorithme, clarifions quelques termes :

• Un graphique G = (V, E) 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 les sommets i et j.

Supposons que S soit un sous-ensemble de villes tirées de {1, 2, 3, …, n} où i et j sont deux villes de ce sous-ensemble. cost(i, S, j) est la longueur du chemin le plus court qui commence à i, visite chaque ville de S exactement une fois et se termine à j.

Par exemple, cost(1, {2, 3, 4}, 1) désigne le 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

La récurrence de la programmation dynamique est :

• complet » cost(i, {}, i) = 0, ce qui signifie que nous commençons et terminons à i sans coût.
• Lorsque vous |S| > 1, définir cost(i, S, 1) = ∞ pour i ≠ 1, car le coût réel du voyage n'est pas encore connu.
• En partant de la ville 1, choisissez la ville suivante de sorte que cost(i, S, j) = min [ cost(i, S − {i}, j) + dist(i, j) ] pour i ∈ S et i ≠ j.

Pour le graphe ci-dessus, la matrice d'adjacence est la suivante :

Voici comment fonctionne l'algorithme :

Étape 1) Le voyage commence à la ville 1, visite chaque autre ville une fois, et retourne à la ville 1.

Étape 2) S est un sous-ensemble de villes. Pour tout |S| > 1, initialiser cost(i, S, 1) = ∞. Ici cost(i, S, j) désigne un circuit qui commence à i, visite une fois chaque ville de S et atteint j. On part de l'infini car la distance est inconnue à ce stade. Les valeurs sont donc :

cost(2, {3, 4}, 1) = ∞ Cela signifie que nous partons de la ville 2, passons par les villes 3 et 4, et arrivons à la ville 1, pour un coût inconnu. De même :

cost(3, {2, 4}, 1) = ∞

cost(4, {2, 3}, 1) = ∞

Étape 3) Pour chaque sous-ensemble de S, calculer :

cost(i, S, j) = min [ cost(i, S − {i}, j) + dist(i, j) ], Où j ∈ S et i ≠ j.

Il s'agit du circuit de coût minimal qui part de i, visite le sous-ensemble de villes une fois et retourne à j. Comme le circuit commence à la ville 1, le coût optimal est cost(1, {other cities}, 1).

Déterminer la récurrence étape par étape

Soit S = {1, 2, 3, 4}. Il y a quatre éléments, donc le nombre de sous-ensembles est 2^4 = 16Ces sous-ensembles sont :

1) |S| = 0 : {Φ}

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 le circuit commence à la ville 1, nous pouvons éliminer tout sous-ensemble contenant la ville 1 lors du calcul des coûts intermédiaires.

Le calcul de l'algorithme se déroule comme suit :

1) |S| = Φ :

• coût(2, Φ, 1) = distance(2, 1) = 10
• coût(3, Φ, 1) = distance(3, 1) = 15
• coût(4, Φ, 1) = distance(4, 1) = 20

2) |S| = 1 :

• coût(2, {3}, 1) = distance(2, 3) + coût(3, Φ, 1) = 35 + 15 = 50
• coût(2, {4}, 1) = distance(2, 4) + coût(4, Φ, 1) = 25 + 20 = 45
• coût(3, {2}, 1) = distance(3, 2) + coût(2, Φ, 1) = 35 + 10 = 45
• coût(3, {4}, 1) = distance(3, 4) + coût(4, Φ, 1) = 30 + 20 = 50
• coût(4, {2}, 1) = distance(4, 2) + coût(2, Φ, 1) = 25 + 10 = 35
• coût(4, {3}, 1) = distance(4, 3) + coût(3, Φ, 1) = 30 + 15 = 45

3) |S| = 2 :

• coût(2, {3, 4}, 1) = min [ dist(2, 3) + coût(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) + coût(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) + coût(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) + coût(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 est 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 in S and i != 1
        Cost (i, S, j) = min {Cost (i, S - {i}, j) + dist(i, j) for j in S and i != j}
Return min(i) Cost (i, {1, 2, 3, ..., n}, j) + d(j, i)

Implémentation en C/C++

Voici l'implémentation dans C++La version ci-dessous corrige le problème initial du code source. return bug, qui se répétait après la toute première permutation au lieu d'énumérer tous les circuits.

#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;
    do {
        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);
    } while (next_permutation(vertex.begin(), vertex.end()));

    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

Le Python La mise en œuvre reflète la C++ version. Elle corrige la source from itertools, import faute de frappe, virgule mal placée return à l'intérieur de la boucle intérieure, et l'indentation parasite sur s = 0.

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
    for perm in permutations(vertex):
        current_cost = 0
        k = s
        for j in perm:
            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 consacré des décennies à la recherche d'algorithmes polynomiaux améliorés pour le problème du voyageur de commerce. À ce jour, ce problème demeure NP-difficile.

Plusieurs techniques publiées permettent de réduire la complexité pratique pour des familles spécifiques d'instances du TSP :

• Le problème classique du voyageur de commerce symétrique est résolu par Méthode du suffixe zéro.
• Le Algorithme d'optimisation basé sur la biogéographie utilise des stratégies de migration pour résoudre les problèmes d'optimisation qui correspondent au TSP.
• Le Algorithme évolutionnaire multi-objectif est conçu pour le TSP multi-objectif et s'appuie sur NSGA-II.
• Le Système multi-agents Cette approche résout le problème du voyageur de commerce (TSP) pour N villes avec des ressources de calcul fixes.
• Le Heuristique de Lin-Kernighan et son successeur LKH Fournir des circuits touristiques à 2-3% de l'optimum pour des cas comportant des millions de villes.
• Concorde utilise des plans de coupe et la méthode de séparation et d'évaluation pour calculer les optima exacts pour des instances de référence comportant des dizaines de milliers de villes.

Application du problème du voyageur de commerce

Le problème du voyageur de commerce se retrouve dans le monde réel sous des formes pures et modifiées. Voici quelques-unes de ses principales applications :

• Planification, logistique et fabrication de microprocesseurs : Les problèmes d'insertion de puces dans l'industrie des microprocesseurs sont modélisés comme des variantes du TSP afin de minimiser le temps de déplacement du bras robotisé.
• Séquençage ADN: Un TSP modifié est utilisé dans le séquençage de l'ADN où les villes représentent les fragments d'ADN et les distances représentent la similarité entre les fragments.
• Astronomie: Les astronomes utilisent le TSP pour minimiser le temps passé à orienter les télescopes entre les cibles d'observation.
• Contrôle optimal : Les formulations TSP modélisent des problèmes de contrôle optimal où de multiples contraintes doivent être respectées tout en minimisant le coût de parcours.
• Livraison au dernier kilomètre: AmazonLes applications de livraison de repas, comme UPS, résolvent les variantes dynamiques du problème du voyageur de commerce (TSP) afin de séquencer les arrêts pour les chauffeurs.
• Préparation de commandes en entrepôt : Les robots et les préparateurs de commandes humains suivent des itinéraires optimisés par le TSP qui raccourcissent le temps de déplacement à l'intérieur des centres de distribution.

Analyse de complexité du TSP

• Complexité temporelle: L'approche de programmation dynamique de Held-Karp résout 2^N des sous-ensembles pour chaque nœud de départ, donnant N × 2^N sous-problèmes. La combinaison de chaque sous-problème prend un temps linéaire. Si le nœud d'origine n'est pas spécifié, une boucle externe sur N nœuds est nécessaire. La complexité temporelle totale est de O(N² × 2^N).
• Complexité de l'espace: La table DP stocke C(S, i) pour chaque sous-ensemble S de l'ensemble des sommets. Il y a 2^N sous-ensembles par nœud, donc la complexité spatiale est O(N × 2^N), qui est souvent écrit comme O(2^N) lorsque N est considéré comme fixe.

Ensuite, découvrez le Algorithme du tamis d'Eratosthène.

FAQ