최단 경로 탐색 – A* 알고리즘

최단 경로 탐색 알고리즘 중 A*(A Star, 에이 스타) 알고리즘에 대해 실제 예시를 통해 풀어가면서 설명하겠습니다. A* 알고리즘은 시작 노드만을 지정해 다른 모든 노드에 대한 최단 경로를 파악하는 다익스트라 알고리즘과 다르게 시작 노드와 목적지 노드를 분명하게 지정해 이 두 노드 간의 최단 경로를 파악할 수 있습니다.

A* 알고리즘은 휴리스틱 추정값을 통해 알고리즘을 개선할 수 있는데요. 이러한 휴리스틱 추정값을 어떤 방식으로 제공하느냐에 따라 얼마나 빨리 최단 경로를 파악할 수 있느냐가 결정됩니다.

A*에 대한 서론은 최대한 배제하고 하나의 명확한 예를 통해 풀어나가며 설명하도록 하겠습니다. 다음과 같은 예를 통해 먼저 살펴보겠습니다.

위의 예는 시작점인 0번 노드에서 목적지인 6번 노드로 가는 최단 경로를 A* 알고리즘으로 분석하고자 하는 것인데요. 각 노드 사이에 연결된 링크에 붙은 숫자는 노드 사이를 이동하는데 소요되는 비용(경비, Cost)입니다. 위의 경우 거리값입니다. 즉, 노드 사이의 거리가 길수록 비용이 늘어나므로 비용값으로써 합리적입니다.

A* 알고리즘을 통한 위의 문제 해결을 위해 가장 먼저 수행하는 첫 과정은 다음과 같습니다.

위의 그림에서 보면 저장소로 O와 C가 있는데요. O는 열린 목록(Open List), C는 닫힌 목록(Close List)인데요. 열린 목록인 O 저장소에는 최단 경로를 분석하기 위한 상태값들이 계속 갱신되며, C 저장소는 처리가 완료된 노드를 담아 두기 위한 목적으로 사용됩니다.  이러한 O와 C의 저장소를 기반으로 0번 노드에서 6번 노드까지의 최단 경로를 산출해 보도록 하겠습니다.

먼저 출발 노드인 0을 닫힌 목록인 C 목록에 집어 넣습니다. 그리고 이 0번 노드와 연결된 노드는 1번과 3번 노드를 열린 목록인 O 저장소에 추가합니다. 추가할 때 F, G, H, Parent Node값도 함게 추가해야 하는데요. 먼저 F = G + H입니다. G는 시작 노드에서 해당 노드까지의 실제 소요 경비값이고, H는 휴리스틱 추정값으로 해당 노드에서 최종 목적지까지 도달하는데 소요될 것이라고 추정되는 값입니다. Parent Node는 해당 노드에 도달하기 직전에 거치는 노드 번호입니다. 먼저 1번 노드에 대한 F, G, H, Parent Node를 살펴 보겠습니다. 출발점인 0번 노드로부터 시작했으므로,  1번 노드의 Parent Node는 0번 노드입니다. 그리고 G 값은 0번 노드에서 1번 노드까지의 거리 비용값인 5.6입니다. H 값을 추정하기 위한 기준이 필요한데요. 이 추정값에 대한 기준을  1번 노드에서 목적지인 6번 노드까지의 직선 거리로 하기로 정하고 측정을 하니(줄자로 재든, 좌표가 있다면 피타고라스 정리를 통해 두 좌표 사이의 거리를 계산하든 하여 얻을 수 있음)  12로 산출되므로 H는 12가 됩니다. F = G + H이므로 5.6 + 12인 17.6이 됩니다. 3번에 대한 F, G, H, Parent Node 역시 이와 동일하게 결정할 수 있습니다. 여기서 다음 단계로 진행합니다.


