Best first search, A* algorithm

- Best first search

- 휴리스틱에 따라 목표까지 가장 좋은 경로 상에 있다고 판단되는 노드를 우선 방문하도록 진행

Evaluation Function에 따라 다음에 확장 할 노드를 선택 (같은 값이면 무작위 선택)

다음에 확장할 노드가 Goal이면, 탐색 종료

- 한 노드로 부터 목표 노드까지 도달하기 위한 비용을 평가 함수로 함

출발노드에서 시작하여 목표노드까지 도달하는 최적의 경로를 탐색하는 것은 보장 되지 않음

- 방안 : A* algorithm

- A* algorithm

- 출발 노드부터 목표 노드까지의 최적경로를 탐색 

- f(n) = g(n) + h(n) -> 출발 노드에서 시작하여 노드 n을 거쳐서 목표 노드까지 도달하는 비용

g(n) : 출발 노드로 부터 노드 n까지의 경로비용 (현재 경로까지 확정 비용)

h(n) : 노드 n으로 부터 목표 노드까지의 경로비용 (현재부터 goal 까지 확정 비용)

- f(n)이 최소인 노드를 따라 탐색하면, 최소 비용의 경로를 탐색

- h(n)은 아직 탐색하지 않은 경로이므로 정확히 계산하기 어렵거나 불가능함 -> 경험적 규칙 사용

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

h*(n) : 노드 n으로 부터 목표 노드까지의 예측 경로 비용 (현재부터 goal 까지 추정 비용)

h*(n)의 예측이 얼마나 잘 되었는가에 따라 f(n)에 근접

- 경우 수

h* = h : 정확히 한 번에 최적화 된 해를 구함

h* < h : 한 번에 최적화 된 해를 구하기는 어렵지만, h*가 지정하는 상태(노드)를 방문한 후

실제로 underestimated 되었다는 것을 판단 후 다시 최적회 된 상태로 감

(언제가는 최적화 된 해를 구함(uniform cost search))

h* > h : 해를 찾지 못하며, BFS의 정의에 어긋남

- BFS와 A*의 차이점

- 현재 Node에서 다음 이동 가능 Node 후보를 선정시에 (f' = g + h' 일 때)

BFS는 모든 후보 중 h'가 가장 유리한 값을 선택함

A*는 모든 후보 중 f'가 가장 유리한 값을 선택함

- 20개의 Node 중에 A에서 B까지 최단 경로를 구하는 문제

- 위에서 A*는 f*(n)이 유리한 값으로 이동하였고, BFS는 h*(n)이 유리한 값으로 이동한 결과이다.

여기서 h*(n)은 n에서 b까지의 유클리디안 기법을 이용하여 구한 직선 길이이다.

- 그림을 보강해준 이연호 군에게 감사드립니다.