Branch & Bound 알고리즘

Backtracking = DFS visit + bound function

--> DFS를 BFS visit으로 전환하면? --> Branch and Bound.

 

Backtracking = DFS + bound function

Branch&Bound = BFS + bound function

--> 차이는 DFS vs BFS.

Q1. DFS vs BFS 장단점을 논하시오.

--> in practice, Branch&Bound >> Backtracking. 

--> BFS: 신뢰성이 더 좋음

 

Q2. f = g + h < Best (bound function) 관점에서 비교하시오.

--> tree traverse(child visit)순서에 따라, g value, h value는 update 차이 발생

** 미래 estimate 'h-value'가 좋으면(정확한 예측이 가능하면),

잘 맞춘다. ==> BFS로 진행하는 것이 좋다 ==> start root 근처에서 pruning이 일찍 발생할 수 있다.

** backtracking은 탐색을 진행할 수록, 'g-value'가 빨리 갱신된다. ==> g-value가 정확해지고, h-value에 대한 

불확실성이 빠른 속도로 줄어든다.

 

Key point:

여러분이 h-value 설계/추정/수식유도 등에 경험을 통해 자신감이 향상되면, Branch&Bound가 우월함.

---> if not, Backtracking 선호.

 

Improve the standard Branch-and-Bound

- idea: based on the visit order of children nodes

- BFS, DFS: fixed visit order (방문 traverse 순서)

- observe that the promising function/bound function updating

- 방문 순서를 바꿈

 

NEW B&B algorithm:

- Branch and Bound with Best-First (Search), Best-first Branch and Bound

- (인공지능) A* algorithm.

Q1. If promising/bound-value가 다른 값이 배정된다면?

Q2. Best-first Branch&Bound: + greedy approach (local optimal choice)

--> 반드시 해야하는 의문점/질문

--> "이것이 optimal 한가?" ==> Proof required.

 

(advanced topic)

how to estimate the h-value?

- f = g + h

- h: mathmatical expression for estimation/prediction

- 0/1 knapsack problem: h = fractional KS.

Guidline for h-value

: h-value의 range를 설정하며 범위를 좁혀감

 

1. h > 0, h < infinite --> 0 < h < infinity

2. h*: global optimal value --> h와 h*의 관계성 유추 (h*는 실제로 나올수 있는 optimal한 값)

    1) h > h*: overestiamte

    2) h < h*: underestimate

3. Overestimate하면 실수(pruning)하지 않는다.

    1) optimal로 진행가능한 가지를 pruning out하지 않음

    2) 보수적, 안정적인 pruning

    3) pruning되는 subtree 가지의 수는 적을 수 있음

         ex. 0/1: fractional << overestimate

4. 0 < h* < h < infinite: h는 h*보다 큰 값중에서 가장 작은 값이 좋습니다. (because pruning power)

    ==> h = h* + alpha(small value)

5. Q: 0/1 KS에서 활용한 frac. KS을 이용한 h-value보다 더

    pruning이 많이되는 h-value 수식을 제시하시오.

 

0/1 KS problem: h = overestimate expression

-> upper bound ====> "Maximization Optimization"

 

Minimization Optimization Problem: TSP.

-> h = underestimate value

-> lower bound