우리가 학부 수준에서 배우는 최단거리 알고리즘은 여러가지가 있다.
꼭 알고리즘 수업이 아니더라도, (나는 아직 알고리즘 수업을 듣지 못 했다.) 자료구조나, 컴퓨터 네트워크, DB 등의 수업등에서도 여러 최단거리 알고리즘을 배울 수 있다.
보통은 자료구조 Queue의 FIFO(First-In First-Out) 성질을 이용해 그래프의 인접 노드들을 전부 동일한 페이즈에 탐색하는 너비 우선 탐색 bfs로 시작할 것이다.
인접한 노드들을 전부 동일한 페이즈에 방문할 수 있으므로, 어떤 지점까지 가는데에 돌아가지 않고 한번에 도달할 수 있다.
하지만 여기에는 함정이 있다.
수업때 알려주지는 않지만, bfs는 대체적으로 노드들끼리 이동하는데 쓰이는 코스트가 같을 때 유효한다.
노드들간의 이동에 드는 코스트가 다르다면 무슨 일이 일어날까? 돌아 가는 것이 오히려 유리한 상황이 나오게 된다.
bfs는 과정의 수를 세는 방식이기 때문에, 이런 문제를 해결하기가 조금 어렵다. 이런 문제는 위대하신 Dijkstra 수령님께서 만드신 다익스트라 알고리즘으로 해결할 수 있다.
다익스트라를 모르던 시절 다양한 꼼수로 몇 문제를 풀어냈으나, 이내 한계에 부딫쳤고, 그 때 다익스트라 알고리즘의 존재를 알게 되었다.
다익스트라 알고리즘은 우리에겐 Priority Queue로 더 익숙한 Heap이라는 자료구조를 이용한다. 트리구조를 내부적으로 가져서 우선순위에 따라 자료가 정렬되는 큐이다. 미리 구현된 Priority Queue 외에 힙을 사용한다면 내가 원하는 대로 복잡한 우선순위를 갖도록 해줄 수도 있다. 다익스트라 알고리즘은 bfs와 유사하게 코드가 짜인다. 다만 큐를 우선순위 큐로 바꾸어준 느낌이다.
다익스트 알고리즘에서는 우선순위 큐를 이용하여, 현재까지 완성된 그래프와 이어진 간선들 중 가장 코스트가 작은 간선을 찾아낸다.
무슨 말이냐면, 시작 노드를 생각해보자. 이 시작 노드에 이어진 간선들 중 가장 코스트가 작은 것을 취해 해당 간선으로 이어진 노드를 다음 노드로 결정한다.
그러면 두 노드가 간선으로 이어진 형태가 되는데, 이를 하나의 작은 그래프로 보겠다는 것이다. 이제 새로운 노드에 연결된 간선들도 우선순위 큐에 들어가게 될 것이다. 그러면 두 노드와 연결된 간선 모두가 들어있는 셈이다. 즉, 지금까지 완성된 그래프와 연결된 모든 간선들이 큐에 들어있다. 우선순위 큐에 의해 가장 코스트가 작은 간선이 선택되는 것이다.
bfs와 다르게, 이미 발견된 간선에 대해 알고 있는 최단거리 보다 긴 경우 무시하고, 짧은 경우 새로운 거리를 갱신하고, 해당 노드를 현재까지의 거리를 포함해 다시 큐에 넣어준다.
이런 이유로 다익스트라 알고리즘에서 쓰이는 우선순위 큐에는 단순히 노드 번호 뿐만 아니라, 출발지로 부터 해당 노드까지의 이동 거리를 포함하고 있는 경우가 많다. 그리고 내가 이미 알고 있는 거리보다 짧은 경우 갱신을 해주는 방식이기 때문에, 수행 전, 출발지로 부터 모든 노드까지의 거리를 충분히 큰 값으로 초기화 해주는 작업이 필요하다.
어떤 상황을 가정해보자. a -> b -> c로 완성된 그래프를 생각해보자. a -> b는 5이고, b -> c도 5이다. 그런데 a -> c가 1억인 간선이 있다고 가정하는 것이다.
기존 bfs의 흐름에 따르면
- a에 연결된
a->b와a->c가 동시에 큐에 진입. - 각각의 거리를 5와 1억으로 기록함.
b -> c를 발견,a -> c는 사실상 1억이 아니라, 10인데, 이미 방문한 노드를 다시 방문하지 않는 bfs의 특성상 해당 발견은 버려진다.
이런 상황이 문제가 된다. 같은 상황에 다익스트라 알고리즘을 적용해보자.
- a에서 dist가 5인
a -> b간선이 선택됨. 현재 알고 있는 거리는 INF이므로 5로 초기화 - b와 연결된 간선들을 우선순위 큐에 넣는다.
- b에서 dist가 5인
b -> c간선이 선택됨. 현재 알고 있는 거리는 INF이므로 5로 초기화 - 성공적으로
a -> c를 10으로 기록. - 마지막 간선인
a -> c1억이 큐에서 발견되었으나, 이미 발견한 거리값인 10보다 크므로 무시된다.
다익스트라는 대부분의 경우에서 아주 좋은 최단거리 알고리즘이다. 여기까지 보통 배우는 것으로 알고 있고, 다익스트라의 여러 한계들을 해결한 알고리즘들도 있다. 다익스트라는 출발지로 부터 모든 노드들과의 최단거리를 찾는 알고리즘이고, 모든 노드들 간의 최단거리를 찾기 위한 플로이드-와샬 알고리즘이 제안되었다. 그리고, 두 알고리즘들의 한계인 음수 사이클을 만날 시 무한 루프를 돈다. 라는 단점을 해결한 벨만 포드 알고리즘등이 있다.
이들은 근본적인 문제점들이고, 실용적인 문제점이 있다.
아래와 같은 상황은 어떻게 할 것인가?
그림은 홍익대학교로 부터 충남 진호리까지의 자전거 루트에 그리드를 씌운 모습이다. 이런 절망적인 상황에서 다익스트라는 어떻게 작동할까? 실제 지도에서는 노드들간의 코스트가 그렇게 큰 차이가 나지 않는다. 결국엔 다익스트라 또한 bfs와 같은 방식으로 퍼지게 될 것이다. 아래와 같은 그림을 보자.
답답한 진행
dijkstra를 통한 탐색 과정은 위와 같은 상황에서 너무나도 느리다. 쓸모없는 노드들을 참 많이도 거치고 있다.
A* 알고리즘을 설명하기 전에
휴리스틱이을 검색하면 각종 어려운 말들을 볼 수 있지만, heuristic은 대충 어림짐작하기이다.
각 노드에서 도착 지점까지의 거리를 대~충 짐작하기 위한 함수를 도입할 것인데, 이를 휴리스틱 함수라고 부른다.
인공지능 분야에서도 k개의 인접 이웃 찾기 알고리즘 등에 다양한 휴리스틱을 쓰지만, 지도에서 길을 찾는 경우에는 주로 Manhattan distance와 Euclidean distance을 사용한다.
맨하탄 거리로 알려진 택시 거리는 가로와 세로의 합으로 거리를 구한다.
(출처: The plan of Manhattan of 1811)
위 사진은 격자형 계획도시 맨해튼의 지도이다. 위와 같이 격자형 도시에서는 어떤 지점에서 다른 지점으로 갈 때의 거리를 생각해보자. 건물을 뚫고 지나갈 수도, 위로 날아서 갈 수도 없으므로, 가로와 세로의 합을 생각해 보는 것이 맨해튼 거리이다.
유클리드 거리는 우리에게 익숙한 피타고라스 정리를 생각하면 된다. 피타고라스 정리는 이미 있는 삼각형에서 가로와 세로의 길이를 이용해 빗변의 길이를 구하는 것이라면, 유클리드 거리는 똑같은 방식으로 두 점을 잇는 선을 빗변으로 하는 삼각형을 만들어 거리를 구하는 방식이다.
연산하는 차원수가 적은 경우 일반적으로 유클리드가 더 성능이 좋지만, 격자 무늬에서는 맨해튼 거리가 더 효율이 좋다고 알려져 있다. (feat. 차원의 저주)
A* 알고리즘에 대해 최대한 요약해보겠다.
- 어떤 노드로 부터 도착지점 까지의 대강의 거리를 계산할 휴리스틱 함수를 도입.
- Dijkstra와 같이 진행하되, 노드를 큐에 넣어주기 전에, 간선의 코스트만 넣어주는 것이 아니라,
간선의 코스트 + 해당 노드와 도착점까지의 추측 거리의 결과를 새로운 코스트로 넣어준다.
여기서 말하는 도착점까지의 추측 거리는 휴리스틱 함수로 추측한 해당 노드에서 부터 목적지까지의 거리이다.
일부 완성된 그래프에서, 우선순위 큐의 가장 위에 있는 노드를 생각해보자. Dijkstra의 진행과 같이 최단 거리의 갱신이 필요하다면 갱신하고, 해당 노드와 간선으로 연결된 노드들을 탐색한다.
이 때, 단순히 현재 거리에서 간선의 값을 더한 결과를 그 노드까지의 최단거리로 생각하지 않고, 해당 노드에서 도착지점까지의 거리를 휴리스틱으로 추측한다.
맨해튼 택시 거리의 예시를 든다면, 다음 노드를 우선순위 큐에 넣기 전에, 노드로 부터 목적지까지의 가로 길이와 세로 길이를 더해서, 아까 계산해둔 현재 거리 + 간선 값에 더해준다.
그럼 무슨 일이 일어날까? 목적지와 가까울 수록 더 작은 값이 더해지게 되고, 목적지와 멀 수록 더 큰 값이 더해지게 된다. 돌아가는 코스트가 곧장 가는 코스트보다 아주 낮지 않은 이상, 웬만하면 목적지 쪽으로 향하는 형태가 된다!
우선순위 큐는 가장 코스트가 적은 곳을 찾아 이동하기에 당연하다.
이제, 이런 멋진 아이디어를 적용한 마법같은 A Star 알고리즘을 보자. (맨해튼 거리 적용)
목적지를 아는 것처럼 바로 출발한다. (WOW)
장애물을 만났지만, 장애물에서 벗어나는 순간 또 바로 직행하는 아름다운 모습을 관찰할 수 있다. (WOW!)
진짜 와우다;
장애물이 있는 경우 더 아름답다. 마치 컴퓨터가 목적지를 아는 듯한 움직임이다.
다익스트라에서 확장된 A* 알고리즘은 노드가 아주 많은 상황에서 아주 멋진 움직임을 보인다. 주로 예전의 게임들에서 많이 사용했는데, 스타크래프트 1에서 사용된 것으로 추측된다. 유닛을 특정 위치로 찍은 경우, 길을 막는 유닛이 없어 이동할 수 있다면, A* 연산을 실행하여 최단거리를 계산하고 이동하는 것으로 추측된다. 전략적인 이동도 가능하다. 지형들에게 가중치를 주어, 벽과 떨어져 가시오, 웬만하면 물 위로는 가지 마시오 등의 전략 부여도 가능하다!
간단한 형태의 수도 코드를 분석해 보겠다.
// A* finds a path from start to goal.
function A_Star(start, goal, h)
openSet := {start}
cameFrom := an empty map
gScore := map with default value of Infinity
gScore[start] := 0
// For node n, fScore[n] := gScore[n] + h(n). fScore[n]
fScore := map with default value of Infinity
fScore[start] := h(start)
while openSet is not empty
current := the node in openSet having the lowest fScore[] value
if current = goal
return reconstruct_path(cameFrom, current)
openSet.Remove(current)
for each neighbor of current
tentative_gScore := gScore[current] + d(current, neighbor)
if tentative_gScore < gScore[neighbor]
cameFrom[neighbor] := current
gScore[neighbor] := tentative_gScore
fScore[neighbor] := tentative_gScore + h(neighbor)
if neighbor not in openSet
openSet.add(neighbor)
return failure- openSet은 힙으로 구현된 자료구조. 휴리스틱이 포함된 값들이 들어가게 된다.
- gScore은 휴리스틱이 포함되지 않은 거리의 기록, fScore은 휴리스틱이 포함된 거리를 기록한다.
- cameForm은 경로 역추적을 위해 존재. 더 이상 설명 X
- 앞서 설명한대로 while문이 openSet이 비어있지 않은 동안 돌아간다
- current는 현재 탐색중인 노드로 openSet에서 가장 작은 값을 꺼내온 다음 제거한다. current가 goal 일때 연산 종료
- current의 이웃 노드들을 살펴보는데, 실제 거리로 따져서 더 가까운 거리를 알고 있다면, 그 쪽으로 이동한다.
- 이동하며 각 배열들에 기록된 값을 갱신하고, 적혀있지 않지만 openSet에는 휴리스틱에 포함된 값을 넣는다.
이렇게 A*는 다익스트라를 정말 빠르게 계산하였다. 실시간으로 바뀌는 정보를 반영하기 위한 Dynamic A star인 D*등으로 A*는 더 강해졌다.
그리고 그리드 형태의 부자연스러움을 개선하기 위한 후처리 작업 알고리즘인 Theta*도 제시되었다.
하지만, 아주 먼 거리에 대해서는 여전히 성능 이슈가 있었고, 무엇 보다도 현실 세계에 적용하기엔 Dijkstra 기반 특성상 1:m의 최단거리 측정만이 가능하다.
즉 어떤 목적지로의 여러 경로를 안내해야하는 지도나 네비게이션의 니즈와는 맞지 않는다.
현실 세계에서는 n:m을 지원하고, A*보다 훨씬 빠르게 동작하며, 다양한 교통 상황을 반영하는 CCH 알고리즘을 주로 사용한다.
- PathFinding.js
- STARCRAFT 1 PATHFINDING: A TECHNICAL ANALYSIS
- When would one use Manhattan distance as opposed to Euclidean distance?
- Commissioners' Plan of 1811
- A*를 이용하는 전술적 경로찾기에서 휴리스틱 성능 비교 <김경혜, 조수진, 설정아, 유견아 저>
- 알고리즘 문제 해결 전략 <구종만 저>
- 지도: Naver 지도