Search Algorithm

시험 유형 위주로 정리함.

1. Search Algorithm

1.1 Well-defined Search Problem

잘 정의된 search problem 구성요소는 다음 과 같다.

	구성 요소
	Initial state
	Actions
	Transition model (state + action -> next state)
	Goal test
	Path cost function (누적 비용 \(g(n)\))

Node \(n\) 이 갖는 정보 (구현 관점에서)

n.STATE
n.PARENT
n.ACTION
n.PATH-COST = g(N)

1.2 Performance Evaluation (4 Methods)

모든 Search Algorithm 은 보통 이 4개로 평가한다.

• Completeness : 해가 존재하면 반드시 찾나?
• Optimality : 최소비용(최적해) 해를 찾나?
• Time Complexity
• Space Complexity

1.3 분석에 쓰이는 기호

Symbol	Desc
\(b\)	branching factor (최대 자식 수)
\(d\)	가장 얕은 goal 의 깊이, depth
\(m\)	가능한 경로의 최대 길이 \((m \geq d)\)
\(C^*\)	최적해 비용
\(\epsilon\)	최소 step cost

2. Tree Search vs. Graph Search

2.1 Tree Search

탐색 트리 - 를 그대로 전개한다. 문제점이 하나 있음, 루프가 있으면 트리가 무한 이 될 수 있고, 해를 찾지 못할 수도 있음.

2.2 Graph Search

트리 서치에 explored set(=reached/closed) 를 추가해 중복 또는 루프를 차단하는 전략이다. 실전에서는 대부분 graph search로 여러 성질을 논한다 (이를테면 Completeness etc.)

• Frontier (open list) : 아직 확장 안 된 Leaf Node 집합
• Explored set (closed list) : 이미 방문한 상태

3. Uninformed Search (정보 없음, 문제 정의만 사용)

3.1 BFS: Breadth-First Search

• Frontier : FIFO Que
• 얕은 깊이 부터 확장
• Character
  • Complete? : If \(b, d\) finite, -> YES
  • Optimal : IF Step Cost가 모두 같을때만, -> YES
  • Time/Space : \(O(b^d)\)

3.2 DFS: Depth-First Search

• Frontier: LIFO Stack
• 현재 가장 깊은 노드 를 확장
• Character
  • Complete? : Generally -> NO
  • Optimal? : NO
  • Time/Space : Time = \(O(b^m)\) / Space = \(O(bm)\)

3.3 DLS: Depth-Limited Search

• DFS + depth limit \(I\) -> 무한루프 방지
• Character
  • Complete? : If \(I < d\), -> NO
  • Optimal? : NO
  • Time/Space : \(O(b^I)\)

3.4 IDS: Iterative Deepening Search

• DLS를 \(I = 0, 1, 2, ...\)로 반복 -> Complete + Optimal(if unit step cost)
• Time : \(O(b^d)\), = BFS’s
• Space : \(O(bm)\), = DFS’s
• 왜 좋은가? 자주 나옴

3.5 BS: Bidirectional Search

• Start 에서 한 번, Goal 에서 한 번, 동시에 탐색해서 중간에서 만나기
• Idea : \(b^{\frac{d}{2}} + b^{\frac{d}{2}} < b^d\)
• Prerequisites: goal state가 명확히 주어져야함 (그래야 골에서도 탐색을 진행하지)

UCS, Dijkstra: Uniform-Cost Search

• Step cost가 균일하지 않을 경우 BFS는 최적이 아니다. 이것을 보완하기 위해 만들어짐.
• Frontier : Priority Queue, Key = \(g(n)\). 즉, 누적 비용이 최소인 노드부터 확장
• Goal Test는 생성시점이 아니라 pop되어 확장될떄 해야 함 : 처음 생성된 goal 이 더 비싼 경로일수도 있음.
• Character
  • Complete? : If costs > 0, -> YES
  • Optimal? : If step cost \(\geq \epsilon > 0\), -> YES
  • 비용이 작은 경로들이 많으면, 탐색해야할 것들이 너무 많음.

4. Informed Search (Heuristic)

4.1 Heuristic \(h(n)\)

문제특화, goal까지 남은 비용을 추정한다. 항상 \(h(n) >0\) 이고, \(h(goal) = 0\)이다. Informed Search 는 앞서 언급했던 UCS, Uniform-Cost Search/ Dijkstra 와 거의 동일한데, PQ 의 Key 가 \(g\) 가 아니라, Evaluation \(f\) 가 됨.

(1) Admissible heuristic

• always 과소추정 : \(h(n) \leq h^* (n)\)
• e.g.: 직선거리 (실제 도로거리보다 작거나 같으니 admissible)

(2) Consistent heuristic

• Triangle Inequality: \(h(n) \leq c(n, a, n') + h(n')\)
• consistent \(\rightarrow\) admissible
• \(A^*\) 에서 graph search면, consistent가 필요하다.

(3) dominance

\(h_2(n) \geq h_1(n)\) for all \(n\), \(h_2\) is dominate \(h_1\) : 보통 더 좋음

(4) How to be heuristic?

• Relaxed problem의 최적비용은 원문제 최적비용의 under-approx -> admissible 근거
• Pattern database: 하위 문제 최적값들을 저장해서 휴리스틱으로 사용

4.2 Greedy Best-First Search

• goal 에 가까워 보이는 것부터 (실제로는 key 가 휴리스틱 기반)
• Character
  • If Graph Search, can complete, but not optimal

4.3 \(A^*\) Search

• \[f(n) = g(n) + h(n)\]
• Prerequisites
  • Tree Search : If admissible, Optimal
  • Graph Search : If consistent, Optimal
• f-contour concept: A*는 \(f\) 가 증가하는 순서로 확장
• pruning aspect: 최적비용인 \(C^*\)가 있다면, \(f(n) \geq C^*\) 인 노드는 확장하지 않는다.