A* algorithm

A* Algorithm

• A* 알고리즘은 그래프 탐색, 경로 탐색 알고리즘 입니다.
• 임의의 노드 $v_i$ 에 대하여, 평가함수 $F(v)$ 를 아래와 같이 정의합니다.

$$F(v_i) = g(v_i) + h(v_i)$$

• 함수 $g$ 와 함수 $h$ 는 다음을 의미합니다.
  • $g(v)$: 시작점으로부터 $v$ 까지 경로의 비용
  • $h(v)$: $v$ 로부터 도착점까지의 비용(추정치)
• A* 알고리즘은 이 평가함수 $F(v)$ 로 얻은 비용에 대해, Best-First Search 방식으로 시작점으로부터 도착점까지 가장 적은 비용이 드는 경로를 찾아냅니다.

• $h(v)$ 함수로 비용의 추정치를 구하는 직관적인 방법은 아래와 같습니다.
  • 유클리드 거리
  • 맨하탄 거리

• Shortest Path 를 찾는 다른 알고리즘으로 Dijkstra 가 있습니다.
• A* 와 Dijkstra 는 도착점(Goal)에 차이가 있습니다.
  • A* 는 단 하나의 도착점을 향해 탐색합니다.
  • Dijkstra 는 출발점으로부터 다른 모든 Vertex 에 이르는 최단경로를 구합니다.
• Dijkstra 는 사실 A* 알고리즘에서 $h(v) = 0$ 으로 두었을 때와 같습니다.

8-puzzle Problem

• (그림 추가 예정)
• $3\times3$ 크기의 보드가 있을 때, 1에서부터 8까지의 블럭이 끼워져 있는 퍼즐 보드의 정답을 찾는 문제입니다.
• 각 보드의 상태를 트리구조로 두고 문제를 풀 수 있으며, 평가함수에 관한 함수를 아래와 같이 정의합니다.
  • $g$: 트리의 깊이
  • $h$: 정답과 현재 보드 상태의 mismatch 갯수
• $F=g+h$ 의 값이 최소인 노드를 선택하다보면, 정답으로 향하는 최소 경로를 구할 수 있게 됩니다.