O 리스트 중 F 값이 가장 작은 노드는 3번인데요. 이 노드 3번을 C 리스트에 추가하고 3번 노드와 연결된 0, 2, 5 중 닫힌 목록에 존재하지 않는 2, 5번 노드에 대해 열린 목록에 추가합니다. 2, 5에 대한 F, G, H, Parent Node를 계산해 기록합니다. 먼저 2번 노드에 대해 계산해 보면.. 2번 노드에 대한 G 값은 바로 직전 노드에 소요되는 비용(6.8)에 3번 노드에서 2번 노드까지 도달하기 위한 비용인 5.6을 합한 값인 12.4가 됩니다. 그리고 H 값은 2번 노드에서 목적지은 6번까지에 대한 거리값인 7이 됩니다. 5번 노드에 대한 것도 이와 동일하게 계산합니다. 다음으로 진행합니다.

열린 목록(O 저장소) 중 F 값이 가장 작은(최소인) 1번 노드를 닫힌 목록에 추가합니다. 그리고 이 1번 노드와 연결된 2, 4번 노드 중 닫힌 목록(C 저장소)에 존재하지 않는 것에 대해 다시 F, G, H, Parent Node를 계산합니다. 이 상태에서 4번 노드는 열린 목록에 없었던 것이기에 그냥 F, G, H, Parent Node를 이미 앞서 설명했던 방식으로 계산해 추가하면 그만이지만 2번 노드는 전 단계에서 이미 추가되어 있었는데요. 이렇게 전 단계에서 추가된 G 값이 새롭게 계산된 G 값보다 크다면 새롭게 계산된 F, G, H, Parent Node 값으로 변경해 줘야 하며 위의 그림이 이러한 변경을 나타내고 있습니다. 다음 단계로 진행합니다.

열린 목록 중 G가 최소인 노드는 2번 노드이고, 이 2번 노드를 닫힌 목록에 추가합니다. 그리고 2번 노드와 연결된 1, 3, 5, 6번 노드 중 닫힌 목록에 존재하지 않는 5, 6번 노드에 대한 F, G, H Parent Node 값을 계산합니다. 5번 노드의 경우 새로운 G 값이 기존 값보다 크므로 변경하지 않고 6번 노드에 대한 값들만을 계산해 추가합니다. 다음 단계로 진행합니다.

열린 목록 중 F가 최소인 노드는 6번 노드인데요. 이 6번 노드를 닫힌 목록에 추가합니다. 그런데 이 6번 노드는 최종 목적지 노드이므로 A* 알고리즘은 종료됩니다.

여기까지 만들어진 닫힌 목록(C 저장소)를 토대로 0번 노드에서 6번 노드까지의 최단 경로를 파악할 수 있습니다. 6번 노드의 Parent Node는 2번 이고, 2번 노드의 Parent Node는 1번이며, 1번 노드의 Parent Node는 0번이므로 최단 경로는 6번 노드←2번 노드←1번 노드←0번 노드가 됩니다.

최단 경로 탐색 – Dijkstra 알고리즘

다익스트라 알고리즘은 시작 노드만을 지정하면, 이 시작 노드에서 다른 모든 노드에 대한 최단 경로들을 분석해 줍니다. 참고로 최단 경로 탐색 알고리즘의 다른 형태로  A*(에이스타) 알고리즘이 있는데요. A* 알고리즘은 시작 노드에서 목적지 노드를 지정해주면 이 2개의 노드 간의 최단 경로 하나만을 분석해 줍니다.

이 글은 다익스트라 알고리즘에 대한 이런 저런 장황한 설명을 배제하고 실제 예를 들어, 그 예에 대한 최단 경로 탐색을 위한 다익스트라 알고리즘에 대해 설명합니다.

먼저 다음과 같은 예를 들어 보겠습니다.

위의 그림을 간단히 설명하면, 0부터 6번까지의 노드(Node)가 존재하고 각 노드를 연결하는 선인 링크(Link)가 있습니다.  각 링크에는 숫자가 표시되어 있는데요. 이 숫자는 해당 링크를 지나갈때에 소요되는 비용(Cost, 경비)로 생각할 수 있습니다. 예를 들어, 2번 노드와 6번 노드 사이에 비용 8인 링크가 있는데요. 이는 2번 노드에서 6번 노드를 지나간다고 할때 8의 비용이 필요하다는 의미입니다. 비용이 적을 수록 상대적으로 더 좋은 경로이겠지요.

