여행하는 세일즈맨 문제(TSP):
일련의 도시와 모든 도시 쌍 사이의 거리가 주어지면 문제는 모든 도시를 정확히 한 번 방문하고 출발점으로 돌아오는 최단 경로를 찾는 것입니다. 해밀턴 사이클과 TSP의 차이점에 주목하세요. 해밀턴 순환 문제는 모든 도시를 정확히 한 번만 방문하는 투어가 있는지 찾는 것입니다. 여기서 우리는 해밀턴 투어(그래프가 완전하기 때문에)가 존재한다는 것을 알고 있으며 실제로 그러한 투어가 많이 존재하므로 문제는 최소 무게의 해밀턴 사이클을 찾는 것입니다.
예를 들어 오른쪽 그림에 표시된 그래프를 살펴보겠습니다. 그래프의 TSP 투어는 1-2-4-3-1입니다. 투어 비용은 10+25+30+15, 즉 80입니다. 문제는 유명한 NP-하드 문제입니다. 이 문제에 대해 알려진 다항식 시간 솔루션은 없습니다. 다음은 여행하는 외판원 문제에 대한 다양한 해결책입니다.
순진한 해결책:
1) 도시 1을 시작점과 끝점으로 간주합니다.
2) 모두 (n-1) 생성! 도시의 순열.
3) 모든 순열의 비용을 계산하고 최소 비용 순열을 추적합니다.
4) 최소 비용으로 순열을 반환합니다.
시간 복잡도: ?(n!)
동적 프로그래밍:
주어진 정점 세트를 {1, 2, 3, 4,….n}으로 둡니다. 1을 출력의 시작점과 끝점으로 생각해보자. 다른 모든 정점 I(1 제외)에 대해 시작점은 1이고 끝점은 I이며 모든 정점이 정확히 한 번 나타나는 최소 비용 경로를 찾습니다. 이 경로의 비용을 (i)라고 하고 해당 사이클의 비용은 (i) + dist(i, 1)입니다. 여기서 dist(i, 1)은 I에서 1까지의 거리입니다. 마지막으로 우리는 다음을 반환합니다. 모든 [cost(i) + dist(i, 1)] 값의 최소값. 지금까지는 간단해 보입니다.
이제 문제는 비용(i)을 구하는 방법입니다. 동적 프로그래밍을 사용하여 비용(i)을 계산하려면 하위 문제 측면에서 일부 재귀 관계가 필요합니다.
용어를 정의해보자 C(S, i)는 1에서 시작하여 i에서 끝나는 집합 S의 각 정점을 정확히 한 번 방문하는 최소 비용 경로의 비용입니다. . 크기 2의 모든 부분 집합으로 시작하여 S가 부분 집합인 모든 부분 집합에 대해 C(S, i)를 계산한 다음 크기 3의 모든 부분 집합 S에 대해 C(S, i)를 계산합니다. 모든 하위 집합에는 1이 있어야 합니다.
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.> 다음은 하향식 재귀+메모 접근 방식을 사용하여 문제에 대한 동적 프로그래밍 솔루션입니다.
오라클 SQL이 같지 않습니다
하위 집합을 유지하기 위해 비트마스크를 사용하여 하위 집합의 나머지 노드를 나타낼 수 있습니다. 비트는 작동 속도가 더 빠르고 그래프에 노드 수가 적기 때문에 비트마스크를 사용하는 것이 더 좋습니다.
보토3
예를 들어: -
10100은 노드 2를 나타내고 노드 4는 처리되도록 세트에 남아 있음을 나타냅니다.
010010은 노드 1과 4가 하위 집합에 남아 있음을 나타냅니다.
참고: - 그래프가 1 기반이므로 0번째 비트를 무시하세요.
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> |
>
>
자바
빈 목록 자바
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> |
>
>
파이썬3
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> |
>
>
씨#
PD 병합
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 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> |
>
>산출
The cost of most efficient tour = 80>
시간복잡도 : O(n2*2N) 여기서 O(n* 2N)는 모든 상태에서 (코드에서와 같이 for 루프를 통해) 전환에 대한 고유한 하위 문제/상태의 최대 수 및 O(n)입니다.
보조 공간: O(n*2N), 여기서 n은 노드/도시 수입니다.
설정 메뉴 열기
크기가 n인 집합에 대해 각각 크기가 n-1인 n-2개의 하위 집합을 고려하여 모든 하위 집합에 n번째가 포함되지 않도록 합니다. 위의 반복 관계를 사용하여 동적 프로그래밍 기반 솔루션을 작성할 수 있습니다. 최대 O(n*2N) 하위 문제가 있으며 각 문제를 해결하는 데 선형 시간이 걸립니다. 따라서 총 실행 시간은 O(n2*2N). 시간 복잡도는 O(n!)보다 훨씬 적지만 여전히 지수적입니다. 필요한 공간도 기하급수적으로 늘어납니다. 따라서 이 접근 방식은 정점 수가 약간 더 많은 경우에도 실행 가능하지 않습니다. 우리는 곧 여행하는 외판원 문제에 대한 대략적인 알고리즘에 대해 논의할 것입니다.
다음 기사: 여행하는 세일즈맨 문제 | 세트 2
참고자료:
http://www.lsi.upc.edu/~mjserna/docencia/algofib/P07/dynprog.pdf
http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf