Problema del commesso viaggiatore (TSP):
Dato un insieme di città e la distanza tra ogni coppia di città, il problema è trovare il percorso più breve possibile che visiti ogni città esattamente una volta e ritorni al punto di partenza. Notare la differenza tra ciclo hamiltoniano e TSP. Il problema del ciclo hamiltoniano consiste nel trovare se esiste un tour che visiti ogni città esattamente una volta. Qui sappiamo che esiste un ciclo hamiltoniano (perché il grafico è completo) e in effetti esistono molti di questi tour, il problema è trovare un ciclo hamiltoniano di peso minimo.
Consideriamo ad esempio il grafico mostrato nella figura a destra. Un tour TSP nel grafico è 1-2-4-3-1. Il costo del tour è 10+25+30+15 ovvero 80. Il problema è un famoso problema NP-difficile. Non esiste una soluzione di conoscenza in tempo polinomiale per questo problema. Di seguito sono riportate diverse soluzioni per il problema del commesso viaggiatore.
Soluzione ingenua:
1) Considera la città 1 come punto di partenza e di arrivo.
2) Genera tutto (n-1)! Permutazioni di città.
3) Calcola il costo di ogni permutazione e tieni traccia del costo minimo della permutazione.
4) Restituisci la permuta con il minimo costo.
Complessità temporale: ?(n!)
Programmazione dinamica:
Sia il dato insieme di vertici {1, 2, 3, 4,….n}. Consideriamo 1 come punto iniziale e finale dell'output. Per ogni altro vertice I (diverso da 1), troviamo il percorso di costo minimo con 1 come punto iniziale, I come punto finale e tutti i vertici appaiono esattamente una volta. Sia il costo di questo percorso (i), e il costo del Ciclo corrispondente costerebbe (i) + dist(i, 1) dove dist(i, 1) è la distanza da I a 1. Infine, restituiamo il minimo di tutti i valori [cost(i) + dist(i, 1)]. Sembra semplice finora.
Ora la domanda è: come ottenere il costo(i)? Per calcolare il costo(i) utilizzando la Programmazione Dinamica, dobbiamo avere qualche relazione ricorsiva in termini di sottoproblemi.
Definiamo un termine C(S, i) sia il costo del cammino di costo minimo che visita ciascun vertice dell'insieme S esattamente una volta, iniziando da 1 e terminando in i . Iniziamo con tutti i sottoinsiemi di dimensione 2 e calcoliamo C(S, i) per tutti i sottoinsiemi dove S è il sottoinsieme, quindi calcoliamo C(S, i) per tutti i sottoinsiemi S di dimensione 3 e così via. Si noti che 1 deve essere presente in ogni sottoinsieme.
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.> Di seguito è riportata la soluzione di programmazione dinamica per il problema utilizzando l'approccio ricorsivo+memoizzato dall'alto verso il basso: -
controllo null Java
Per mantenere i sottoinsiemi possiamo usare le maschere di bit per rappresentare i nodi rimanenti nel nostro sottoinsieme. Poiché i bit sono più veloci da utilizzare e ci sono solo pochi nodi nel grafico, è meglio utilizzare le maschere di bit.
cosa è awt
Per esempio: -
10100 rappresenta il nodo 2 e il nodo 4 viene lasciato nel set per essere elaborato
010010 rappresenta il nodo 1 e 4 sono lasciati nel sottoinsieme.
NOTA: ignorare il bit 0 poiché il nostro grafico è in base 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> |
>
>
Giava
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> |
Scorciatoie da tastiera di Linux
>
>
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> |
quante settimane in un mese
>
>
C#
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
>// 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> |
>
>Produzione
The cost of most efficient tour = 80>
Complessità temporale: O(n2*2N) dove O(n* 2N)sono il numero massimo di sottoproblemi/stati univoci e O(n) per la transizione (attraverso il ciclo for come nel codice) in ogni stato.
Spazio ausiliario: O(n*2N), dove n è il numero di nodi/città qui.
Per un insieme di dimensione n, consideriamo n-2 sottoinsiemi ciascuno di dimensione n-1 in modo tale che tutti i sottoinsiemi non contengano n-esimo. Utilizzando la relazione ricorsiva di cui sopra, possiamo scrivere una soluzione dinamica basata sulla programmazione. Ci sono al massimo O(n*2N) sottoproblemi, e ognuno di essi richiede tempo lineare per essere risolto. Il tempo di esecuzione totale è quindi O(n2*2N). La complessità temporale è molto inferiore a O(n!) ma pur sempre esponenziale. Anche lo spazio richiesto è esponenziale. Quindi questo approccio non è fattibile anche per un numero leggermente superiore di vertici. Tra poco discuteremo degli algoritmi approssimati per il problema del commesso viaggiatore.
carattere Java in stringa
Articolo successivo: Problema del commesso viaggiatore | Insieme 2
Riferimenti:
http://www.lsi.upc.edu/~mjserna/docencia/algofib/P07/dynprog.pdf
http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf