건빵의 블로그

Branch and Bound 기법은 백트래킹과 유사하게 어떠한 기준을 만족하는 순서를 정하는 알고리즘 기법이다. 하지만 state space tree를 traverse하는 방법을 특별하게 정하지 않는다는 점에서 백트래킹과 다르며, branch and bound는 최적화 문제에 주로 사용된다. 즉, 백트래킹은 branch and bound의 일부라고 봐도 될 것이다. branch and bound는 어떠한 노드의 promising을 판단하기 위해 bound 개념을 도입한다. 최소해를 구하는 문제에 있어서는 minimum bound를, 최고의 값을 구하는 문제에 있어서는 maximum bound를 정한다. bound는 현재의 상태에서 나올 수 있는 최대 혹은 최소의 값을 의미한다. branch and bo..