[강의정리] 알고리즘 Backtracking, Branch-and-Bound
Depth First Search(깊이우선탐색)
- 노드의 모든 후손노드를 방문한다. (preorder tree traversal)
State Space Tree(상태 공간 트리)
- 뿌리 노드에서 잎노드까지의 경로가 해답후보(candidate solution)가 되는 트리
- DFS를 하여 해답을 찾을 수 있음. 그러나 가능성이 없는 노드도 검색해서 비효율적
Back Tracking
정의: promising
- 전혀 해답이 나올 가능성이 없는 노드: (non-promising)
- 그렇지 않은 노드: promising
되추적?
- 유망성 점검 후 유망하지 않으면, 부모노드로 돌아가서(“backtrack”) 다음 후손에 대한 검색을 진행
BackTracking 개념
- 상태공간트리에서 깊이우선검색 실시
- 유망하지 않으면 가지쳐서(pruning) 검색하지 않음
- 유망한 노드만 자식노드 검색
The 0-1 Knapsack Problem
- Optimization problem이므로 검색이 끝나기 전까진 해답을 알 수 없음
Let:
- profit: 가치 총합
- weight: 무게 총합
- totweight: 무게 count
- bound: 가치 추정치
풀이:
단위당 가치가 높은 순으로 sort
- 탐욕적 방법처럼 보이지만 탐욕적인 알고리즘은 아니다.
bound와 totweight를 profit과 weight값으로 초기화
탐욕적으로 아이템 취하기
toweight이 W초과할때까지
남은부분에 마지막일부취하고 profit을 bound에 더함
분석
점검하는 마디의 수: O(2^n)
DP보다 좋은가? 확실하지 않음
- DP worst(O(min(2^n, nW)))
- BT worst(O(2^n))
–
Branch-and-Bound (분기한정법)
backtracking과 비슷
- state space tree 사용
Backtracking과 차이점
- 트리를 순회하는 방법을 제한하지 않는다.
- 최적화 문제에서만 사용
Breadth-First Search ( 너비우선탐색)
- 뿌리마디 먼저 검색
- 다음 수준1에있는 모든 마디를 검색
- 다음 수준2에있는 모든 마디를 검색
- …
- Queue 사용
Best-First Search (최고우선탐색)
- 최고의 한계를 가진 마디를 우선으로 선택
- 우선순위 큐(Priority QUeue) 사용
The Travveling Salesperson Problem (TSP)
외판원의 집이 위치하고 있는 도시에서 출발,
다른 도시들을 각각 한번씩만 방문하고, 다시 집으로 돌아오는
가장 짧은 일주여행경로(tour)을 결정하는 문제여러개의 징루 여행경로 중에서 길이가 최소가 되는 경로가 최적일주여행경로(optimal tour)가 된다.
부르트포스 알고리즘:
- 가능한 일주여행경로의 총 개수는 (n-1)!
DP를 이용한 접근방법
V: 모든 정점의 집합
A: V의 부분집합
D[vi][A]: A에 속한 각 정점을 한번씩만 거쳐서 vi에서 v1로 가는 최단경로 길이
D[vi][V-{v1}] = min(W[1][j] + D[vj][V-{v1, vj}])
n=40일때 DP로 6년…. O(n^2*s2^n)
분기한정법을 이용한 접근방법
상태공간트리 구축방법
각 마디는 출발마디로부터 일주여행경로
리프노드에있는 일주여행경로를 찾음
lowerbound 가져오기
Branch-and-Bound
- Backtracking은 속해있다.