[인공지능] Informed Search

* 정보이용 탐색 (informed search)

• State space가 매우 커질 경우 → uninformed search가 효과적이지 않음 (메모리, 시간 비효율)

• 맹목적 탐색으로 해를 찾기 어렵거나 시간이 오래 걸리는 문제

• 상태 공간의 정보를 이용하여 모든 노드를 탐색하지 않고 해를 찾는 방법

예시) 휴리스틱 탐색 (heuristic search), 언덕 오르기 방법, 최상 우선 탐색, 빔 탐색, A* 알고리즘 등

 

• 탐색 공간에서의 해 (solution) 찾기

- Global maximum

- Local maximum

• Local maximum을 찾는 알고리즘

- 언덕 오르기 방법(hill climbing method)

- Simulated annealing

- Local beam search

- Genetic algorithms

- Best-first search

• Global maximum을 찾을 수 있는 알고리즘

- A* search

 

* 언덕 오르기 방법(hill climbing method)

- 지역 탐색(local search), 휴리스틱 탐색(heuristic search)

- 현재 노드에서 휴리스틱에 의한 평가값이 가장 좋은 이웃 노드 하나를 확장해 가는 탐색 방법

- 현재 노드 선택 -> 현재에서 가장 높은 값을 갖는 이웃을 선택하여 현재보다 값이 크면 현재 노드를 이웃 노드로 선택 -> 전 과정을 반복하되, 이웃 노드가 현재 노드보다 크지 않으면 종료

- 국소 최적해(local optimal solution)에 빠질 가능성 있음

hill climbing method 예시

Local maxima: 전역해를 찾아주는 것이 아니라 지역적으로 최적해를 찾아준다 Ridges (산등성이) Plateaux: 해를 찾을 때, 변화가 없는 평평(shoulder/plateau)한 값에 빠질 때 해를 찾기 어렵다

 

* Best-first search 방법

- 일반적인 트리 탐색 (tree-search) 또는 그래프 탐색 (graph-search) 알고리즘으로 평 가 함수 h(n)에 따라 탐색을 확장

- Heuristic function : f(n) = h(n)

- 특징 : Depth-first search와 유사한 방법, 현재에 가장 좋은 것으로 선택하는 방법

- Non-optimal, Incomplete

- 확장 중인 노드들 중에서 목표 노드까지 남은 거리가 가장 짧은 노드를 확장하여 탐색

- 남은 거리를 정확히 알 수 없으므로 heuristic 사용

BFS의 예시

 

* A* 탐색 알고리즘

- estimated total cost 𝑓' 𝑛 을 최소로 하는 노드로 확장해 가는 방법

- 𝑓(𝑛) ∶ 노드 n 을 경유하는 전체 비용

- 현재 노드 n까지 이미 투입된 비용 g(n)과 목표 노드까지의 남은 비용 h(n)의 합

• 𝑓 (𝑛) = 𝑔(𝑛) + ℎ(𝑛)

- ℎ(𝑛) : 남은 비용의 정확한 예측 불가

• ℎ'(n) : ℎ(𝑛) 에 대응하는 휴리스틱 함수(heuristic function)

𝑓'(𝑛) ∶ 노드 n 을 경유하는 추정 전체 비용

• f '(𝑛) = 𝑔(𝑛) + ℎ'(𝑛) 

- optimal, complete

: ℎ(𝑛) 이 admissible heuristic 이면 optimal // Admissible이란? 주어진 state에서 goal에 도달하기까지 비용이 높게 추산되지 않음, ℎ (𝑛) ≤ 목적지까지의 비용

A* 알고리즘의 예시