AI Informed search, Greedy Best-first Search, A* Serach

Informed search

지금까지의 Uninformed search 와는 달리 문제 정의 이외의 정보를 활용하여 더 효율적인 검색을 하는 방법입니다.

 

Best-first search

트리 내 노드에서 evaluation function f(n)에 의해 cost가 가장 적은 노드를 판별하여 해당 노드를 먼저 탐색합니다.

 

f(n) 은 heuristic function h(n)을 포함하고 있습니다.

h(n)은 n에서부터 goal state 까지의 최소 비용을 예측하는 함수입니다.

가령 예를 들어 Romania 문제에서 도시간의 비용이 지도에 주어졌지만 h(n)으로는 도시 n에서부터 goal 도시까지의 직선거리를 사용할 수 있을 것입니다. 지금부터 이를 hSLD라고 부르겠습니다. (SLD = Straight-Line Distance)

 

Greedy Best-First Search

f(n) = h(n) 으로 오직 heuristic 한 추정치만을 사용하여 검색을 진행하는 방법입니다.

이는 비슷한 문제를 풀어본 경험을 필요로 합니다.

 

평가

• Completeness

• Graph version : Yes

• Tree version : No ( DFS )

• Optimal : No

• 결과의 최적은 아니지만 탐색 비용의 최적은 만족함 : 최적의 답이 아니더라도 답을 찾는 데에 있어서 최소한의 비용으로 찾아냄

• Time complexity : O(b ^ m)

• Space complexity : O(b ^ m)

 

A* Search

Best-first search 알고리즘 중 가장 유명한 알고리즘입니다.

f(n) = g(n) + h(n) 으로 g(n)은 start state 에서부터 n 까지의 실제 cost 를 말하며, h(n)은 n에서부터 goal state 까지의 최소 코스트의 추정치를 말합니다.

A* 탐색은 UNIFORM-COST-SEARCH 와 동일하게 구현하지만 priority queue에 들어가는 가중치가 g(n)이 아닌 f(n) = g(n) + h(n) 이라는 것만 다릅니다.

 

A* search의 complete, optimal 조건

• Admissibility

• h(n) 은 goal state 까지의 비용을 절대 과대평가 하지 않는다.

• 즉 추정치는 실제 측정값보다 더 크게 추정해서는 안된다.
  
  

• Consistency

• h(n) <= c(n, a, n`) + h(n`) 을 만족한다.

• c(n, a, n`) = n →  n` 으로 가는데에 action a를 통해 갔을 때 필요한 비용

• 즉 추정치는 실제 측정값보다 더 크게 추정해서는 안되며 goal에 다가갈수록 그 추정치는 작아진다.

• Consistency → admissible (O)

• Admissible → Consistency (X)

• Consistency 가 Admissible 보다 더 강력한 조건임

Heuristic 한 h(n)은 문제에 specific 하기 때문에 다른 문제에 활용이 어렵습니다.

 

h(n) 이 consistent 하다면 A* search 는 optimal 하다.

A* search에서 frontier의 노드가 pop 되는 순간 해당 노드의 path cost는 최적입니다. 그리고 이를 반복하여 goal state node가 expand 되는 순간 해당 노드의 path cost는 최적이기에 A* search는 최적의 답을 찾습니다. 따라서 어떤 node 가 frontier에서 pop 될 때 해당 노드의 cost가 최적이라는 것을 증명하겠습니다.

 

딸림정리 : h(n)이 consistent 하다면 f(n)은 절대 작아지지 않습니다.

딸림정리 증명

consistent 의 정의 : h(n) <= c(n, a, n`) + h(n`)

f(n`) = g(n`) + h(n`) = g(n) + c(n, a, n`) + h(n`) >= g(n) + h(n) = f(n)

따라서 f(n) <= f(n`) <= f(n``) <= … 

 

증명

모순에 의한 증명으로 증명하겠습니다. A* search에서 모든 노드는 unexplored -> frontier -> expored 순으로 들어가게 됩니다. A* search에서 노드 n이 frontier에서 expand 되는 순간에 n으로 가는 더 최적의 path인 n`이 있다고 가정합니다. 그렇다면 f(n) >= f(n`) 이라는 것이며 이는 딸림정리에 의해 n보다 먼저 선택되었어야 합니다. 따라서 이는 모순이며 n 은 최적의 path cost 를 가진 노드입니다.

 

Contours by f(n) in a State Space ( state 공간의 등고선)

f(n)의 등고선이 의미하는 바는 다음과 같습니다. A* Search 가 수행될 때 작은 등고선부터 차례로 탐색해나가는데 해당 등고선 내부의 노드를 모두 탐색한 뒤에 다음 등고선으로 넘어가기 때문에 등고선이 뾰족하고 좁으면 더 적은 노드를 탐색한다는 것입니다.

 

Uniform-cost search 는 h(n) 이 0이므로 등고선이 동심원을 그리게 됩니다.

왜냐하면 heuristic 한 h(n) 이 있기에 goal state와 start state 간의 path cost 차이가 적게 나게 되지만 h(n) 이 0이라면 실제값인 g(n)만으로 등고선이 그려지기 때문에 start state에 가까울수록 0에 가깝고, goal state에 가까워질수록 값이 커지게 되기 때문입니다.

 

h(n) 이 정확한 추정일 수록 등고선은 goal state 쪽으로 늘어나며 optimal path 쪽으로 더 뾰족하고 날카롭게 변하게 됩니다.

C* = optimal cost

A* 탐색은 모든 노드를 f(n) < C* 가 되도록 expand 합니다.

A* 탐색은 C*보다 작거나 같은 f(n)의 노드 수가 유한하다면 Complete 합니다.

Optimal 알고리즘 중에서는 A* 알고리즘이 가장 빠릅니다. f(n) < C* 인 노드를 모두 탐색하기 때문에 Optimal 합니다. f(n) < C* 이여도 탐색하지 않는다면 빠르기는 더 빠르겠지만 Optimal 을 보장할 수는 없습니다.

 

Computational Complexities of A* Search

h* = 실제 cost

 

Absolute error A = h* - h

Relative error e = (h* - h) / h*

 

Time complexity = O(b ^ A), O(b ^ ed)

Effective branching factor : b ^ e    실제적인 branching factor 로 시간복잡도를 계산 할 때 더 유의미한 결과를 낸다하여 붙여진 이름입니다.

 

Space complexity = O(b ^ m) 으로, 시간복잡도에 비하면 매우 나쁜 수준입니다.