분기 한정법: 최적해가 될 수 없는 탐색 가지를 버리기
분기 한정법은 최적화 문제의 탐색 공간을 여러 선택으로 나누고, 각 부분 공간에서 얻을 수 있는 최선의 한계를 계산해 탐색량을 줄인다. 현재 확보한 완성 해와 비교하여 더 좋은 답이 나올 수 없는 가지를 제거한다.
낙관적 상한조차 현재 최선보다 좋지 않은 가지는 탐색하지 않는다.
가능한 해와 낙관적 한계를 구분하기
최대 가치 문제에서는 현재 최선의 실현 가능한 해가 하한이고, 어떤 분기에서 얻을 수 있는 최대 가능 가치의 낙관적 추정이 상한이다. 상한이 현재 해보다 크지 않다면 그 분기를 더 볼 필요가 없다. 최소 비용 문제에서는 방향이 반대다.
0/1 배낭에서 남은 물건을 분수로 쪼개도 된다고 완화하면 원래 문제보다 선택 자유가 커진다. 가치/무게 비율순으로 채운 분수 배낭 값은 원래 분기에서 얻을 수 있는 가치의 상한이다. 실제 0/1 해가 아니어도 상한으로는 쓸 수 있다.
search(partial_choice, current_value, remaining_capacity):
optimistic_bound = current_value + fractional_upper_bound(
unprocessed_items, remaining_capacity
)
if optimistic_bound <= best_feasible_value:
return
if all items have been decided:
best_feasible_value = max(best_feasible_value, current_value)
return
explore the branch that takes the next item, if it fits
explore the branch that skips the next item
전역 최선 값은 실현 가능한 완성 해에서만 갱신해야 한다. 상한 계산 결과를 그대로 정답으로 저장하면 분수 물건을 선택한 불가능한 값을 반환할 수 있다. 상한 함수도 현재 분기에서 아직 사용할 수 있는 물건만 고려해야 한다.
작은 숫자로 가지 제거하기
현재 최선이 20이고 어떤 부분 선택의 현재 가치가 8, 남은 물건을 느슨하게 허용해도 더할 수 있는 가치가 10이면 상한은 18이다. 이 가지는 최선 20을 이길 수 없으므로 중단한다. 다른 가지의 상한이 27이라면 실제로 27을 얻는다는 보장은 없지만 더 탐색할 이유는 있다.
한계를 너무 낙관적으로 잡으면 정확성은 유지되지만 가지가 거의 제거되지 않는다. 반대로 안전한 상한보다 낮게 잡으면 진짜 최적해를 버릴 수 있다. 부동소수점 반올림도 잘못된 가지 제거를 만들 수 있어 보수적인 계산이 필요하다.
깊이 우선은 메모리를 적게 쓰고 완성 해를 빨리 얻을 수 있다. 가장 유망한 한계부터 보는 우선순위 탐색은 많은 대기 상태를 저장할 수 있다. 좋은 초기 해와 타이트한 한계가 실제 성능에 큰 영향을 준다.
최악에는 많은 조합을 방문하여 지수 시간이 걸릴 수 있다. 백트래킹이 제약 위반으로 불가능한 해를 버린다면 분기 한정은 가능한 해 중에서도 현재 최선보다 좋아질 수 없는 영역을 버린다. 탐색 순서와 최적성 증명을 분리해 이해해야 한다.