Chapter 3. Informed Search

Greedy Best-First Search

Evaluation Func & Heuristic Func

1. Evaluation func f(n)
   1. node n의 estimated cost
2. Heuristic func h(n)
   1. node n에서 goal state로 가는 가장 저렴한 비용의 추정치
   2. root-finding problem에서 각 도시별 직선거리 함수

Greedy Best-First Search

1. 정의: best-first search의 일종 → h(n) value가 가장 적은 노드를 확장
   1. table을 유지하는 경우 그래프 (중복을 고려)
   2. 없애는 경우 tree search (중복을 고려하지 않음)
2. 성능 평가
   1. Completeness → 사이클 발생
      1. Not complete: tree-like search
      2. complete: graph search
   2. Not cost-optimal
   3. Time Complexity: O(b^m)
   4. Space Complexity: O(b^m)

A* Search

1. 정의: f(n) = g(n) + h(n)을 evaluation function으로 이용
   1. g(n): n까지 오는 데 비용
   2. h(n): n부터 goal까지 가는 데 추정되는 비용
2. Admissible Heuristic Function
   1. goal에 도달하기 위한 비용을 절대 overestimate하지 않음
   2. h(n) <= h*(n) : h(n)은 실제 값
   3. admissible heuristic function을 이용한다면 A* search는 cost-optimal하다.
3. Consistent Heuristic Function
   1. consistent: 모든 노드 n과 a라는 행동으로 생성된 자식 n’이 있을 때
   2. h(n) <= c(n,a,n') + h(n') 성립
   3. consistent heuristic function을 이용한다면 A* search는 cost-optimal하다 → 모든 consistent heuristic은 admissible하다.
4. Search contours
   1. A*는 가장 적은 f-cost를 가진 frontier 노드를 확장하므로 등고선이 커지면서 cost가 점점 커지는 형태이다.
   2. 좋은 휴리스틱을 가졌다면, 등고선은 점점 goal state에 가까워질 것이며 최적 경로에 가까워질수록 더 좁아질 것이다.
5. Optimally Efficient → C* : optimal cost
   1. surely expanded: f(n)<C*
   2. depends: f(n)=C*
   3. never expended: f(n) > C*
6. Weighted A* Search
   1. 정의: C와 WC*사이의 cost를 가지는 해답을 찾는 것
   2. f(n)=g(n)+W*h(n)
   3. Suboptimal search techniques
      1. bounded suboptimal search: 실제 optimal cost의 1/2배 ..
      2. bounded-cost search: 실제 cost는 모르고 얼마 안에 도달하는 경로 찾기
      3. unbounded-cost search
      4. beam search: 메모리는 적게 유지 → 가장 좋은 score인 것만 유지하고 나머지는 가지치기
7. 성능 평가
   1. Complete
   2. Cost-optimal
   3. Time-complexity <= O(b^d)
   4. Space complexity <= O(b^d)

Iterative-Deepening A* Search

1. 정의 (IDA*)
   1. iterative deepening search + A* Search
   2. 이전 반복에서 cutoff를 초과하였던, f-cost가 가장 작은 임의의 노드를 cutoff → 기준보다 크지 않았다면 계속 내려감
2. 특징
   1. f-cost가 모두 정수일 때 잘 작동
   2. f-cost가 모두 다른 노드일 때, 반복 숫자가 결국 state수와 같아질 수 있다.

Recursive Best-First Search

1. 정의 (RBFS)
   1. recursive depth-first search + best-first search
   2. f-limit을 현재 노드가 초과한다면 다시 감아 내려가서 alternative path로 이동
2. 진행 과정
   1. 일단 처음 limit = 무한대
   2. 다음 경로 중 가장 작은 cost인 쪽을 선택, limit은 두 번째로 가장 작은 값으로 변경
   3. 내려가서 limit과 cost의 값을 비교 → cost가 limit보다 크면 해당 cost를 limit으로 변경하고, limit과 같은 cost를 가졌던 node를 확인
3. 성능 평가
   1. Complete
   2. Cost-optimal
   3. time complexity <= O(b^d)
   4. space complexity <= O(bd)
      • 지나치게 적은 메모리 사용 → 계속 같은 state를 반복하여 탐색

Simplified Memory-Bounded A* Search

1. 정의
   1. A* search를 메모리가 꽉 찰 때까지 진행
   2. 메모리가 꽉 찼다면 f-cost가 가장 큰 worst leaf node를 버림
   3. 잊어버린 노드의 값을 다시 부모에게 전달
2. 성능 평가
   1. Complete
   2. Cost-optimal
   3. time complexity <= O(b^d)
   4. space complexity <= O(b^d)