Informed Search ( A*, Greedy Search)

Uninformed VS Informed 

 

Informed Search에 대해 알아보기 앞서 Uninformed 와의 차이점을 알아보겠습니다. 

 

Uninformed의 경우 경로를 선택할 때 start에서의 거리를 기준으로 합니다.  하지만 Informed 의 경우 goal까지의 거리를 기준으로 경로를 택하게 됩니다. Uninformed 는 오직 그래프에 나타난 정보(시작점에서의 비용 또는 거리)만 이용하며 goal까지의 거리를 알 수 없습니다. 

 

Informed의 경우 휴리스틱 heuristic과 평가 함수 evaluation function를 이용한 정보를 추가적으로 이용해 최적 경로를 찾게 됩니다. 대표적인 Informed Search 인 Greedy search와 A* 에 대해 알아보겠습니다. 

 

 

Greedy Search

 

Greedy 는 아시다시피 현재 할 수 있는 가장 좋은 선택을 할 뿐 이 선택이 미래에 어떤 영향을 끼칠지는 신경 쓰지 않는 방법입니다. 하지만 이전의 uninformed 방식과는 다르게 heuristic h(n)을 이용해 현재 지점에서 goal까지의 거리 비용을 계산합니다. 

 

다시 한번 저번 글의 내용을 되살려 complete와 optimal, time, space에 대해 언급하자면 탐욕 서치가 늘 그렇듯이 complete는 어쩌다 가끔? 또는 not always라고 할 수 있습니다. 당장 좋아 보이는 것만 쫒아가다 목적지가 저 멀리 가버리는 상황이 발생하기 때문이죠.

 

그리고 optimal 역시 보장되지 않습니다. 일단 해답을 찾았다면 그게 끝입니다. 이후에 더 나은 경로가 있는지 알아보지 않습니다. 예를 들어 쇼핑을 하러 갔습니다. 나이키 맥스 97 올검을 사러 갔습니다. 처음으로 방문한 매장에 있는 거 아니겠습니까. 가격은 199,000원입니다. 현명한 소비자라면 인터넷에 더 싸게 파는 상품이 있는지 다른 백화점에 할인을 하는지를 알아보고 최저가를 선택할 텐데 greedy 이 자식은 고민 없이 바로 199000원 정가 주고 사버립니다. 

 

time의 경우 greedy의 장점이 뭡니까? 바로 빠른 선택입니다. 고민 없이 제일 좋아 보이는 길을 후딱 선택해버리는, 다른 매장, 인터넷 쇼핑에 더 싸게 파는 제품이 있는지 조사할 필요가 없으니깐 시간을 절약할 수 있습니다. 그래서 보통 다른 탐색들이 O(b^m)의 시간이 걸리는데 반해 greedy는 최악의 경우 맥스 97 사러 갔는데 제고가 롯데 백화점도 없고 현대 백화점도 없고 신세계 백화점도 없고 마지막으로 간 나이키 매장에 있게 될 경우가 되어서야  O(b^m) 의 시간이 걸립니다. 만약 좋은 heuristic 이 존재한다면 시간을 더 단축할 수 있습니다. 

 

space의 경우 time과 마찬가지로 O(b^m)입니다. 왜냐면 모든 경로를 메모리에 저장하기 때문이라고 나와 있는데 처음에는 이해가 안됐습니다. 해답이 나오면 이제 탐색을 멈춰버리는데 O(b^m) 보다 적어야 하는거 아닌가 생각했는데 역시나 최악의 경우, 마지막으로 방문한 곳에서 해답을 찾는다면 모든 경로를 다 방문하고 저장하니깐 O(b^m)의 공간을 차지하게 됩니다. 

 

 

 

 

 

 

 

A* Search

 

 

그저 당장 눈앞에서 목적지까지 최소비용, 거리만 따지는 greedy Search의 neither optimal nor even always complete의 단점과 start에서 최소 비용, 거리만 따지는 Uninformed의 complete and optimal but expensive의 단점을 보완한 탐색방법입니다. 

 

핵심 특징은 heuristic 을 이용해 종합적으로 경로를 진단하자!입니다. 다시 한번 언급하면 Uninformed는 from start to current loaction의 비용 그리고 greedy는 from current location to goal을 따지는데 A*는 그냥 from start to current location and from current location to goal까지의 비용을 모두 고려해 보자입니다. 

 

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

g(n) = start 에서 n까지의 실제 비용입니다. 

h(n) = n 에서 goal까지 예상되는 비용입니다. 

f(n) = start 에서 n을 거처 goal에 가는 비용입니다. 

 

A* search의 Optimaliy 에 대해 알아보겠습니다.  A*가 complete와 optimal 되기 위해서는 2가지 전제조건이 있습니다. 

 

- The heuristic must be admissible.

- The costs along a given path must monotonic or consistent

 

The heuristic must be admissibe 하다는 의미는 내가 현재 알고 있는 경로의 비용보다 더 낮거나 동등한 비용의 경로를 제공할 수 있어야 한다는 의미입니다. 

 

h(n) = 현재 경로 n에서 목적지 까지의 예상되는 비용.

h*(n) = 현재 경로 n에서 목적지 까지의 실제 비용. 

 

If h(n)<=h*(n) for all n then the heuristic is admissibe.

 

두번째로 The costs along a given path must monotonic or consistent.라는 의미는 현재 경로 n에서 인접한 지역  n'을 방문한 비용과 n'에서 목적기까지 가는 경로에 대한 예상되는 비용의 합이 h(n)과 같거나 크게 될 경우입니다.

 

if h(n) <= c(n,n') (n에서 n'까지 가는데 걸린 비용 )+ h(n'), then monotonic or consistent

 

h(n) 이란 n에서 목적지 까지 디렉트로 가는 경로입니다. 근처 한 군데를 더 지나고 가는 경로의 비용보다 낮아야 하는 것은 당연해 보입니다. 현재 위치에서 집으로 가는 거리가 스타벅스를 들려서 커피 한잔 사서 가는 거리보다 짧아야 monotonic or consistent 하다고 말할 수 있습니다.

 

h(n') 은 h(n) 의 경로를 잠시 이탈했다가 다시 재진입해서 가는 것입니다. 출발지가 조금 달라졌다고 정말 새로운 경로를 이용하게 되는 것은 문자 그대로 단일적이거나 일치하는이 될 수 없습니다. 

 

마지막으로 A* 의 complete, optimal, time, space 에 대해 알아보겠습니다. x는 노드의 개수이며  f* 는 경로의 실제 비용 f(n) 은 휴리스틱을 통해 가게 되는 비용입니다. 

 

만약 노드의 숫자가 무한이 아니면서 f(n) 이 f* 이하 일때 complete와 optimal 은 yes입니다. f(n) 이 실제 비용보다 낮다는 것은 목적지로 가는 더 낮은 비용의 경로를 찾았다는 것이기 때문입니다. time과 space는 O(x)입니다.  A* 는 uninfromed search처럼 여기저기 갔다 오면서 최적의 경로를 찾는 게 아니라 이미 h(n)을 통해 목적지까지 최적화된 경로를 알 수 있기 때문입니다. 최악의 경우 모든 x를 한 번씩 거쳐가게 되고 모든 x가 메모리에 다 저장됩니다. 그리고 이 x는 얼마나 좋은 휴리스틱을 가지고 있느냐에 따라 정해집니다.

 

이번 글에서는 infromed search 에서 greedy serach와 A* search에 대해 간략히 알아봤습니다. 하지만 A*는 훨씬 더 많은 내용이 있기에 다음 글에서 더 심화적으로 다뤄보려 합니다.