[알고리즘] 분기한정법 - 0-1 배낭 채우기, 외판원 순회

분기한정법이란?

 

분기한정 설계전략은 상태공간트리를 사용해 문제를 푼다는 사실이 되추적과 매우 비슷하다. 차이점으로 분기한정법은 (1) 트리 횡단방법에 구애받지 않고, (2) 최적화 문제를 푸는데만 쓰인다. 분기한정 알고리즘은 어떤 마디가 유망한지를 결정하기 위해서 그 마디에서 수(한계값)를 계산한다. 이 수는 그 마디 아래로 확장해 구할 수 있는 해답의 한계(bound)를 나타낸다. 그 한계값이 그때까지 찾은 최고 해답값보다 더 좋지 않으면 그 마디는 유망하지 않다. 최적값은 문제에 따라서 최대값이 될 수도 있고, 최소값이 될 수도 있으므로 여기서 "좋다"란 문제에 따라서 더 작다는 의미도 되고 더 크다는 의미도 된다.

 

https://kimmessi.tistory.com/74?category=871925

[알고리즘] 그리디 알고리즘 - 최소비용신장트리, 스케줄 짜기

 

위의 글에서 0-1 배낭 채우기 문제를 완전탐색, 그리디, 다이나믹 프로그래밍으로 다양한 방식으로 풀었지만 시간복잡도가 지수시간이었다. 그러면 분기한정법으로 풀면 어떨까?

0-1 배낭 채우기 (0-1 Knapsack problem)

 

분기한정 가지치기 너비우선검색 (breadth-first search with branch-and-bound pruning)

 

여기서 $weight$와 $profit$는 그 마디에 오기까지 포함되었던 아이템의 총 무게와 총 이익으로 한다. $totweight$는 최대 무게 값이고, $bound$는 $profit$의 한계값이다. 그러면 다음과 같은 식을 얻는다.

 

$$totweight = weight + \sum^{k-1}_{j=i+1} w_j$$

$$bound = (profit + \sum^{k-1}_{j=i+1} p_j ) + (W - totalweight) \times \frac{p_k}{w_k} $$

 

지금까지 찾은 최고 해답에서의 값인 $maxprofit$보다 이 한계값이 작거나 같으면 그 마디는 유망하지 않다.

다음 부등식이 성립해도 마디는 유망하지 않다. 

$$weight \geq W$$

 

$i$	$p_i$	$w_i$	$\frac{p_i}{w_i}$
1	$40	2	$20
2	$30	5	$ 6
3	$50	10	$ 5
4	$10	5	$ 2

 

아래의 그림은 위의 표에서 분기한정 가지치기 너비우선탐색을 해 만든 가지친 상태공간트리이다.

노드 별로 위에서부터 $profit$, $weight$, $bound$이다.

 

위의 값들을 위의 공식으로 어떻게 구하는지 예시를 들어보면,

 

노드 (0, 0)

$$totweight = weight + \sum^{3-1}_{j=0+1} w_j = 0 + \sum^{2}_{1} w_j = 7$$

$$bound = \$0 + \sum^{2}_{j=1}p_j + (16-7) \times \$5 = \$70 + \$45 = \$115  $$

 

노드 (3, 2)

$$totweight = 7 + \sum^{4}_{j=4} w_j = 7 + 5 = 12$$

$$bound = \$70 + \sum^{5-1}_{j=4} p_j + (W- totweight) \times \frac{p_5}{w_5} = 70 + 10 ( \frac{p_5}{w_5} = 0) = 80$$

 

노드 (3, 3)에서 $profit$값이 $90 (<= bound)이므로 $maxprofit$은 $90이다. 그러므로 bound값이 90과 같거나 작은 노드들의 자손노드는 유망하지 않으므로 탐색하지 않는다.

 

너비우선탐색을 실시한 결과 17번 노드를 탐색했다.

 

그렇다면 깊이우선탐색을 실시한다면 어떨까?

 

분기한정 가지치기 깊이우선검색 (depth-first search with branch-and-bound pruning)

 

 

위 그림은 깊이우선탐색을 실시했을 때 탐색한 노드들을 표시한 상태공간트리이다.

 

깊이우선탐색으로는 13번 탐색한 걸 볼 수 있다.

 

분기한정 가지치기 최고우선검색 (best-first search with branch-and-bound pruning)

 

일반적으로 너비우선탐색 전략은 깊이우선탐색(되추적)보다 좋은 점이 없다. 그러나 마디의 유망성 여부를 결정하는 것 이외에 추가적인 용도로 한계값을 사용하면 검색을 향상시킬 수 있다. 한계값(bound)이 큰 순서로 너비우선탐색에서 쓰인 큐를 우선순위 큐로 선언해주어서 최고우선탐색을 실시해보자

 

 

한계값이 큰 노드부터 먼저 우선순위 큐에 정렬해 너비우선탐색(최고우선탐색)을 실시한 결과 11번만에 정답을 찾았다.

 

반응형

외판원 순회 문제 (Traveling Salesman problem) (TSP)

 

외판원 문제는 다음과 같이 설명할 수 있다. 어떤 외판원이 n개의 도시를 방문할 계획을 수립하고 있다고 가정하자. 각 도시는 다른 모든 도시와 도로로 연결되어 있다. 출장 비용을 최소로 줄이기 위하여 외판원이 거주하고 있는 도시에서 각 도시를 한 번씩만 방문하고 다시 출발한 도시로 돌아오는 가장 최소 비용의 일주여행 경로를 찾고자 한다. 

