Handelsreizigerprobleem (TSP):
Gegeven een reeks steden en de afstand tussen elk paar steden, is het probleem om de kortst mogelijke route te vinden die elke stad precies één keer bezoekt en terugkeert naar het startpunt. Let op het verschil tussen Hamiltoniaanse cyclus en TSP. Het Hamiltoniaanse fietsprobleem is om te achterhalen of er een tour bestaat die elke stad precies één keer bezoekt. Hier weten we dat Hamiltonian Tour bestaat (omdat de grafiek compleet is) en in feite bestaan er veel van dergelijke tours. Het probleem is om een Hamiltonian Cycle met een minimumgewicht te vinden.
Beschouw bijvoorbeeld de grafiek in de figuur aan de rechterkant. Een TSP-tour in de grafiek is 1-2-4-3-1. De kosten van de tour bedragen 10+25+30+15, wat 80 is. Het probleem is een beroemd NP-moeilijk probleem. Er is geen bekende oplossing in polynomiale tijd voor dit probleem. Hierna volgen verschillende oplossingen voor het handelsreizigersprobleem.
Naïeve oplossing:
1) Beschouw stad 1 als begin- en eindpunt.
2) Genereer alles (n-1)! Permutaties van steden.
3) Bereken de kosten van elke permutatie en houd de minimale kostenpermutatie bij.
4) Retourneer de permutatie met minimale kosten.
Tijdcomplexiteit: ?(n!)
Dynamisch programmeren:
Laat de gegeven set hoekpunten {1, 2, 3, 4,….n} zijn. Laten we 1 beschouwen als begin- en eindpunt van de uitvoer. Voor elk ander hoekpunt I (behalve 1) vinden we het minimale kostenpad met 1 als startpunt, I als eindpunt, en alle hoekpunten komen precies één keer voor. Stel dat de kosten van dit pad (i) kosten, en de kosten van de overeenkomstige cyclus zouden (i) + dist(i, 1) kosten, waarbij dist(i, 1) de afstand van I naar 1 is. Ten slotte geven we de minimum van alle [cost(i) + dist(i, 1)]-waarden. Dit ziet er tot nu toe eenvoudig uit.
De vraag is nu: hoe krijg je cost(i)? Om de kosten(i) te berekenen met behulp van dynamisch programmeren, hebben we een recursieve relatie nodig in termen van subproblemen.
Laten we een term definiëren C(S, i) zijn de kosten van het minimale kostenpad dat elk hoekpunt in set S precies één keer bezoekt, beginnend bij 1 en eindigend bij i . We beginnen met alle subsets van maat 2 en berekenen C(S, i) voor alle subsets waarbij S de subset is, daarna berekenen we C(S, i) voor alle subsets S van maat 3 enzovoort. Merk op dat 1 in elke subset aanwezig moet zijn.
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.> Hieronder vindt u de dynamische programmeeroplossing voor het probleem met behulp van een top-down recursieve + gememoriseerde benadering: -
tekenreeks jsonobject
Voor het onderhouden van de subsets kunnen we de bitmaskers gebruiken om de resterende knooppunten in onze subset weer te geven. Omdat bits sneller te gebruiken zijn en er maar weinig knooppunten in de grafiek voorkomen, zijn bitmaskers beter te gebruiken.
string naar jsonobject
Bijvoorbeeld: -
10100 vertegenwoordigt knooppunt 2 en knooppunt 4 blijft in de set staan om te worden verwerkt
010010 vertegenwoordigt knooppunt 1 en 4 die in de subset blijven.
OPMERKING: - negeer het 0e bit omdat onze grafiek op 1 is gebaseerd
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> |
>
>
shellscript uitvoerbaar maken
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#
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)> |
subtekenreeks in bash
>
>
Javascript
tekenreeksformaat
>// 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> |
>
>Uitvoer
The cost of most efficient tour = 80>
Tijdcomplexiteit: O(n2*2N) waarbij O(n* 2N)zijn het maximale aantal unieke subproblemen/statussen en O(n) voor transitie (via lus zoals in code) in elke status.
Hulpruimte: O(n*2N), waarbij n hier het aantal knooppunten/steden is.
Voor een set van maat n beschouwen we n-2 subsets van elk maat n-1, zodat niet alle subsets n-de bevatten. Met behulp van de bovenstaande herhalingsrelatie kunnen we een dynamische, op programmeren gebaseerde oplossing schrijven. Er zijn maximaal O(n*2N) subproblemen, en elk ervan kost lineaire tijd om op te lossen. De totale looptijd is dus O(n2*2N). De tijdscomplexiteit is veel minder dan O(n!) maar nog steeds exponentieel. De benodigde ruimte is ook exponentieel. Deze aanpak is dus ook onhaalbaar, zelfs voor een iets groter aantal hoekpunten. Binnenkort zullen we het hebben over algoritmen voor het handelsreizigersprobleem.
Volgend artikel: Handelsreizigerprobleem | Stel 2 in
Referenties:
http://www.lsi.upc.edu/~mjserna/docencia/algofib/P07/dynprog.pdf
http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf