[인공지능기초] Tree Search(Informed Search)

해당 글은 아래의 2가지를 다룬다.
1. Informed Search(Heuristic Search)란?
2. Informed Search의 종류

- Informed Search(= Heuristic Search)란? 

: 문제 정의 외에 추가적인 정보를 가진채 검색하는 알고리즘

-> Informed Search는 Uninformed Search의 단점을 극복하기 위해 나온 탐색법, 더 효율적임

-> Informed Search의 기본적인 접근 방법은 Best-First Search 이다.

 

* Best-First Search는 평가 함수 F(n)을 기반으로 한 Tree/Graph-Search의 확장이다.

이는 Uninformed Search의 Uniform-Cost Search와 유사한데, Uniform-Cost Search는 현재 노드에서 탐색하는데 가장 비용이 적게 드는 노드로 탐색을 진행한다. Beat-First Search는 비용계산을 g(n) 대산 f(n)을 사용하는 것이다.

 

- Informed Search의 종류

1) Greedy Best-First Search

Greedy는 '탐욕적인'이라는 뜻으로, 현재 상황에서 가장 좋아보이는 걸 선택하여 최적인지 아닌지를 항상 확인해줘야 하는 알고리즘이다. 여기서 평가함수가 오직 h(n)으로 구성된다. ( f(n) = h(n) )

h(n) = 현재 노드와 목표 노드 사이의 직선 거리 = SLD

Arad 도시 -> Bucharest 도시 까지 이동하는 예시

SLD가 가장 작은 것으로 계속 이동했을때

 

- 평가 : Complete(X), Optimal(X)

- 시간&공간복잡도 : O(b^m)

* m : maximum depth of the search space 

 

 

2) A* Search

A* Search는 f(n) 함수로 h(n) 뿐만 아니라 g(n)을 사용한다.

( f(n) = g(n) + h(n) )

 

 

 

- A* Search의 특징

   -> Tree-Search 일 때, h(n)이 admissible 하면 Optimal 해진다.

   -> Graph-Search 일 때, h(n)이 Consistent 하면 Optimal 해진다.

- 평가 : Complete(O), Optimal(O)

- 시간복잡도 : 휴리스틱 함수에 근거하여 Exponential(지수적)하다.

- 공간복잡도 : O(b^m)

 

 

[참고자료]

https://com24everyday.tistory.com/304

[인공지능] 3. Informed Search