이제 위의 예, 즉 0번 노드를 시작점으로 해서 나머지  1, 2, 3, 4, 5, 6 번 노드를 목적지로 하는 최단 경로 6개를 구할 수 있는 방법이 바로 다익스트라 알고리즘입니다.

이상의 문제 해결을 위해 가장 먼저 시작되는 연산은 다음 그림과 같습니다.

위의 그림에서 S 은 이미 처리가 완결된 노드의 집합인데요. 가장 먼저 시작 노드인 0번을 집어 놓음으로써 0번 노드에 대한 처리를 시작합니다. D 저장소는 0번~6번까지의 노드에 대해, 시작노드로부터 소요되는 비용을 저장하고 있습니다. D 저장소의 상단 행은 노드의 번호이고 하단 행은 시작노드로부터 소요되는 비용입니다. 위 그림에서 D 저장소를 보면 0번 노드는 시작노드이므로 소요되는 비용이 0이고, 0번 노드와 링크로 연결된 1번과 3번 노드는 각각 5와 1의 비용이 소요되는 것으로 기록되어 있습니다. T 저장소는 해당 노드로 가는데 연결된 노드의 번호를 담고 있는데요. T 저장소이 상단 행은 노드의 번호이고 하단 노드는 연결된 노드 번호입니다. 위의 그림을 보면 1번 노드와 3번 노드는 0번 노드와 연결되어 있으므로 0으로 기록되어져 있습니다. 이게 주어진 문제에 대한 다익스트라 알고리즘의 첫번째 처리입니다.

이제 다음 처리에 대한 그림을 살펴 보겠습니다.

S집합에 3번 노드를 추가했습니다. 이유는 D 저장소에 3번 노드에 대한 비용값이 가장 최소이기 때문입니다. S집합에 3번 노드를 추가함으로써 3번 노드와 링크로 연결된 2번과 5번 노드에 대한 비용값을 계산해 D 저장소에 기록해야 하는데요. 시작 노드인 0번 노드에서 2번 노드까지 가기 위해서 소요되는 비용은 총 3입니다. 이유는 0번-3번-2번 노드로 가야하므로 비용값은 0번-3번 노드로 가는 비용 1과 3번과 2번 노드로 가는 비용 2를 합한 값입니다. 이러한 계산은 D 저장소를 활용하면 쉽게 계산할 수 있는데요. 이미 시작노드에서 각 노드로 가는 비용이 계산되어 있기 때문에 마지막 노드로 가는 비용만을 더해주면 되기 때문입니다. 5번 노드에 대한 비용은 동일한 방식으로 1+1인 2가 됩니다. 그리고 T 저장소도 각 노드에 대해 이전에 연결된 노드값을 기록해 둡니다. T 저장소의 2번과 5번 노드는 3번 노드를 통해 연결되어 있으므로 3을 기록합니다. 다음 처리에 대한 그림을 살펴봅시다.

S 집합에 5를 추가했습니다. 이는 이미 처리가 완료된 노드 이외의 노드 중 5번 노드의 비용이 2로 가장 최소이기 때문입니다.  이미 처리가 완료된 노드인지 S 집합에 존재하는지를 보면 알 수 있습니다. 5번 노드에 대해 연결된 노드는 2, 3, 6번 노드인데요. 이미 3번은 처리가 완료되었으므로 2번 노드와 3번 노드에 대해 D 저장소의 값을 갱신해야 합니다. 5번 노드를 거쳐 2번 노드를 갈 경우 소요되는 비용은 2+2로 4입니다. 이 값은 이미 전 단계에서 계산된 비용값(3)보다 크므로 무시합니다. 6번 노드에 대한 비용값은 5번 노드까지 오는데 소요된 비용값(2)와 5번에서 6번 노드로 가는데 추가적으로 필요한 비용 3을 합한 값 5이므로, 이 값을 D 저장소에 기록하고 T 저장소의 6번 노드 값에 5번 노드를 기록합니다. 다음 단계로 넘어 갑니다. 

