공부/자료 구조 및 알고리즘
2019. 7. 22.
알고리즘 기법[부분 탐색] - 분기 한정(Branch & Bound)
분기 한정(Branch & Bound) 분기: branch, 한정: bound →분기를 한정시켜 쓸데없는 시간 낭비를 줄이는 방법 백트래킹에서 부가적으로 발생한 알고리즘 설계 기법 백트래킹이 허용되는 탐색에서 더 이상 탐색할 필요가 없는 지점을 판단하는 것. -비선형 구조의 탐색 과정에서 더 이상 나아갈 수 없는 상황에서 그 이전 단계로 복귀 -탐색과정에서 더 이상 의미가 없다고 판단되는 데이터에 대해서는 더 이상 탐색하지 않고 백트래킹함. -나무에서 필요없는 가지를 잘라내는 가지치기와 유사하여 가지치기 기법이라고도 함. 만약 2번에서 3번으로 진행하려고 할 때, 3번 이하의 모든 노드를 더 이상 탐색할 필요가 없다고 판단할 경우, 이하의 탐색을 중단하고 9번으로 진행할 수 있다. 위 그림은 더 이상 탐..