Brute-Force design: How to implement BF?
Ex. 동전 2개의 모든 조합 나열
→ For-loop 구현
→ Graph 탐사: DFS, BFS
Ex. 미로 공원(Maze problem)
Ex. 4-Queen problem: place 4 Queens onto 4×4 chess board
→ N-Queens problem(generalization)
N-Queens Problem
- Time complexity
ex. 8-Queen problem → 64⁸ (permuation의 수)
State-space tree(Search-space tree)→ 4-Queen state-space tree
모든 탐색 가능한 조합을 검사하고 나열할 필요가 있을까 → 상당 부분은 검사하고 나열할 필요가 없다
Backtracking
1. DFS of a space-state tree, except that nodes are visited
if promising (ex: same row ✕, same col ✕, same diagonal ✕)
2. Backtrack if NON-promising → Pruning
3. (formal) Do a DFS of a state-space tree, checking
whether each node is promising, and
if it is nonpromising, backtracking to the node's parent.
Non-promising 조건이 발견되면, 리프 노드까지 갈 필요 없이 다음 노드를 방문할 필요가 없다.
Promising한가, Promising하지 않은가를 생각하여 조합 수를 줄일 수 있다.
Non-promising하다면, 서브 트리를 방문하지 않고 잘라내겠다는 아이디어
이론적인 시간 복잡도의 향상을 목표로 하는 것이 아니라,
실질적인 실행 시간(runtime/execution time)에 대한 효율성을 극대화하는 것이 목적
[N-Queeens Problem]
Design key: promising function의 설계.
- N-Queen 문제는 promising function이 명확히 주어짐.
- Promising function이 주어지지 않는 일반화된 문제에서는 promising function을 이끌어내는 단계가 필요
Analysis key:
Optimality == 답이 있으면 반드시 정답을 찾는다 → Backtracking의 경우 모든 경우 고려하기 때문에 trivial
!= Efficiency
- 이론적 Time Compleixty: Exponential (NOT polyonmial time) == BF complexity
- 중요한 것은 empirical test → 실험적 성능 (execution / runtime)
Worst time complexity는 brute-force time complexity와 동일하다.
→ Optimality: trivial
→ Time complexity도 누구나 brute enumeration이라는 것을 알기 때문에 크게 중요하지 않음
Backtracking analysis에서 중요한 것은
→ 실험적 성능,
→ 얼마나 불필요한 노드를 줄일 수 있는가
→ Running time을 얼마나 보장하는가
4Q Problem → 16⁴
Q. 자식 노드를 방문하기 전에 check? or 직접 방문 후 check?
→ 구현의 이슈는 개발자 몫, 본 강의에서는 방문 후 check
[Sum of Subsets Problem]
Sum of Subsets Problem (Subset Sum Problem): a special case of 0/1 KS.
S = {item1, item2, ..., item_i, item_(i+1), ..., item_n}
weight = (weight1, weight2, ..., weight_i, ..., weight_n}
W: fixed weight (Given)
→ Find A (a subset of S) such that the sum of weights in A
equals W.
Example:
n=5
weight_i=(5, 6, 10, 11, 16)
W=21kg.
solution: {i1, i2,i3}, {i1,i5}, {i3,14} -> multiple solutions
algorithm design? -> Brute-force.
All enumerations of possible subsets -> for-loop << DFS(훨씬 더 유연하고 dynamic)
i1 i2 i3 i4 i5
O O O O O → CHECK
X O O O O → CHECK
X X X X O → CHECK
...
⇒ 2ⁿ, 즉 O(2ⁿ)
(2ⁿ보다 빠르게 정답을 찾을 수 있는 방법은 없다⇒ difficult problem)
Design:
Step 1. promising function 설계
1) i-th level: weight + weight(i+1) > W
2 ) weight + 미래 총 weight 합 < W
→ IF condition, then STOP.
(위에 조건을 만족하면 자식 노드로 확장, 만족하지 못하면 거기서 멈춘다)
Step 2. DFS traverse / visit
Identify / find out your promising function
BF(DFS) → If ✕ (Not promising), stop visiting(generating child)
function promising(i: index)
{
return (Boolean: T / F)
→ promising = 조건 1) and 조건 2) 위배 여부
}
promising function = 수학적 표현 ⇒ T or F return
Analysis:
1. Optimal solution generated.
2. Execution time → promising function에 따라 달라짐
3. 실제 생성된 노드 수 = 15 / 31 (total) → performance gain
⇒ 또는 생성된 Leaf 노드 수 / 전체 Leaf 노드 수 계산
*Questions:
앞선 예제는 item → sorted.
What if:
- 아이템들이 역순으로 정렬되어 있었으면?
- 아이템들이 random 입력되었으면?
→ 만약에 정렬하는 것이 우수하다면?
→ 정렬은 전처리로 처리될 수 있다.
→ 전처리 (Sorting)가 시간이 다소 걸리더라도, 진행하고 backtracking을 수행하는 것이 좋은 것인가?
[Graph Coloring Problem]
Graph Coloring Problem = Vertex Coloring Problem = m-Coloring Problem
- Color undirected graph with (<= m)개의 colors
- 2 adj vertices must have different colors
Q1. how to find minimum 'm'? → NO (efficient polynomial algorithm X)
Q2. given m (fixed), m-colorable? => Yes/No (algorithm O) → Backtracking for Grapph Coloring
BF: Time Complexity = T(n, m) = O(m^n)
<Promising function> : check adj nodes for the same color
[Hamiltonian]
- Hamiltonian Circuits (HC) Problem = Hamiltonian Path = Hamiltonian Cycle Problem
- 한 붓 그리기 문제
Given a connected and undirected graph, HC (H.tour)
is a path that starts at a given vertex, visits each vertex
exactly once, and ends at the starting vertex.
Promsing function:
1. i_node -> (i+1)_node
2. (n-1)_th node -> 출발 node (zero node)
3. i_th node can not be one of zero ~ (i-1)_th nodes
Analysis:
BF: O(n!)
Backtracking: node 생성 수 보다 running time이 더 중요