처리가 완결되지 않은 노드 중 비용이 최소인 노드는 2번인데요. 2번 노드와 연결된 노드는 1, 3, 5, 6번 노드입니다. 처리가 완결된 노드를 저장하고 있는 S 집합을 통해 3번 노드와 5번 노드는 더 이상 고려할 필요가 없다는 것을 알 수 있으니, 1, 6번만 고려하면 됩니다. 먼저 1번의 경우 소요되는 비용은 3+1로 4인데요. 이 값은 이전 단계에서 계산된 비용값(5)보다 작으로 D 저장소의 값을 변경 합니다. D 저장소가 변경되면  T 저장소의 값도 2번 노드로 변경합니다. 중요한 부분이므로 위의 그림에서 빨간색으로 표시했습니다. 이제 남은 6번 노드에 대한 비용값을 계산해 보면 3+8로 11인데요. 이 값은 이전 단계에서 계산된 비용인 5보다 크므로 무시합니다. 다음 단계로 진행합니다.

처리가 완료된 노드가 아닌 것 중 1번 노드의 비용이 현재 가장 최소이므로 집합 S에 1번 노드를 추가하고 1번 노드와 연결된 0, 2, 4번 노드 중 완결되지 않은 4번 노드에 대한 비용값을 계산합니다. 4번 노드의 비용값은 4+3으로 7이므로 이 값을 D 저장소에 기록하고 T 저장소에 1번 노드를 기록합니다.

이미 처리가 완료된 노드가 아닌 것 중 최소인 노드는 6번 노드인데요. 이 6번 노드를 집합 S에 추가하고 6번 노드와 링크로 연결된  1, 2, 4, 5 중 처리가 완결되지 않은 노드는 4번인데요. 6번 노드를 경유해 4번 노드로 가기 위한 비용은 5 + 1인 6으로 계산되며, 이 값은 이전 단계에서 계산된 값(7)보다 작으므로 D 저장소가 변경되고, 이와 함께 T 저장소에 대해서도 4번 노드에 대해 6번 노드로 변경합니다.  다음 단계로 진행합니다.

처리되지 않은 노드 중, 이제 유일하게 4번 노드만 남았는데요. 4번 노드와 연결된 1, 6번 노드에 대해 처리를 해야 하는데 이미 1, 6번 노드는 처리가 완결되었으므로 더 이상 진행하지 않고 종료됩니다.

이상의 결과에서 T 저장소를 통해 출발 노드인 0번 노드에서 각 노드에 대한 최단 경로를 파악할 수 있습니다. 0번 노드에서 1번 노드에 대한 최단 경로는 (1번 노드)←(2번 노드)←(3번 노드)←(0번 노드)가 됩니다. 이는 T 저장소를 보면, 먼저 1번 노드에 연결되는 노드는 2번 노드라는 것을 알 수 있고, 다시 2번 노드는 3번 노드와 연결되며 3번 노드는 시작 노드인 0번 노드라고 기록되어 있기 때문입니다. 시작 노드 0번에서 각 노드에 대한 최단 경로를 정리하면 다음과 같습니다.

  • 0번 노드에서 1번 노드 : (1번 노드)←(2번 노드)←(3번 노드)←(0번 노드)
  • 0번 노드에서 2번 노드 : (2번 노드)←(3번 노드)←(0번 노드)
  • 0번 노드에서 3번 노드 : (3번 노드)←(0번 노드)
  • 0번 노드에서 4번 노드 : (4번 노드)←(6번 노드)←(5번 노드)←(3번 노드)←(0번 노드)
  • 0번 노드에서 5번 노드 : (5번 노드)←(3번 노드)←(0번 노드)
  • 0번 노드에서 6번 노드 : (6번 노드)←(5번 노드)←(3번 노드)←(0번 노드)