오늘 배운 것
- A* 알고리즘
A* 알고리즘
F = G + H
A* 알고리즘은 다익스트라 알고리즘 (Dijkstra's Algorithm) 에서 휴리스틱이 추가된 알고리즘이다.
다익스트라 알고리즘이 모든 방향, 가능성을 열어두고 최단 거리를 탐색한다면
A* 알고리즘은 도착 위치까지의 거리를 예상(Heuristic) 하여 도착점 방향으로 탐색한다.
즉, A* 알고리즘은 도착 위치를 알고 있어야 한다.
휴리스틱 (Heuristic)
휴리스틱은 간단히 말하자면 추정치로,
현재 위치에서 도착 위치까지의 거리를 예상한 값이다.
A* 알고리즘에서 측정하는 휴리스틱에 따라 탐색 방향과 성능이 달라지는데,
크게 두가지가 있다.
맨해튼 거리 (Manhattan distance)
위의 이미지에서 빨강, 파랑, 노란 선처럼
상, 하, 좌, 우 네 방향으로만 이동하는 거리를 말한다.
유클리드 거리 (Euclidean distance)
위의 이미지에서 초록 선처럼
시작 위치와 도착 위치의 직선거리로
대각선 방향으로 이동이 가능할 때의 최단 거리를 말한다.
F = G + H
필요한 변수
- 시작 위치, 도착 위치
- F : 총 예상 거리 (
G + H)- G : 시작 위치부터 현재 위치까지의 거리
- H : 현재 위치에서 도착 위치까지의 거리 (휴리스틱)
- Open 리스트 : 탐색할 가치가 있는 자료구조 (우선순위 큐)
- Closed 리스트 : 이미 탐색한 노드 자료구조
- allNodes 딕셔너리<위치, 노드> : 위치기반으로 노드를 저장하는 자료구조
- Parent 부모노드 : 최종 경로를 역추적할 때 필요
- 벽을 구분하는 함수
- 4방향 or 8방향 이웃 노드를 계산하는 함수
- 거리 계산 함수 : G 계산시 사용, 상하좌우 1, 대각선 1.4 (
1 : 1 : √2)- 도착 위치에 도달할 시 경로를 역추적하여 경로를 계산하는 함수
A* 알고리즘은 도착점까지 도달하거나, 더 이상 탐색할 노드가 없을 때까지 다음 과정을 반복한다
- 현재 위치에서 상하좌우(4방향) 또는 대각선 포함(8방향)의 노드들을 탐색한다.
- 각 이웃 노드에 대해 G, H, F 값을 계산한다.
- F 값이 가장 낮은 노드를 다음 탐색 대상으로 선택하여 이동한다. (같으면 G나 H를 비교)
- 해당 노드를 Closed 리스트(방문 완료)에 추가하고, 다음 탐색을 계속한다.
이 과정을 반복하면 둘 중 하나를 알 수 있다.
- 도착 지점에 도달하여 최단 경로를 얻거나,
- 더 이상 탐색 가능한 노드가 없어서 경로가 존재하지 않거나
Hi