[인공지능] Informed Search 알고리즘 비교

[이 글은 고려대학교 윤수식 교수님 COSE361 강의 중간고사 내용 정리를 위해 작성한 글입니다.]

 

Informed Search란 heuristic한 정보를 바탕으로 하며, goal state에서 얼마나 가까운지를 고려하는 방식이다.

1. Greedy Search

그리디 알고리즘과 유사하게 그리디 탐색은 goal state에 가장 가깝다고 판단되는 노드를 가장 먼저 방문을 한다.

허나 거리가 가깝다고 해서 최적의 해는 아니기 때문에 최악의 경우 DFS와 같이 작동할 수 있다는 문제점이 있다.

위의 그림이 의도이지만,아래와 같이 작동 가능

 

 

Complete

DFS와 같이 무한 경로에 빠질 수 있으므로 Complete 하지 않다.

 

Optimal

최소의 값을 탐색하지 않으므로 optimal 하지 않다.

 

1.  A* Search

A* search는 실제 path cost와 heuristic하게 계산한 남은 path값의 합을 기준으로 가장 작은 경로를 탐색한다.

 

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

 

 

• f(n): 총 비용 (total cost)
• g(n): 실제 경로 비용 (actual path cost)
• h(n): 목표까지의 휴리스틱 비용 (heuristic cost to goal)

 

 

Optimality

Optimality에 대해 얘기를 하려면 먼저 admissible와 consistent 개념에 대해 알아야한다.

 

Admissible

$0\leq h\left ( n \right )\leq h^{*}\left ( n \right )$

 

heuristic하게 계산한 남은 path값이 실제 남은 값보다 작아야 된다는 것이 admissible의 정의이다.

 

Admissible하다면 A* tree search는 optimal하다.

 

증명은 다음과 같다. 

A는 optimal하고 b는 suboptimal point라고 가정을 하자.

h는 admissible heuristic 하여 $0\leq h\left ( n \right )\leq h^{*}\left ( n \right )$ 다음 식을 만족한다.

 

A가 B보다 먼저 탐색 됨을 증명하여야 한다.

 

먼저 A의 조상 노드 중 하나를 n이라고 명하자.

 

f(n) = g(n) + h(n)이여 f(A) = g(A) + h(A)이다.

h(A) = 0 이다.

$g\left ( A \right ) \geq g\left ( n \right )$이므로 f(A)$\geq  $f(n)이다.

 

f(A)와 f(B)의 경우 f(A) = g(A)+h(A), f(B)= g(B)+h(B)이다.

h(A) = h(B)= 0이다.

B가 suboptimal이라고 가정을 하였으므로, g(A)<g(B)이다.

 

$$ f(n) \leq f(A) < f(B)$$

수식이 성립하므로 최소 값으로 optimal한 알고리즘임을 알 수 있다.

 

Consistency

$h(A) - h(C) \leq \text{cost}(A \text{ to } C)$

consistent하다는 것은 heuristic하게 예상한 값이 실제 cost 보다는 작아야 한다는 것이다.

 

모든 경로 중에서 항상 평가 함수 값이 작은 경로부터 차례대로 확장하므로 그래프에서는 consistent 하다면 optimal 하다.