A* 알고리즘
Ⅰ.대표적인 탐색 알고리즘, A* 알고리즘의 개요
가. A* 알고리즘의 개요
- A* 알고리즘은 그래프의 시작점에서 도착점에 이르는 최단경로를 찾는 알고리즘으로 현재 위치한 정점에서 목적점에 이르는 잔여거리를 추정하여 다음 노드를 선택하는 휴리스틱 알고리즘
- 시작 노드에서 목적노드에 이르는 최단 경로를 찾아야 하는 경우 사용하는 알고리즘으로 최적우선탐색에 목적점에 이르는 추정치를 같이 사용하여 다음 정점을 선택하는 탐색 방법
나. A* 알고리즘의 특성
- A*는 시작으로부터 목표에 이르는 하나의 경로를 찾음
- A*는 최적의 경로를 찾음
- A*는 휴리스틱을 가장 효율적으로 사용
Ⅱ. A* 알고리즘의 평가함수 및 의사코드
가. A* 알고리즘의 평가함수
- 현재 노드에서 목적노드까지 가는 거리가 비슷하다면 시작노드에서 현재노드까지 온거리가 짧은 쪽이 전체적인 이동거리가 더 짧음
- A* 알고리즘이 관리하는 상태 리스트는 아직 조사하지 않은 상태들이 담긴 Open List이고 다른 하나는 이미 조사한 상태를 담은 Closed List로 구성됨
- 최단 거리 탐색 경로를 찾기 위해서는 평가 함수의 아래와 같은 2가지 사항을 고려해야 함
- 시작노드에서 현재노드(N)까지 온 실제의 최단거리(g(n)으로 표시)
- 현재노드(N)에서 목적노드까지의 실제의 최단거리(h(n)으로 표시)
- 이를 고려하여 만든 평가 함수 f는 f(n)=g(n)+h(n)임
- 하지만 h(n)는 정확하게 알지 못하는 거리 이므로
- h*(n):현재 노드(n)에서 목적노드 가지의 추정치를 사용하면
- 다음 정점을 선택하기 위한 A*알고리즘의 평가 함수는 f*(n)=g(n)+h*(n)