알고리즘 기법[부분 탐색] - 분기 한정(Branch & Bound)

분기 한정(Branch & Bound)

분기: branch, 한정: bound

  →분기를 한정시켜 쓸데없는 시간 낭비를 줄이는 방법

 

백트래킹에서 부가적으로 발생한 알고리즘 설계 기법

백트래킹이 허용되는 탐색에서 더 이상 탐색할 필요가 없는 지점을 판단하는 것.

 

  -비선형 구조의 탐색 과정에서 더 이상 나아갈 수 없는 상황에서 그 이전 단계로 복귀

  -탐색과정에서 더 이상 의미가 없다고 판단되는 데이터에 대해서는 더 이상 탐색하지 않고 백트래킹함.

  -나무에서 필요없는 가지를 잘라내는 가지치기와 유사하여 가지치기 기법이라고도 함.

탐색할 트리

만약 2번에서 3번으로 진행하려고 할 때, 3번 이하의 모든 노드를 더 이상 탐색할 필요가 없다고 판단할 경우,

이하의 탐색을 중단하고 9번으로 진행할 수 있다.

탐색공간의 축소

위 그림은 더 이상 탐색이 필요 없다는 것을 판단하고 분기를 제한하여 탐색을 배제한 결과를 나타낸다.

 

결과적으로 11회 탐색해야 할 문제를 6회의 탐색으로 동일한 결과를 얻을 수 있기 때문에 알고리즘의 효율을

향상시킬 수 있다.

Branch & Bound 원리

각 노드를 방문할 때 마다, 그 노드가 유망한지의 여부를 결정하기 위해서 한계치(bound)를 계산한다.

  -한계치는 그 노드로부터 가지를 뻗어나가서(branch) 얻을 수 있는 해답치의 한계를 나타낸다.

  -한계치가 이전까지 찾은 최고 해답값보다 더 좋으면 그 마디는 유망하다(Promising).

 

→만약 한계치가 지금까지 찾은 최적의 해답치 보다 좋지 않은 경우는 더 이상 가지를 뻗어서 검색을 계속 할

    필요가 없으므로, 그 노드는 유망하지 않다고 할 수 있다.(이 경우, 해당 서브트리를 가지치기(pruning)한다.)

Backtracking과의 공통점 및 차이점

공통점

  -경우들을 차례로 나열하는 방법 필요

 

차이점

  -Backtracking: 가보고 더 이상 진행이 되지 않으면 돌아온다.

  -Branch&Bound: 최적해를 찾을 가능성이 없으면 분기를 하지 않는다.

 

Branch & Bound 예시 및 알고리즘

최대-최소 게임 트리 (max-min game tree)

  -게임은 두 명의 경기자 중 하나만 이기면 상대는 진다. 따라서 제로합(zero-sum)게임이라 부르며 상대방의 반응을

    고려하여 선택한다.

  -게임은 나의 기대값을 최대화, 상대의 기대값을 최소화한다. 따라서 최대-최소게임 트리로 표현할 수 있다.

 

틱택톡 게임 방법은 오목과 유사하다. 가로나 세로, 대각선 한 줄 이상을 O 또는 X가 모두 차지하면 이기는 게임이다.  

최대-최소 게임 트리(tic - tac - toe)