목차
A* 알고리즘
Ⅰ.대표적인 탐색 알고리즘, A* 알고리즘의 개요
가. A* 알고리즘의 개요
나. A* 알고리즘의 특성
Ⅱ. A* 알고리즘의 평가함수 및 의사코드
가. A* 알고리즘의 평가함수
관련 문서
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)
관련 문서
정보보안기사