A* 알고리즘
Intro
- A* 알고리즘의 이해
A* 알고리즘
A* 알고리즘은 Dijkstra알고리즘을 확장하여 만들어졌고 주어진 출발 꼭짓점에서부터 목표 꼭짓점까지 가는 최단 경로를 찾아내는 그래프/트리 탐색 알고리즘이다.
이를 위해서는 각각 꼭짓점에 대한 평가함수를 정의해야 한다. 이를 위한 평가 함수 f(n)은 다음과 같다.
f(n) = g(n) + h(n)
- g(n) : 출발 꼭짓점으로부터 꼭짓점 n까지의 경로 가중치
- h(n) : 꼭짓점 n으로부터 목표 꼭짓점까지의 추정 경로 가중치1
예제 8-퍼즐 문제
f(n) = g(n) + h(n) 이며 g(n)은 움직인 횟수 h(n)은 제자리에 맞지않는 퍼즐 수이다.
댓글남기기