저번 게시물에서는 외판원 순회 문제를 동적 계획법을 이용해서 풀어보았다. 이번에는 Branch & Bound(분기한정법)을 이용해서 풀 예정이다. 문제의 목표는 동일하게 출발점에서 모든 노드를 각 한 번씩 방문하고 다시 출발점으로 되돌아오는 최소한의 비용을 가지는 경로를 찾는 것이다. 최고 우선 검색을 사용하기 위해서 각 마디의 한계값을 구할 수 있어야 한다. 0-1 배낭 채우기 문제에서는 총무게가 W를 넘지 않도록 하면서 이익을 최대로 하는 게 목표였기 때문에, 주어진 마디에서부터 뻗어나가서 얻을 수 있는 이익의 상한을 계산하였다. 그리고 어떤 마디에서 당시 최대 이익보다 한계값이 큰 경우에 그 마디를 유망하다고 판단했다. 외판원 문제에서는 주어진 마디에서부터 뻗어나가서 얻을 수 있는 여행경로 길이의 ..
