TSP: Traveling Salesman Problem
- the most widely-used combinatorial optimization problem in computer science
- minimization optimization
- 택배 배달시스템에서 1,000개 boxes를 배달할 때,
노드들을 한 번씩만 거치고 출발 노드로 돌아와서 가장 먼저 퇴근하도록 하는 경로
Question: h-value estimation in TSP
Maximization Optimization (0/1 KS)
- h 값을 over-estimate
- Overstimate하면 실수로 pruning하지 않음
0 < h* < h < infinite
- h = h* + alpha
alpha 값이 작을 수록 higher pruning power
Minimization Optimization (TSP)
- h 값을 under-estimate
- under-estimation => 실수로 pruning 하지 않음
0 < h < h* < infinite -
- h = h* - alpha
alpha 값이 작을 수록 higher pruning power
h*에 가깝게 붙어있을 수록 pruning power가 높다
example: 5-city TSP (비대칭, fully connected)
BF: O(n!) => B&B: f = g+h
g: actual edge cost (exact)
h: heuristic ??? = h*-alpha
For better understanding, we assume with h=1
an edge cost between two nodes is equal to 1
1) h1
무조건 제일 작은 outgoing edges로 연결되는 것을 추정
h 값은 underestimation만 하면 되고 정답을 맞출 필요는 없다
1번에서 나가는 outgoing 하는 edge 중에서 가장 짧은 것을 타고 나가는 것이고,
2번으로 incoming 하는 edge 중에서 가장 짧은 것을 택하면,
1번과 2번을 잇는 edge가 대충 얼마일 것이다를 추측할 수 있다.
h-value (교과서)
1) TSP >= minimum of outgoing edges of node A
2) TSP >= minimum of incoming edges of node B
: 가장 min edg로 나가고, 가장 min edge로 들어온다
(실제로 연결이 안되는 구조이더라도, 그냥 예측치로 h*보다만 작으면 되므로 이 값을 h값으로 쓸 수 있다, h < h*)
2) h2
h1을 활용하되, 이미 지나온 노드는 배제하여 추정
v1: starting node (fixed)
(v1)의 h = 4 + 7 + 4 + 2 + 4 = 21
(v1->v2)의 h= (v2) min(7,8,7) + (V3) min(4,7,16) + (V4) min(11,9,2) + (v5) min(18,17,4) = 17
2번 도시에서 갈 수 없는 도시는 1번 도시
3번 도시에서 갈 수 없는 도시는 2번 도시 → 1번, 3번, 4번 가능
4번 도시에서 갈 수 없는 도시는 2번 도시 → 1번, 3번, 4번 가능
(v1->v3)의 h = (v3) min(5,7,16) + (v2) min(14,8,7) + (v4) min(11,7,2) + (v5) min(18,7,4)
= 5+7+2+4 = 18
3번 도시에서 1번, 2번 갈 수 없다
4번에서는 2번, 3번 갈 수 없다
(v1->v2->v3)의 h= (v3) min(7,16) + (v4) min(11,2) + (v5) min(18,4)=7+2+4
3) h3
In general, bound function is NOT unique
(1) minimum cost of entering v2 = min of 2nd column = 5
(2) minimum cost of exiting v2 = min of 2nd row = 7
=> average: min cost of v2 = [(1) + (2)] / 2 = 12/2 = 6
Further Issues:
1. h₂와 h₃의 비교 우위를 논하시오.
2. Search tree를 그리면서 답변하시오.
3. 각 incoming / outgoing edges ⇒ 1 / 2 계산 이슈?
4. Branch factor and DFS/BFS
(A with Backtracking) and (B with B&B) vs (A with B&B) and (B with Backtracking)
Branch factor는 큰 것이 좋은가, 작은 것이 좋은가?
⇒ Tree visit type과 관계 있다.
⇒ Branch factor는 설계와 관련 있음 (DFS, BFS)
→ Root에서 가까이 어떤 아이템을 먼저 배치할 것인가의 문제
5. Relaxation (= Simplification) Technique
- Constraint 제거
- h-value estimation
- Relaxed model에서 h*를 쉽게 계산할 수 있다. 그런 다음, 이 h를 원래 있던 모델의 h로 활용하는 것.
Ex. 0/1 Knapsack: h-value 유도
→ (relax) 제약 조건: sack에 item을 (0 or 1)로 담는다, 전부 담거나 담지 못하거나
→ item을 쪼개어 담을 수 있다 ⇒ 0/1 KS의 h-value = fractional knapsack의 h*
6. What if |V|=n is HUGE in TSP? => New design approach is needed:
- NP class problems ==> Approximation algorithms