[인공지능] 5주차: Heuristic search

Best-First Search가 대표적임

탐색 알고리즘 = expand 할 수 있는 여러 노드 중 어느 노드를 먼저 expand할 것인가?

 

 

Best-First Search

평가 함수(Evaluation function, $f(n)$)로 각 노드(여기서는 '상태'에 해당)를 평가해 더 좋은 노드르 확장

확장할 수 있는 노드를 평가함수에 넣고 평가치가 가장 높은 상태를 확장

 

Priority queue(= Sorted queue)로 구현한다.

 

평가 함수는 '지식'이다. 평가 함수는 주어진다. 인간이 줄 수도 있고 기계가 학습할 수도 있다.

 

 

Greedy Best-First Search

$f(n)$ = heuristic function $h(n)$

좁은 의미의 heuristic search로 보는 경우도 있다.

$f$에 주면 다시 $h$로 전달되어 평가됨

 

평가치는 비용으로 해석할 수도 있고,

현재부터 목표까지 가려면 얼만큼의 비용(거리)가 남았는지 예측한 값으로 볼 수도 있다.

-> 값이 작을수록 좋은 것이므로 값이 작은 노드부터 확장

 

Complete: N (루프에 빠질 수 있다)

Iasi에서 Fagaras로 간다고 할 때 비용이 적은 노드만 선택하면 Iasi와 Neamt만을 왔다갔다 하는 루프에 빠진다.

 

Time: $O(b^m)$

Space: $O(b^m)$

Optimal: N

 

* Notation

$b$: 노드

 

 

A* Search

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

 

$g(n)$: 출발 상태부터 후보 상태까지의 비용

$h(n)$: 후보 상태 노드에서 목표까지의 비용

$f(n)$: 총비용

 

$g(n)$과 $h(n)$ 모두 최단 경로.

단 $g(n)$은 이미 지나온 경로를 통해 알아낼 수 있지만 $h(n)$은 아직 미지의 값이다.

따라서 $h(n)$은 별도의 정보, 경험적 지식을 통해 예측된 값이며,

 

$f(n)$은 시작부터 현재 노드를 지나는 solution들 중 가장 비용이 적게 드는 경로의 비용을 예측한 것이 된다.

매 상태마다 다음 노드를 선택한다.

 

heuristic function($h(n)$)에 영향을 많이 받는다.

 

Complete: Y

Time: $O(b^d)$

Space: $O(b^d)$ (모든 노드가 memory에 남는다)

Optimal: Y

 

 

 

 

Admissible Heuristic

항상 $h(n) \leq h^*(n)$, 즉 $h(n)$은 항상 실제 비용보다 적다.

 

$h(n)$이 admissible하면, 즉 항상 실제비용보다 적은 비용으로 예측하면 A* Search는 항상 최적 해를 보장받는다.

 

물론 $h(n)$이 실제보다 높게 예측해도 최적 해를 찾을 수도 있다. 그러나 항상 그렇진 않다.

over-estimate하면 실제로는 최적 해임에도 비용이 많이 든다고 예측하기 때문에 최적이 아닌 다른 해를 찾을 수 있다.

 

예를 들어 직선거리는 항상 admissible 하다.

 

 

Dominance

모든 $n$에 대해 $h_2(n) \geq h_1(n) \geq h^*(n)$이면

$h_2$ 가 $h_1$에 비해 더 우월하다($h_2(n)\;\;dominates\;\;\h_1(n)$)고 한다.

 

즉 탐색에서 $h_2$는 $h_1$보다 더 '좋다'(= 더 효율적으로 탐색한다).