(이 때, 도시 하나를 탐색하는데 걸리는 시간이 1μsec이라고 가정한다.)

 

이 때, 완전 탐색, 동적 계획 마지막으로 분기한정법으로 풀면 어떨까?

 

완전 탐색 풀이 (Brute-Force)

 

완전 탐색 알고리즘으로 푼다면 모든 도시의 순회의 경우의 수를 모두 탐색해야하므로

 

$$ T(n) \in \Theta ( (n-1) ! ) $$

 

이 된다. 만약 도시의 수가 20개라면 $19!$의 여행경로를 만들어 보아야 한다. 이 알고리즘으로는 3800년 이상이 걸린다.

 

https://kimmessi.tistory.com/94

[브루트 포스] BOJ 10971 외판원 순회 2

외판원 순회 문제를 완전탐색으로 푼 풀이이다.

 

동적 계획 풀이 (Dynamic Programming)

 

$$ D[v_1][V-{v_1}] = min_{2 \geq j \geq n} ( W[1][j] + D[v_j][V- \{v_1, v_j \} ] ) $$

$$ \mathrm{In\; general} , i \neq 1 \;\; \mathrm{and} \;\; v_i \; \mathrm{is\; not\; in} \; A $$

$$ \begin{matrix} D[v_i][A] & = & minumum_{v_j \in A} (W[i][j] + D[v_j][A- \{v_j \}] ) \;\;\; \mathrm{if} A \neq 0 \\ D[v_i][\emptyset] &= &W[i][1] \end{matrix} $$

 

위의 동적 계획법의 시간 복잡도를 구하면 

 

$$ T(n) \in \Theta(n^2 2^n) $$

 

이 된다. 만약 도시의 수가 20개라면 

 

$$ \begin{matrix} T(n) & = & (n-1)(n-2) 2^{n-3} \\  T(20) & = & 45 \mathrm{sec} \end{matrix}$$ 

45초만에 문제를 풀 수가 있다. 하지만 20이상으로 갈수록 시간복잡도는 점점 복잡해진다.

 

분기 한정법 풀이 (Branch-and-bound)

 

최고우선탐색을 사용하기 위해서 각 마디의 한계값을 구할 수 있어야 한다. 이 문제에서는 주어진 마디에서부터 뻗어나가서 얻을 수 있는 여행경로 길이의 하한을 구할 필요가 있다. 그리고 당시 최소경로길이보다 한계값이 작은 경우에 그 마디를 유망하다고 한다. 한계값은 다음과 같이 구할 수 있다. 이 때 어떤 여행경로라도, 정점을 떠날 때 선택한 이음선의 길이는 그 정점에서 나오는 가장 짧은 이음선의 길이만큼은 최소한 길다.

 

5개의 도시가 있고 왼쪽의 행렬은 그 5개의 도시의 인접행렬이다.

[1] (0-level) 에서의 한계값을 구해보자.

 

$v_1\; minimum(14, 4, 10, 20) = 4 $

$v_2\; minimum(14, 7, 8, 7) = 7$

$v_3\; minimum(4, 5, 7, 16) = 4$

$v_4\; minimum(11, 7, 9, 2) = 2$

$v_5\; minimum(18, 7, 17, 4) = 4$

$4 + 7 + 4 + 2 + 4 = 21$

 

 

 

 

[1, 2] (1-level)에서의 한계값을 구해보자

 

 

 

 

$1 \rightarrow 2: 14$

$2 \rightarrow minimum(3, 4, 5) :$ $v_2에서 v_1$으로 바로 돌아갈 수 없고, $v_2$는 자기자신이므로 제외한다. $minimum(7, 8, 7) = 7$

$3 \rightarrow minimum(1, 4, 5) : 4$

$4 \rightarrow minimum(1, 3, 5) : 2$ 

$5 \rightarrow minimum(1, 3, 4) : 4$

 

$14 + 7 + 4 + 4 = 31$

 

 

 

[1, 3, 2] (2-level)에서의 한계값을 구해보자

 

 

 

 

$1 \rightarrow 3: 4$

$3 \rightarrow 2: 5$

$2 \rightarrow minimum(4, 5): 7$

$4 \rightarrow minimum(1, 5): 2$

$5 \rightarrow minimum(1, 4): 4$

 

$4 + 5 + 7 + 2 + 4 = 22$

 

 

 

 

 

[1, 3, 2, 4] (3-level)에서의 한계값을 구해보자

 

 

 

 

[1, 3, 2, 4]이 결정되면 [1, 3, 2 ,4, 5, 1]도 자동으로 결정되므로

$1 \rightarrow 3: 4$

$3 \rightarrow 2: 5$

$2 \rightarrow 4: 8$

$4 \rightarrow 5: 2$

$5 \rightarrow 1: 19$

$4 + 5 + 8 + 2 + 18 = 37$

이때 한계값은 경로의 비용에 해당한다.

 

위의 방식대로 여행경로마다 한계값을 구한다. 그것을 우선순위 큐에 넣어 한계값이 낮은 노드부터 탐색을 실시한다. 마지막 level일 때는, minlength보다 그 노드의 length가 낮으면 minlength를 length로 바꿔준다. 마지막 level이 아닐 때는, 한계값이 minlength보다 높다면 그 노드의 탐색을 종료하고 낮으면 계속해서 탐색을 한다.

 

위의 설명대로 탐색을 진행해주면 아래의 그림과 같은 트리가 나온다.

 

 

위의 트리 탐색 결과, 가장 짧은 길이는 30이다.