저번 게시물에서는 외판원 순회 문제를 동적 계획법을 이용해서 풀어보았다. 이번에는 Branch & Bound(분기한정법)을 이용해서 풀 예정이다. 문제의 목표는 동일하게 출발점에서 모든 노드를 각 한 번씩 방문하고 다시 출발점으로 되돌아오는 최소한의 비용을 가지는 경로를 찾는 것이다. 최고 우선 검색을 사용하기 위해서 각 마디의 한계값을 구할 수 있어야 한다. 0-1 배낭 채우기 문제에서는 총무게가 W를 넘지 않도록 하면서 이익을 최대로 하는 게 목표였기 때문에, 주어진 마디에서부터 뻗어나가서 얻을 수 있는 이익의 상한을 계산하였다. 그리고 어떤 마디에서 당시 최대 이익보다 한계값이 큰 경우에 그 마디를 유망하다고 판단했다. 외판원 문제에서는 주어진 마디에서부터 뻗어나가서 얻을 수 있는 여행경로 길이의 ..
되추적 알고리즘을 이용한 0-1 배낭 채우기를 앞에서 해보았다. 이번에는 분기한정을 이용한 0-1 배낭 채우기를 해보겠다. 되추적 알고리즘과 어떤 차이가 있는지를 중점으로 보면 될 것이다. -앞선 문제와 동일하게 n= 보석의 개수 W= 배낭의 용량 n=4, W=13 p(profit)=[40,30,50,10], w(weight)=[2,5,10,5], p/w(단위 무게별 이익)=[20,6,5,2] 1. 앞선 0-1 배낭 채우기 문제와 같이 무게별 이익이 큰 순서대로 재 정렬한다. 2. 되추적 알고리즘과 상태 공간 트리를 구성한다. 3. 트리는 (profit, totweight, bound)로 이루어진다. profit은 내가 가방에 담은 이익 totweight은 내가 가방에 담은 무게 bound는 내가 탐색한..
Branch & Bound(분기 한정) 알고리즘은 Backtracking(되추적) 알고리즘을 개선한 알고리즘이다. 차이점 트리횡단방법에 구애받지 않음. 최적화 문제를 푸는데 만 쓰인다. 분기 한정 알고리즘은 어떤 마디가 유망한 지를 결정하기 위해서 그 마디에서 한계값을 계산한다. 이 한계값은 그 마디 아래로 확장하여 구할 수 있는 해답 값의 한계(Bound)를 나타낸다. 그 한계값이 찾은 최고 해답 값보다 더 좋지 않으면 그 마디는 유망하지 않다.(nonpromisin), 그 한계값이 찾은 최고 해답 값보다 더 좋으면 유망하다.(promising) 분기 한정 알고리즘은 마디들의 한계값을 비교하여 그중에서 가장 좋은 한계값을 가진 마디의 자식 마디를 방문한다.(유망도가 높은 자식을 방문함). --> 되추적..
