#좌선법, 우선법
- 단순히 왼쪽 혹은 오른쪽 벽을 계속 짚고 가는 알고리즘.(DFS와 비슷)
- 자신이 지나온 길을 체크하지않기때문에 메모리는 적게소비한다.
- 하지만 사이클이 생기는 미로는 탈출이 불가능할 수도 있다.
- 또한 최단경로가 아닐 가능성이 많다.
#DFS, BFS
- 깊이 우선 탐색(Depth-first search), 너비 우선 탐색(Breadth-first search)
- 보통 너비우선탐색이 깊이우선탐색보다 확률적으로 더 짧은 경로를 찾는다.
- 좌선법, 우선법과는 다르게 지나온 길을 기억하고있어 같은 길을 반복해 탐색하지않는다(메모리 소비)
- 맵이 무한하거나 길이 없지않는 경우가 아니라면 무조건 해답을 찾아낸다.
#다익스트라 알고리즘
- 분신술 알고리즘
- BFS알고리즘의 발전형
- 갈림길의 갯수만큼 분신하여 모든 경로를 탐색한다.
- 분신들 중 하나가 출구를 찾아내면 지나온 경로를 기록, 모든 분신들에게 자신이 지나온 길이를 알린 후 소멸한다.
- 남아있는 분신 중 더 짧은 경로를 찾아내면 또다시 남아있는 분신들에게 알린 후 소멸한다.
- 모든 분신이 소멸하면 기록된 최단 경로를 얻을 수 있다.
#A* 알고리즘
- A*알고리즘은 DFS알고리즘에 기초를 두고있다.
- A*알고리즘은 목적지를 알고 있어야 사용이 가능하다.
- 갈림길을 만나면 다익스트라처럼 분신을 만들지 않고 '다른 길이 있다'라는 정보만 남겨둔 후 지나온 길들을 삭제한다.
- 막다른 길을 만나면 이전의 갈림길로 돌아와 해당 길에 대한 정보를 삭제한다.
- 최단 거리를 보장하진 않으나, 대체적으로 최단거리에 가까운 경로를 찾아낸다.