너비 우선 탐색(BFS)
- 가장 단순한 방법
- 몇 가지 수정하면 다익스트라 알고리즘이 됨
- 항상 최단 거리 반환
- 지도의 타일이 동일한 이동 비용을 가지게 돼서 지도에 다양한 타일을 추가할 수 없음
- 여러 개의 시작점과 종료점이 있어도 상관 없음
- 중간 정도 속도
다익스트라(Dijkstra)
- 휴리스틱 탐색법을 추가해서 몇 가지를 수정하면 A* 알고리즘이 됨
- 항상 최단 거리 반환
- 이동 비용을 잘 다룸
- 여러 개의 시작점과 종료점이 있어도 상관 없음
- 속도가 느림
A* 알고리즘
- 항상 최단 거리 반환 설정도 가능, 변수를 추가해 속도와 정확성 사이에서 트레이드 오프를 할 수도 있음 => 알고리즘을 훨씬 빠르게 실행할 수 있지만 최단 경로를 보장하지는 않음
- 이동 비용을 잘 다룸
- 여러 개의 시작점과 종료점이 있으면 안 됨 => 한 포인트에서 한 포인트로 연결되는 알고리즘임
- 실행속도가 아주 빠름 (그래서 경로찾기에 A* 알고리즘을 추천하는 것임) *속도에서 중요한 점은 정확성을 높이면 실행 속도가 느려지게 됨 - 휴리스틱 탐색법 때문에
너비 우선 탐색
1. 탐색 방향을 정한다. - 설계자가 알아서 선택하도록 놔둬도 되고 알고리즘에서 하드코딩해 방향을 정해도 된다.
2. 노드를 트리에 추가한다. - 시작점이라면 시작 노드를 추가한다.
3. 탐색 방향을 사용해서 트리에 현재 노드의 이웃을 추가한다.
4. 아직 탐색하지 않은 다음 노드로 넘어간다.
5. 목표에 도달하지 못했다면 3단계로 돌아가서 트리에 현재 노드의 이웃을 추가한다.
6. 결과가 나오면 트리에서 거꾸포 그 순서를 기록한다.
7. 그 리스트를 뒤집어서 경로를 바른 순서대로 찾는다.