DAA - Problème de voyageur de commerce
Énoncé du problème
Un voyageur doit visiter toutes les villes à partir d'une liste, où les distances entre toutes les villes sont connues et chaque ville ne doit être visitée qu'une seule fois. Quel est l'itinéraire le plus court possible pour qu'il visite chaque ville une seule fois et retourne à la ville d'origine?
Solution
Le problème des vendeurs itinérants est le problème de calcul le plus notoire. Nous pouvons utiliser l'approche de la force brute pour évaluer chaque circuit possible et sélectionner le meilleur. Pourn nombre de sommets dans un graphe, il y a (n - 1)! nombre de possibilités.
Au lieu de la force brute utilisant une approche de programmation dynamique, la solution peut être obtenue en moins de temps, bien qu'il n'y ait pas d'algorithme de temps polynomial.
Considérons un graphe G = (V, E), où V est un ensemble de villes et Eest un ensemble d'arêtes pondérées. Un borde(u, v) représente que les sommets u et vest connecté. Distance entre les sommetsu et v est d(u, v), qui devrait être non négatif.
Supposons que nous ayons commencé à la ville 1 et après avoir visité quelques villes maintenant nous sommes en ville j. Par conséquent, il s'agit d'une visite partielle. Nous avons certainement besoin de savoirj, car cela déterminera les villes les plus pratiques à visiter ensuite. Nous devons également connaître toutes les villes visitées jusqu'à présent, afin de ne pas en répéter. C'est donc un sous-problème approprié.
Pour un sous-ensemble de villes S Є {1, 2, 3, ... , n} qui comprend 1, et j Є S, laisser C(S, j) être la longueur du chemin le plus court visitant chaque nœud de S exactement une fois, à partir de 1 et se terminant à j.
Quand |S| > 1, on définitC(S, 1) = ∝ puisque le chemin ne peut pas commencer et se terminer à 1.
Maintenant, laisse exprimer C(S, j)en termes de sous-problèmes plus petits. Nous devons commencer à1 et se terminer à j. Nous devrions sélectionner la prochaine ville de telle manière que
$$ C (S, j) = min \: C (S - \ lbrace j \ rbrace, i) + d (i, j) \: où \: i \ dans S \: et \: i \ neq jc ( S, j) = minC (s- \ lbrace j \ rbrace, i) + d (i, j) \: où \: i \ dans S \: et \: i \ neq j $$
Algorithm: Traveling-Salesman-Problem
C ({1}, 1) = 0
for s = 2 to n do
for all subsets S Є {1, 2, 3, … , n} of size s and containing 1
C (S, 1) = ∞
for all j Є S and j ≠ 1
C (S, j) = min {C (S – {j}, i) + d(i, j) for i Є S and i ≠ j}
Return minj C ({1, 2, 3, …, n}, j) + d(j, i)Une analyse
Il y a au plus $ 2 ^ nn $ sous-problèmes et chacun prend un temps linéaire à résoudre. Par conséquent, la durée totale de fonctionnement est de $ O (2 ^ nn ^ 2) $.
Exemple
Dans l'exemple suivant, nous illustrerons les étapes pour résoudre le problème du voyageur de commerce.
À partir du graphique ci-dessus, le tableau suivant est préparé.
| 1 | 2 | 3 | 4 | |
| 1 | 0 | dix | 15 | 20 |
| 2 | 5 | 0 | 9 | dix |
| 3 | 6 | 13 | 0 | 12 |
| 4 | 8 | 8 | 9 | 0 |
S = Φ
$$ \ small Coût (2, \ Phi, 1) = d (2,1) = 5 \ small Coût (2, \ Phi, 1) = d (2,1) = 5 $$
$$ \ small Coût (3, \ Phi, 1) = d (3,1) = 6 \ small Coût (3, \ Phi, 1) = d (3,1) = 6 $$
$$ \ small Coût (4, \ Phi, 1) = d (4,1) = 8 \ small Coût (4, \ Phi, 1) = d (4,1) = 8 $$
S = 1
$$ \ small Cost (i, s) = min \ lbrace Cost (j, s - (j)) + d [i, j] \ rbrace \ small Cost (i, s) = min \ lbrace Cost (j, s ) - (j)) + d [i, j] \ rbrace $$
$$ \ small Cost (2, \ lbrace 3 \ rbrace, 1) = d [2,3] + Cost (3, \ Phi, 1) = 9 + 6 = 15cost (2, \ lbrace3 \ rbrace, 1) = d [2,3] + coût (3, \ Phi, 1) = 9 + 6 = 15 $$
$$ \ small Cost (2, \ lbrace 4 \ rbrace, 1) = d [2,4] + Cost (4, \ Phi, 1) = 10 + 8 = 18cost (2, \ lbrace4 \ rbrace, 1) = d [2,4] + coût (4, \ Phi, 1) = 10 + 8 = 18 $$
$$ \ small Cost (3, \ lbrace 2 \ rbrace, 1) = d [3,2] + Cost (2, \ Phi, 1) = 13 + 5 = 18cost (3, \ lbrace2 \ rbrace, 1) = d [3,2] + coût (2, \ Phi, 1) = 13 + 5 = 18 $$
$$ \ small Cost (3, \ lbrace 4 \ rbrace, 1) = d [3,4] + Cost (4, \ Phi, 1) = 12 + 8 = 20cost (3, \ lbrace4 \ rbrace, 1) = d [3,4] + coût (4, \ Phi, 1) = 12 + 8 = 20 $$
$$ \ small Cost (4, \ lbrace 3 \ rbrace, 1) = d [4,3] + Cost (3, \ Phi, 1) = 9 + 6 = 15cost (4, \ lbrace3 \ rbrace, 1) = d [4,3] + coût (3, \ Phi, 1) = 9 + 6 = 15 $$
$$ \ small Cost (4, \ lbrace 2 \ rbrace, 1) = d [4,2] + Cost (2, \ Phi, 1) = 8 + 5 = 13cost (4, \ lbrace2 \ rbrace, 1) = d [4,2] + coût (2, \ Phi, 1) = 8 + 5 = 13 $$
S = 2
$$ \ small Cost (2, \ lbrace 3, 4 \ rbrace, 1) = \ begin {cases} d [2, 3] + Cost (3, \ lbrace 4 \ rbrace, 1) = 9 + 20 = 29 \ \ d [2, 4] + Cost (4, \ lbrace 3 \ rbrace, 1) = 10 + 15 = 25 = 25 \ small Cost (2, \ lbrace 3,4 \ rbrace, 1) \\\ lbrace d [ 2,3] + \ petit coût (3, \ lbrace4 \ rbrace, 1) = 9 + 20 = 29d [2,4] + \ petit coût (4, \ lbrace 3 \ rbrace, 1) = 10 + 15 = 25 \ end {cases} = 25 $$
$$ \ small Cost (3, \ lbrace 2, 4 \ rbrace, 1) = \ begin {cases} d [3, 2] + Cost (2, \ lbrace 4 \ rbrace, 1) = 13 + 18 = 31 \ \ d [3, 4] + Cost (4, \ lbrace 2 \ rbrace, 1) = 12 + 13 = 25 = 25 \ small Cost (3, \ lbrace 2,4 \ rbrace, 1) \\\ lbrace d [ 3,2] + \ petit coût (2, \ lbrace4 \ rbrace, 1) = 13 + 18 = 31d [3,4] + \ petit coût (4, \ lbrace 2 \ rbrace, 1) = 12 + 13 = 25 \ end {cases} = 25 $$
$$ \ small Cost (4, \ lbrace 2, 3 \ rbrace, 1) = \ begin {cases} d [4, 2] + Cost (2, \ lbrace 3 \ rbrace, 1) = 8 + 15 = 23 \ \ d [4, 3] + Cost (3, \ lbrace 2 \ rbrace, 1) = 9 + 18 = 27 = 23 \ small Cost (4, \ lbrace 2,3 \ rbrace, 1) \\\ lbrace d [ 4,2] + \ petit coût (2, \ lbrace3 \ rbrace, 1) = 8 + 15 = 23d [4,3] + \ petit coût (3, \ lbrace 2 \ rbrace, 1) = 9 + 18 = 27 \ end {cases} = 23 $$
S = 3
$$ \ small Cost (1, \ lbrace 2, 3, 4 \ rbrace, 1) = \ begin {cases} d [1, 2] + Cost (2, \ lbrace 3, 4 \ rbrace, 1) = 10 + 25 = 35 \\ d [1, 3] + Coût (3, \ lbrace 2, 4 \ rbrace, 1) = 15 + 25 = 40 \\ d [1, 4] + Coût (4, \ lbrace 2, 3 \ rbrace, 1) = 20 + 23 = 43 = 35 coût (1, \ lbrace 2,3,4 \ rbrace), 1) \\ d [1,2] + cost (2, \ lbrace 3,4 \ rbrace , 1) = 10 + 25 = 35 \\ d [1,3] + coût (3, \ lbrace 2,4 \ rbrace, 1) = 15 + 25 = 40 \\ d [1,4] + coût (4 , \ lbrace 2,3 \ rbrace, 1) = 20 + 23 = 43 = 35 \ end {cases} $$
Le chemin de coût minimum est de 35.
Partir du coût {1, {2, 3, 4}, 1}, nous obtenons la valeur minimale pour d [1, 2]. Quands = 3, sélectionnez le chemin de 1 à 2 (le coût est de 10) puis revenez en arrière. Quands = 2, nous obtenons la valeur minimale pour d [4, 2]. Sélectionnez le chemin de 2 à 4 (le coût est de 10) puis revenez en arrière.
Quand s = 1, nous obtenons la valeur minimale pour d [4, 3]. En sélectionnant le chemin 4 à 3 (le coût est de 9), nous passerons ensuite às = Φétape. Nous obtenons la valeur minimale pourd [3, 1] (le coût est de 6).
