에이스타탐색 A* Search

A* Search

---

전혀 새로울 것이 없는 탐색 방법이다.

2018/05/04 - [Artificial intelligence] - Uninformed Search and Informed Search

2018/05/04 - [Artificial intelligence] - 탐욕 탐색 Greedy Search

실제 거리 + 예측거리식을 이용하는데 이 두가지를 섞은 것이 A* Search이다.

Combining UCS and Greedy

---

- Uniform-cost orders by path cost, or backward cost  g(n)

- Greedy orders by goal proximity, or forward cost  h(n)

A* Search orders by the sum: f(n)=g(n)+h(n)

만약 a에서 다음 노드를 확장해야 한다고 할 때, a와 인접한 노드 e, d, b의 f값을 측정하여 확장 노드를 택할 것이다.

각 값을 구해보자.

- f(e) = backward cost g(n) + forward cost h(n) = 9 + 1 = 10.

g(e)는 왜 9인가? g(e)는 backward cost이기 때문에 시작 노드인 S노드에서 다음 노드인 e노드까지의 Real Cost를 모두 더한 값이다.

h(e)는 왜 1인가? h(e)는 forward cost이기 때문에 다음 노드인 e의 예측거리만을 보면 되기 때문.

- f(d) = 4 + 2 = 6

- f(b) = 2 + 6 = 8

이 셋 中 가장 작은 값인 f(d)를 선택하여 다음 노드로 d를 확장한다.

Is A* Optimal?

---

A*는 상황에 따라 Optimal하거나 Optimal하지 않다.

바로 휴리스틱 값이 Cost 값보다 높을때(h(x)>cost) Optimal 하지 않다.

반드시 Cost 값보다 h(x)가 작아야 Optimal 하다.

위 이미지를 보면 실제 Cost만을 고려한다면 S에서 G로 가는 방법중 가장 가까운 거리는 S -> A -> G(cost 4) 이다.

하지만 A*를 사용하면 S -> G(cost 5)를 리턴하는데 이는 A노드에서 휴리스틱을 실제 cost보다 훨씬 높은 6으로 줘버렸기 때문이다.

Admissible Heuristics

---

휴리스틱 h(n) 값이 실제 값 h*(n) 보다 작을 경우 Heuristics이 Admissible 하다고 한다.

Heuristics이 Admissible 하다면 A* Search는 Optimal 한 결과를 리턴한다.

이 h(n)에 h*(n)보다 작은 값을 부여하기 위해 앞서 말한 맨하탄이나 유클리디안을 이용한다.

Properties of A*

---

UCS vs A* Contours

---

A*가 옵티말 하다면 UCS도 옵티말하다. 

A*=UCS + Greedy     ==>    UCS=A*-Greedy

더 나아가 A*에서 Greedy (휴리스틱)값을 제거하면, 다른 말로 휴리스틱 값이 0이라면 UCS = A*가 성립한다.

if all h(x) = 0 : UCS=A*-Greedy    ==>    UCS=A*