10 / 16강

더 좋은 답이 없는 가지를 자르기

조건을 만족하는 답을 하나 찾았더라도 그것이 가장 좋은 답인지는 아직 모를 수 있습니다. 분기 한정법은 남은 가지에서 얻을 수 있는 최선의 한계를 계산한 뒤, 현재 답을 이길 수 없는 가지를 버립니다.

배낭에서 가치 합을 최대화한다면

이미 찾은 가능한 답의 가치가 12라고 합시다. 다른 가지에서 지금까지 고른 가치가 6이고, 남은 물건의 가치 합이 5입니다. 남은 물건을 무게 제한 없이 모두 넣어도 6 + 5 = 11입니다. 따라서 이 가지는 12를 이길 수 없습니다.

현재 최선의 가능한 답: 12

가지 A: 현재 6 + 남은 가치 최대 5 = 상한 11 → 중단
가지 B: 현재 8 + 남은 가치 최대 10 = 상한 18 → 더 탐색

물건의 가치는 0 이상이라고 가정했습니다. 남은 물건의 무게를 무시한 합은 실제로 가능한 가치보다 크거나 같으므로 안전한 상한입니다. 다만 너무 느슨해서 가지를 많이 자르지 못할 수 있습니다.

좋은 한계값은 낙관적이면서 가깝습니다

배낭에서는 남은 물건을 쪼개 담을 수 있다고 가정해 더 촘촘한 상한을 만들 수도 있습니다. 원래 문제보다 조건을 느슨하게 풀면 가능한 가치가 줄지 않기 때문입니다.

• 최대화: 앞으로 얻을 수 있는 값의 상한이 현재 최선 이하이면 버립니다.
• 최소화: 앞으로 필요한 비용의 하한이 현재 최선 이상이면 버립니다.
• 주의: 현재 최선은 실제 조건을 만족하는 답에서 얻어야 합니다.

같은 최적값을 내는 답을 전부 모으려면 동점 가지도 남겨야 합니다. ‘최적값 하나’와 ‘모든 최적해’는 종료 조건이 다릅니다.

백트래킹과 비교하기

백트래킹은 주로 조건 위반을 보고 돌아옵니다. 분기 한정법은 조건에 맞는 답이 남아 있어도 더 좋은 답을 만들 수 없다면 돌아옵니다. 둘 다 가지치기를 사용하며 최악에는 많은 후보를 탐색할 수 있습니다. 한계값이 안전하고 필요한 가지를 끝까지 탐색해야 최적해 보장이 성립합니다.

확인 문제

실제로는 앞으로 최대 10을 더 얻을 수 있는데, 실수로 3만 더 얻을 수 있다고 계산하면 무엇이 위험할까요?