Q: Why is Greedy algorithm important?
1. natural, simple, fast/easy implementation: (heuristic = 경험적) idea
2. Test-bed: baseline performance 제공, <기준점>
- When we face new/open problems, 연구자들이 가장 먼저 접근하는 설계 전략.
- 정밀도/정확도 (accuracy) 향상, 속도 증가, model size 감소의 기준이 됨
3. May be "optimal.": optimal substructure
local optimal → global optimal: proof required.
example 1. 도둑 가방 (sack) → 보석방: 보석 (무게/부피, 가치)
→ 보석 아이템의 일부만 담을 수 있다. (constraint... 제약)
→ E.g., boss Q: optimal? highest prices?
example 2. startup company: fund raising.
→ 투자자: 사업 아이템, 전체 투자금 (constraint. 제한)
→ 아이템: 사업 주제, 필요 자금, 수익. 일부만 투자할 수 있다.
Definition: constrained combinatorial optimization problem
S = {item_1, item_2, ..., item_n} // 문제 구성요소, object
w(i) = (weight_1, weight_2, .., weight_n}
p(i) = (profit_1, profit_2, .., profit_n}
W = sack size (limited)
Q: Find A (a subset of S) such that
1) ∑w ≤ W.
2) maximizes the profits in A
[Solve the 0/1 KS]
1. BF
- 2^n enumeration -> Exponential time complexity (n: huge)
2. D&C
- optimal을 찾을 수 있는가?, optimal 있더라도 inefficient 하지는 않는가?
- 일반적인 divide and conquer:
각 아이템에 대해 (포함 or 제외)를 고려하므로, 시간복잡도는 O(2^n), optimal을 보장하지 않음
3. Greedy
IDEA 1) ❌
Largest Profit First : simple rank
(w1 w2 w3) = (25kg, 10kg, 10kg)
(p1 p2 p3) = ($10, $9, $9)
W = 30kg.
→ A = {item_1}
현재무게: 25kg → 35kg X
→ optimal A = {i2, i3) total_profit=$18.
IDEA 2) ❌
Largest Profit per Unit weight First
(w1 w2 w3) = (5kg, 10kg, 20kg)
(p1 p2 p3) = ($50, $60, $140)
W= 30kg.
→ pi/wi = ($10, $6, $7)
→ A={item1, item3), total_profit=50+140=190
→ optimal A={i2, i3}, total_profit=60+140=200
언제 Greedy는 optimal solution을 제공하는가?
IDEA 2는 (0/1 KS → Fractional KS)로 변경되면 optimal.
→ Fractional: 남은 sack에 item을 나누어서 일부분을 담을 수 있다.
남은 공간에 5kg에 item2를 분할해서(쪼개서) 담는 것.
4. DP
DP key point
optimal substructure (principle of optimality) → YES
dp[i][w] = max(dp[i-1][w], dp[i-1][w - w[i]] + v[i]),
최적해는 아이템 i를 선택하지 않는 것과 아이템 i를 선택하는 것 중 더 큰 값을 선택해서 얻을 수 있다
IDEA 1)
1차원 array : 아이템을 담은 상태에서 Profit 최대치 → 기록
P[i] = i번째 item까지 선택한 상태의 profit 누적 (APSP i번째 도시를 경유할지를 결정하는 문제와 유사)
P[i] = max {(1) item_i를 담는 경우, (2) item_i를 담지 않는 경우}
= max { P[i - 1], P[i - 1] + p_i }
❌ => weight에 대한 고려가 없음
IDEA 2)
2차원 array (아이템, 무게)
P[i, w] = max {(1) item_i를 못 담는 경우, (2) item_i를 담는 경우 (sack에 포함될 수 있음)}
= max { P[i - 1, w], P[i - 1, w - w_i] + p_i }
❌ => item_i를 담기 위해서는 그 전 sack에 w_i만큼이 비어 있어야 한다
IDEA 3) ✅
P[i,w] = max { (1) P[i-1, w], (2) P[i-1, W-w_i] + p_i }
P[i, w] = max 1) P[i - 1, w] // item_i 포함 안됨
2) P[i - 1, w - w_i] + p_i // item_i 포함
Example:
S = (item_1, item_2, ... item_4)
P_i = (10, 40, 30, 50)
w_i = (5kg, 4kg, 6kg, 3kg)
W = 10kg
바로 위에 것
vs
위에 것에서 w_i 만큼 간 셀 값 + p_i
: 둘 중 큰 것!! (위에 것에서 w_i 만큼 못 가면 그냥 바로 위의 값)
- 이 문제도 APSP나 CMM 처럼 For-loop에서 어떤 값이 선택되는 지 저장해서
이후에 복기하여, 프린트 가능!
Analysis
T(n,W) = TC for each subproblem *nW
= θ(1) * nW = O(nW)
If W is huge (real number)
→ polynomial time complexity(input size 'n')이 아님
→ terrible performance
→ W value: depends on numeric value of input W (NOT number of inputs.)
=> Pseudo-polynomial time complexity
W의 input의 개수가 중요한 게 아니라,
W라는 값의 numerical 값 자체가 중요하다.
W라는 값이 백만, 천만이고, real value를 가질 때, 계산량 자체가 폭발적으로 증가할 수 있다.
단순한 그 인풋의 크기만 중요한 것이 아니라, 인풋의 값 자체도 결과에 영향을 미칠 때,
이를 pseudo-polynomial time complexity라고 한다.
0/1 knapsack problem은 pseudo-polynomial O(nW)
→ Do not need to compute all elements in P[i,w]
Idea: DP optimization (implementation)
# operations = 1 + 2 + 2^2 + ... + 2^(n-1) = O(2^n)
Final TC = min {O(nW), O(2^n)}
Difficulty level: Knapsack problem > > Sort, Search, CMM...
We need a new approach: Backtracking, Branch and Bound...
DFS 시간 복잡도 vs BFS 시간 복잡도
| 인접 리스트 | O(V+E) | O(V+E) |
| 인접 행렬 | O(V^2) | O(V^2) |
5. Backtracking
Promising vs Nonpromising
1. weight > W: stop, not expand, nonpromising
2. (subset sum)
- weight + w(next item) > W (fixed): stop
- weight + w(total sum of next items) < W (fixed): stop
=> 0/1 KnapSack Problem에서는 기준점이 변한다 (Best Profit)
=> (다이아몬드 + 금) → (금 + 큐빅) nonpromising, profit이 BEST보다 작아지면 nonpromising
=> Nonpromising function == Bounding function
Bounding function
= 지금까지의 Profit (g) + 남은 아이템 이익의 최대 추정치 (예측, h)
bound function = g + h < BEST → nonpromising
h는 구현하는 사람마다 다르게 계산/제시할 수 있다
Bounding function for 0/1 Knapsack Problem.
bound function = g + h
g = (item_1, item_2, ... item_i) sum of p_j (j= 1,2,...i)
h = (item_i+1, item_ i+2, . . item_k) sum of p_j (j=i+1,...k)
+
(item_k+1의 일부분) p_(k+1)/w_(k+1) * (W-(w_1+w 2+..w_k))
=> 최대한 쪼개서 넣을 수 있을 만큼 넣을 때 얻을 수 있는 최대 profit
bound = 현재(g) + 미래 예측(h:idea 승부처) < 현재까지의 BEST
h: heuristic(경험, 인사이트)
Q: estimator h는 큰 값을 예측하도록 설계하는 것이 좋은가?
→ pruning power가 증가되는가?, 한편으로는, incorrect pruning이 발생하지는 않는가?
Example:
p1,...,pn = (40, 30, 50, 10)
w1,..,wn = (2kg, 5kg, 10kg, 5kg)
W = 16kg.
N-Queens, subset sum problems: Non-optimization Problem, Yes / No만 답하는 문제
0/1 KS problem: Optimization Problem (조합 최적화 문제), 최적의 값을 찾는 문제
Maximization Optimization Problem (ex. 0/1 KS)
: upper bound 계산 in each node
Minimization Optimization Problem (ex. TSP)
: lower bound in each node
Backtracking = DFS visit + bound function
[Branch and Bound]
Backtracking = DFS visit + bound function
DFS를 BFS visit로 전환하면? → Branch and Bound
NEW algorithm design: Branch and bound approach
Backtracking = DFS + bound function
Branch and Bound = BFS + bound function
Q1. DFS vs BFS 장단점
→ in practice, B&B >> Backtracking (BFS >> DFS)
→ BFS가 더 reliable
Q2. f = g + h < Best (bound function) 관점에서 비교
→ a tree traverse (child visit) 순서에 따라, g value, h value는 update 차이가 발생
미래 estimate h-value가 좋으면 (정확한 예측이 가능하면) 잘 맞춘다
=> BFS로 진행하는 것이 좋다 => start/root 근처 pruning이 일찍 발생할 수 있다
backtracking은 탐색을 진행할수록, 'g-value'가 빨리 갱신된다 => g-value가 정확해지고
h-value에 대한 불확실성이 빠른 속도로 줄어든다.
h-value 설계 / 추정 / 수식 유도 등에 경험을 통해 자신감이 향상되면, B&B가 우월함.
→ if not, Backtracking이 더 나을 수 있음
Example:
[Branch and Bound: Best-First]
Branch and Bound with Best-First (Search)
= Best-first Branch and Bound
= (인공지능) A* algorithm
Improve the standard Branch-and-Bound
- idea: based on the visit order of children nodes
부모 노드에서 양쪽 확장 마친 후에, promising 값이 가장 큰 노드 쪽으로 간다
(일단 양쪽 자식 확장하고, 말단에 있는 자식들 중 promising 값이 가장 큰 자식을 선택한다, 층계 상관 없이)
(일단 자식 양쪽 확장 한 후에, 바로 BEST 값 먼저 업데이트 할 것)
일반 부모가 확장되면 자식까지는 확장된다 (Branch-bound 방식)
Best를 먼저 따라간다, 어기서 말하는 Best는 upper-bound값 (promising 값)의 best
(실제 담은 값의 best는 아니다)
Example:
Advanced Questions
Q1: 만약에 bound-value가 다른 값이 배정된다면, 어떻게 변할 것인가?
Q2: Best-first 방식은 B&B: + greedy approach → "이것이 optimal 한가?" => Proof required
[H-value]
- how to estimate the h-value?
- h: mathematical expression for estimation (h*)
- 0/1 knapsack problem에서 h = fractional KS.
Guideline for h-value: h-value의 range를 설정하여 범위를 좁혀감
1. h > 0, h < infinite → 0 < h < ∞
2. h*: global optimal value → h와 h*의 관계성 유추
1) h > h* : overestimate
2) h < h* : underestimate
3. 0/1 Knapsack 문제에서 Overestimate 하면 실수pruning 하지 않는다
1) optimal로 진행 가능한 가지를 pruning out 하지 않음
2) 보수적, 안정적인 pruning이 가능하다
3) pruning 되는 subtree 가지의 수는 적을 수 있음 (ex. 0/1 KS : fractional)
4. 0 < h* < h < ∞ : h는 h*보다 큰 값 중에서 가장 작은 값이(작으면 작을 수록) 좋다 (pruning power가 크다)
⇒ h = h* + α (α: 작은 값)
5. Q: 0/1 KS에서 활용한 fractional KS을 이용한 h-value보다 더 pruning이 많이 되는 h-value 수식을 제시하시오.
(i+1)번째 담을 수 없음에도 불구하고, 일부를 쪼개서 넣음 → overestimate 한 것
Pruning 가지 수는 적을 수 있으나, 잘못된 가지치기는 하지 않음
0/1 Knapsack problem:
h = overestimate expression
upper bound => Maximization Optimization Problem
TSP:
h = underestimate value
lower bound => Minimization Optimization Problems