DAA-출장 세일즈맨 문제

문제 설명

여행자는 목록에서 모든 도시를 방문해야합니다. 모든 도시 간의 거리가 알려져 있고 각 도시는 한 번만 방문해야합니다. 그가 각 도시를 정확히 한 번 방문하고 원래 도시로 돌아 오는 가장 짧은 경로는 무엇입니까?

해결책

출장 세일즈맨 문제는 가장 악명 높은 계산 문제입니다. 무차별 대입 방식을 사용하여 가능한 모든 투어를 평가하고 최상의 투어를 선택할 수 있습니다. 에 대한n 그래프의 정점 수에는 (n - 1)! 가능성의 수.

다항식 시간 알고리즘이 없더라도 동적 프로그래밍 접근 방식을 사용하는 무차별 대입 방식 대신 더 짧은 시간에 솔루션을 얻을 수 있습니다.

그래프를 생각 해보자 G = (V, E), 어디 V 도시의 집합이며 E가중치가 적용된 가장자리 집합입니다. 가장자리e(u, v) 그 정점을 나타냅니다 u 과 v연결되어있다. 정점 사이의 거리u 과 v 이다 d(u, v), 음수가 아니어야합니다.

우리가 도시에서 시작했다고 가정하자 1 그리고 몇몇 도시를 방문한 후 우리는 도시에 있습니다 j. 따라서 이것은 부분 여행입니다. 우리는 확실히 알아야합니다j, 다음에 방문하기 가장 편리한 도시가 결정되기 때문입니다. 우리는 또한 지금까지 방문한 모든 도시를 알아야 반복하지 않습니다. 따라서 이것은 적절한 하위 문제입니다.

일부 도시의 경우 S Є {1, 2, 3, ... , n} 그것은 포함 1, 및 j Є S, 허락하다 C(S, j) 각 노드를 방문하는 최단 경로의 길이 S 정확히 한 번, 시작 1 그리고 끝 j.

언제 |S| > 1, 우리는C(S, 1) = ∝ 경로는 다음에서 시작하고 끝날 수 없으므로 1.

자, 표현하자 C(S, j)작은 하위 문제의 관점에서. 우리는 시작해야합니다1 그리고 끝 j. 다음 도시를 선택해야합니다.

$$ C (S, j) = min \ : C (S-\ lbrace j \ rbrace, i) + d (i, j) \ : where \ : i \ in S \ : and \ : i \ neq jc ( S, j) = minC (s- \ lbrace j \ rbrace, i) + d (i, j) \ : where \ : i \ in S \ : and \ : 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)

분석

최대 $ 2 ^ nn $ 개의 하위 문제가 있으며 각각 해결하는 데 선형 시간이 걸립니다. 따라서 총 실행 시간은 $ O (2 ^ nn ^ 2) $입니다.

예

다음 예에서는 출장 판매원 문제를 해결하는 단계를 설명합니다.

위의 그래프에서 다음 표가 준비되었습니다.

	1	2	삼	4
1	0	10	15	20
2	5	0	9	10
삼	6	13	0	12
4	8	8	9	0

S = Φ

$$ \ 작은 비용 (2, \ Phi, 1) = d (2,1) = 5 \ 작은 비용 (2, \ Phi, 1) = d (2,1) = 5 $$

$$ \ 작은 비용 (3, \ Phi, 1) = d (3,1) = 6 \ 작은 비용 (3, \ Phi, 1) = d (3,1) = 6 $$

$$ \ 작은 비용 (4, \ Phi, 1) = d (4,1) = 8 \ small 비용 (4, \ Phi, 1) = d (4,1) = 8 $$

S = 1

$$ \ small 비용 (i, s) = min \ lbrace 비용 (j, s – (j)) + d [i, j] \ rbrace \ small 비용 (i, s) = min \ lbrace 비용 (j, s) )-(j)) + d [i, j] \ rbrace $$

$$ \ small 비용 (2, \ lbrace 3 \ rbrace, 1) = d [2,3] + 비용 (3, \ Phi, 1) = 9 + 6 = 15cost (2, \ lbrace3 \ rbrace, 1) = d [2,3] + 비용 (3, \ Phi, 1) = 9 + 6 = 15 $$

$$ \ small 비용 (2, \ lbrace 4 \ rbrace, 1) = d [2,4] + 비용 (4, \ Phi, 1) = 10 + 8 = 18cost (2, \ lbrace4 \ rbrace, 1) = d [2,4] + 비용 (4, \ Phi, 1) = 10 + 8 = 18 $$

$$ \ small 비용 (3, \ lbrace 2 \ rbrace, 1) = d [3,2] + 비용 (2, \ Phi, 1) = 13 + 5 = 18cost (3, \ lbrace2 \ rbrace, 1) = d [3,2] + 비용 (2, \ Phi, 1) = 13 + 5 = 18 $$

$$ \ small 비용 (3, \ lbrace 4 \ rbrace, 1) = d [3,4] + 비용 (4, \ Phi, 1) = 12 + 8 = 20cost (3, \ lbrace4 \ rbrace, 1) = d [3,4] + 비용 (4, \ Phi, 1) = 12 + 8 = 20 $$

$$ \ small 비용 (4, \ lbrace 3 \ rbrace, 1) = d [4,3] + 비용 (3, \ Phi, 1) = 9 + 6 = 15cost (4, \ lbrace3 \ rbrace, 1) = d [4,3] + 비용 (3, \ Phi, 1) = 9 + 6 = 15 $$

$$ \ small 비용 (4, \ lbrace 2 \ rbrace, 1) = d [4,2] + 비용 (2, \ Phi, 1) = 8 + 5 = 13cost (4, \ lbrace2 \ rbrace, 1) = d [4,2] + 비용 (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] + \ small cost (3, \ lbrace4 \ rbrace, 1) = 9 + 20 = 29d [2,4] + \ small 비용 (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] + \ small cost (2, \ lbrace4 \ rbrace, 1) = 13 + 18 = 31d [3,4] + \ small 비용 (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] + \ small cost (2, \ lbrace3 \ rbrace, 1) = 8 + 15 = 23d [4,3] + \ small 비용 (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] + Cost (3, \ lbrace 2, 4 \ rbrace, 1) = 15 + 25 = 40 \\ d [1, 4] + Cost (4, \ lbrace 2, 3 \ rbrace, 1) = 20 + 23 = 43 = 35 cost (1, \ lbrace 2,3,4 \ rbrace), 1) \\ d [1,2] + cost (2, \ lbrace 3,4 \ rbrace , 1) = 10 + 25 = 35 \\ d [1,3] + cost (3, \ lbrace 2,4 \ rbrace, 1) = 15 + 25 = 40 \\ d [1,4] + cost (4 , \ lbrace 2,3 \ rbrace, 1) = 20 + 23 = 43 = 35 \ end {cases} $$

최소 비용 경로는 35입니다.

비용에서 시작 {1, {2, 3, 4}, 1}, 우리는 최소값을 얻습니다. d [1, 2]. 언제s = 3, 1에서 2까지 (비용은 10) 경로를 선택한 다음 뒤로 이동합니다. 언제s = 2, 우리는 최소값을 얻습니다. d [4, 2]. 2에서 4까지 (비용은 10) 경로를 선택한 다음 뒤로 이동합니다.

언제 s = 1, 우리는 최소값을 얻습니다. d [4, 3]. 경로 4에서 3 (비용은 9)을 선택하면 다음으로 이동합니다.s = Φ단계. 우리는 최소값을 얻습니다.d [3, 1] (비용은 6입니다).