[인공지능] Ch13 Informed Search

Search Heuristics

휴리스틱이란, 목표에 얼마나 가까운 상태인지 추정하는 함수를 의미한다.
ex) 맨해튼 거리, 경로를 위한 유클리드 거리

팩맨을 예시로 들자면,

팩맨의 위치에서 목표까지의 거리는 위의 빨간색 선과 달리 벽을 뚫지 않고 구불하게 이동해야 할 것이다.

 

그렇다면 추정값은 유클리드 거리를 이용해서 구할 수 있다. 그게 바로 빨간색 선이다.

목표까지의 유클리드 커리를 반환하는 함수가 휴리스틱인 것이다.

 

Greedy Search

greedy search는 목표와 가까워 보이는 노드부터 확장해 나가는 방법이다.

 

Optimal하냐고 물어본다면 그렇지는 않다. 

당장 현재 노드로부터 가까워 보이는 노드들을 선택해 나가기 때문에 최적해가 될 수 없는 건 어찌보면 당연하다.

 

여기서 휴리스틱은 각 상태에 대해 가장 가까운 목표까지의 거리 추정치를 반환한다.

최악의 경우, 잘못된 DFS처럼 결과가 나올 수 있다.

 

A* Search

A*는 Greedy Search 의 heuristic ℎ(𝑛)과 UCS 의 path cost 𝑔(𝑛)을 합친 것이다.

위 그림을 보면 이해가 갈 수 있을 것이다.

빨간색은 Greedy Search 경로를 나타낸 것이고, 파란색은 UCS 경로를 나타낸 것이다.

핑크색은 A* Search이다.

 

이를 𝑓(𝑛) = 𝑔(𝑛) + ℎ(𝑛)로 표현할 수 있다.

 

그리고 여기서 A*의 특징을 확인할 수 있는데, 뒤로 갈수록 𝑔(𝑛)는 커지고 ℎ(𝑛)는 작아지고 있다.

(초반에는 ℎ(𝑛)의 영향이 크고, 후반에는 𝑔(𝑛)의 영향이 큰 것이다.)

 

그러면 우리는 goal을 enqueue할 때 멈춰야 할까?

아니다. fringe가 goal에서 dequeue할 때만 멈춰야 한다.

 

그 이유는 내가 위 그림에서 필기한 것으로 확인할 수 있다.

 

파란색으로 표시한 것은 optimal하지 않다.

즉, fringe에 적은 비용의 노드가 남아있다면 그 노드를 거치는 경로가 optimal일 가능성도 배제할 수 없다는 것이다.

 

UCS vs. A* Contours

왼쪽은 UCS의 탐색 윤곽이다. 모든 방향에서 동일하게 탐색을 하고 있는 것을 확인할 수 있다.

반면 오른쪽은 A*의 탐색 윤곽이다. 주로 goal를 향해 확장하고 있어 훨씬 효율적이다.