Problème de voyageur de commerce (TSP) :
Étant donné un ensemble de villes et la distance entre chaque paire de villes, le problème est de trouver l’itinéraire le plus court possible qui visite chaque ville exactement une fois et revient au point de départ. Notez la différence entre le cycle hamiltonien et le TSP. Le problème du cycle hamiltonien est de savoir s’il existe un circuit qui visite chaque ville exactement une fois. Ici, nous savons que le circuit hamiltonien existe (car le graphique est complet) et en fait, de nombreux circuits de ce type existent, le problème est de trouver un cycle hamiltonien de poids minimum.
Par exemple, considérons le graphique présenté dans la figure de droite. Un tour TSP dans le graphique est 1-2-4-3-1. Le coût de la visite est de 10+25+30+15, soit 80. Le problème est un fameux problème NP-difficile. Il n’existe pas de solution connue en temps polynomial à ce problème. Voici différentes solutions au problème du voyageur de commerce.
Solution naïve :
1) Considérez la ville 1 comme point de départ et d'arrivée.
2) Générez tout (n-1) ! Permutations de villes.
3) Calculez le coût de chaque permutation et gardez une trace du coût minimum de la permutation.
4) Renvoyez la permutation avec un coût minimum.
Complexité temporelle : ?(n !)
Programmation dynamique:
Soit l'ensemble de sommets donné étant {1, 2, 3, 4,….n}. Considérons 1 comme point de départ et d'arrivée de la sortie. Pour tout autre sommet I (autre que 1), nous trouvons le chemin de coût minimum avec 1 comme point de départ, I comme point final et tous les sommets apparaissant exactement une fois. Supposons que le coût de ce chemin coûte (i), et le coût du cycle correspondant coûterait (i) + dist(i, 1) où dist(i, 1) est la distance de I à 1. Enfin, nous renvoyons le minimum de toutes les valeurs [cost(i) + dist(i, 1)]. Cela semble simple jusqu'à présent.
Maintenant, la question est de savoir comment obtenir le coût (i) ? Pour calculer le coût (i) à l'aide de la programmation dynamique, nous devons avoir une relation récursive en termes de sous-problèmes.
Définissons un terme C(S, i) le coût du chemin à coût minimum visitant chaque sommet de l'ensemble S exactement une fois, commençant à 1 et se terminant à i . Nous commençons par tous les sous-ensembles de taille 2 et calculons C(S, i) pour tous les sous-ensembles où S est le sous-ensemble, puis nous calculons C(S, i) pour tous les sous-ensembles S de taille 3 et ainsi de suite. Notez que 1 doit être présent dans chaque sous-ensemble.
If size of S is 2, then S must be {1, i}, C(S, i) = dist(1, i) Else if size of S is greater than 2. C(S, i) = min { C(S-{i}, j) + dis(j, i)} where j belongs to S, j != i and j != 1.> Vous trouverez ci-dessous la solution de programmation dynamique au problème utilisant une approche récursive + mémorisée de haut en bas : -
structure de contrôle python
Pour gérer les sous-ensembles, nous pouvons utiliser les masques de bits pour représenter les nœuds restants de notre sous-ensemble. Étant donné que les bits sont plus rapides à utiliser et qu'il n'y a que peu de nœuds dans le graphique, il est préférable d'utiliser des masques de bits.
Oracle SQL n'est pas égal
Par exemple: -
10100 représente le nœud 2 et le nœud 4 sont laissés dans l'ensemble à traiter
010010 représente les nœuds 1 et 4 laissés dans le sous-ensemble.
REMARQUE : - ignorez le 0ème bit puisque notre graphique est basé sur 1
C++
#include> using> namespace> std;> // there are four nodes in example graph (graph is 1-based)> const> int> n = 4;> // give appropriate maximum to avoid overflow> const> int> MAX = 1000000;> // dist[i][j] represents shortest distance to go from i to j> // this matrix can be calculated for any given graph using> // all-pair shortest path algorithms> int> dist[n + 1][n + 1] = {> >{ 0, 0, 0, 0, 0 }, { 0, 0, 10, 15, 20 },> >{ 0, 10, 0, 25, 25 }, { 0, 15, 25, 0, 30 },> >{ 0, 20, 25, 30, 0 },> };> // memoization for top down recursion> int> memo[n + 1][1 << (n + 1)];> int> fun(>int> i,>int> mask)> > >// base case> >// if only ith bit and 1st bit is set in our mask,> >// it implies we have visited all other nodes already> >if> (mask == ((1 << i)> // Driver program to test above logic> int> main()> {> >int> ans = MAX;> >for> (>int> i = 1; i <= n; i++)> >// try to go from node 1 visiting all nodes in> >// between to i then return from i taking the> >// shortest route to 1> >ans = std::min(ans, fun(i, (1 << (n + 1)) - 1)> >+ dist[i][1]);> >printf>(>'The cost of most efficient tour = %d'>, ans);> >return> 0;> }> // This code is contributed by Serjeel Ranjan> |
>
>
Java
import> java.io.*;> import> java.util.*;> public> class> TSE {> >// there are four nodes in example graph (graph is> >// 1-based)> >static> int> n =>4>;> >// give appropriate maximum to avoid overflow> >static> int> MAX =>1000000>;> >// dist[i][j] represents shortest distance to go from i> >// to j this matrix can be calculated for any given> >// graph using all-pair shortest path algorithms> >static> int>[][] dist = {> >{>0>,>0>,>0>,>0>,>0> }, {>0>,>0>,>10>,>15>,>20> },> >{>0>,>10>,>0>,>25>,>25> }, {>0>,>15>,>25>,>0>,>30> },> >{>0>,>20>,>25>,>30>,>0> },> >};> >// memoization for top down recursion> >static> int>[][] memo =>new> int>[n +>1>][>1> << (n +>1>)];> >static> int> fun(>int> i,>int> mask)> >> >// base case> >// if only ith bit and 1st bit is set in our mask,> >// it implies we have visited all other nodes> >// already> >if> (mask == ((>1> << i)> >// Driver program to test above logic> >public> static> void> main(String[] args)> >{> >int> ans = MAX;> >for> (>int> i =>1>; i <= n; i++)> >// try to go from node 1 visiting all nodes in> >// between to i then return from i taking the> >// shortest route to 1> >ans = Math.min(ans, fun(i, (>1> << (n +>1>)) ->1>)> >+ dist[i][>1>]);> >System.out.println(> >'The cost of most efficient tour = '> + ans);> >}> }> // This code is contributed by Serjeel Ranjan> |
>
trouver dans la chaîne c++
>
Python3
n>=> 4> # there are four nodes in example graph (graph is 1-based)> # dist[i][j] represents shortest distance to go from i to j> # this matrix can be calculated for any given graph using> # all-pair shortest path algorithms> dist>=> [[>0>,>0>,>0>,>0>,>0>], [>0>,>0>,>10>,>15>,>20>], [> >0>,>10>,>0>,>25>,>25>], [>0>,>15>,>25>,>0>,>30>], [>0>,>20>,>25>,>30>,>0>]]> # memoization for top down recursion> memo>=> [[>->1>]>*>(>1> << (n>+>1>))>for> _>in> range>(n>+>1>)]> def> fun(i, mask):> ># base case> ># if only ith bit and 1st bit is set in our mask,> ># it implies we have visited all other nodes already> >if> mask>=>=> ((>1> << i) |>3>):> >return> dist[>1>][i]> ># memoization> >if> memo[i][mask] !>=> ->1>:> >return> memo[i][mask]> >res>=> 10>*>*>9> # result of this sub-problem> ># we have to travel all nodes j in mask and end the path at ith node> ># so for every node j in mask, recursively calculate cost of> ># travelling all nodes in mask> ># except i and then travel back from node j to node i taking> ># the shortest path take the minimum of all possible j nodes> >for> j>in> range>(>1>, n>+>1>):> >if> (mask & (>1> << j)) !>=> 0> and> j !>=> i>and> j !>=> 1>:> >res>=> min>(res, fun(j, mask & (~(>1> << i)))>+> dist[j][i])> >memo[i][mask]>=> res># storing the minimum value> >return> res> # Driver program to test above logic> ans>=> 10>*>*>9> for> i>in> range>(>1>, n>+>1>):> ># try to go from node 1 visiting all nodes in between to i> ># then return from i taking the shortest route to 1> >ans>=> min>(ans, fun(i, (>1> << (n>+>1>))>->1>)>+> dist[i][>1>])> print>(>'The cost of most efficient tour = '> +> str>(ans))> # This code is contributed by Serjeel Ranjan> |
>
>
C#
Java entier en chaîne
using> System;> class> TSE> {> >// there are four nodes in example graph (graph is> >// 1-based)> >static> int> n = 4;> >// give appropriate maximum to avoid overflow> >static> int> MAX = 1000000;> >// dist[i][j] represents shortest distance to go from i> >// to j this matrix can be calculated for any given> >// graph using all-pair shortest path algorithms> >static> int>[, ] dist = { { 0, 0, 0, 0, 0 },> >{ 0, 0, 10, 15, 20 },> >{ 0, 10, 0, 25, 25 },> >{ 0, 15, 25, 0, 30 },> >{ 0, 20, 25, 30, 0 } };> >// memoization for top down recursion> >static> int>[, ] memo =>new> int>[(n + 1), (1 << (n + 1))];> >static> int> fun(>int> i,>int> mask)> > 3))> >return> dist[1, i];> > >// memoization> >if> (memo[i, mask] != 0)> >return> memo[i, mask];> >int> res = MAX;>// result of this sub-problem> >// we have to travel all nodes j in mask and end the> >// path at ith node so for every node j in mask,> >// recursively calculate cost of travelling all> >// nodes in mask> >// except i and then travel back from node j to node> >// i taking the shortest path take the minimum of> >// all possible j nodes> >for> (>int> j = 1; j <= n; j++)> >if> ((mask & (1 << j)) != 0 && j != i && j != 1)> >res = Math.Min(res,> >fun(j, mask & (~(1 << i)))> >+ dist[j, i]);> >return> memo[i, mask] = res;> >> >// Driver program to test above logic> >public> static> void> Main()> >{> >int> ans = MAX;> >for> (>int> i = 1; i <= n; i++)> >// try to go from node 1 visiting all nodes in> >// between to i then return from i taking the> >// shortest route to 1> >ans = Math.Min(ans, fun(i, (1 << (n + 1)) - 1)> >+ dist[i, 1]);> >Console.WriteLine(> >'The cost of most efficient tour = '> + ans);> >}> }> // This code is contributed by Tapesh(tapeshdua420)> |
>
>
Javascript
Diana Mary Blacker
>// JavaScript code for the above approach> >// there are four nodes in example graph (graph is 1-based)> >let n = 4;> > >// give appropriate maximum to avoid overflow> >let MAX = 1000000;> >// dist[i][j] represents shortest distance to go from i to j> >// this matrix can be calculated for any given graph using> >// all-pair shortest path algorithms> >let dist = [> >[0, 0, 0, 0, 0], [0, 0, 10, 15, 20],> >[0, 10, 0, 25, 25], [0, 15, 25, 0, 30],> >[0, 20, 25, 30, 0],> >];> >// memoization for top down recursion> >let memo =>new> Array(n + 1);> >for> (let i = 0; i memo[i] = new Array(1 << (n + 1)).fill(0) } function fun(i, mask) // base case // if only ith bit and 1st bit is set in our mask, // it implies we have visited all other nodes already if (mask == ((1 << i) // Driver program to test above logic let ans = MAX; for (let i = 1; i <= n; i++) // try to go from node 1 visiting all nodes in // between to i then return from i taking the // shortest route to 1 ans = Math.min(ans, fun(i, (1 << (n + 1)) - 1) + dist[i][1]); console.log('The cost of most efficient tour ' + ans); // This code is contributed by Potta Lokesh> |
>
>Sortir
The cost of most efficient tour = 80>
Complexité temporelle : O(n2*2n) où O(n* 2n)sont le nombre maximum de sous-problèmes/états uniques et O(n) pour la transition (via la boucle for comme dans le code) dans chaque état.
Espace auxiliaire : O(n*2n), où n est le nombre de nœuds/villes ici.
Pour un ensemble de taille n, nous considérons n-2 sous-ensembles chacun de taille n-1 de telle sorte que tous les sous-ensembles ne contiennent pas de nième. En utilisant la relation de récurrence ci-dessus, nous pouvons écrire une solution basée sur la programmation dynamique. Il y a au plus O(n*2n) sous-problèmes, et chacun prend un temps linéaire pour être résolu. La durée totale d’exécution est donc O(n2*2n). La complexité temporelle est bien inférieure à O(n!) mais toujours exponentielle. L'espace requis est également exponentiel. Cette approche est donc également irréalisable, même pour un nombre légèrement plus élevé de sommets. Nous discuterons bientôt des algorithmes approximatifs pour le problème du voyageur de commerce.
Article suivant : Problème de voyageur de commerce | Ensemble 2
Les références:
http://www.lsi.upc.edu/~mjserna/docencia/algofib/P07/dynprog.pdf
http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf