A* 알고리즘(A* search algorithm), 그동안 개념만 얼추 알고 있던 알고리즘이었습니다. A* 알고리즘은 인공지능 분야에 더 가깝기 때문입니다. 따라서 저도 학부 인공지능 수업 시간에 잠깐 들었던 게 다였죠. 그런데 이번 학기 조교 일을 하면서 어쩌다 보니 A* 알고리즘을 좀 심도 있게 공부해야 할 모종의 사건(?)이 생겼습니다. 처음에는 뭐 이런 것까지 공부해야 하나 싶었지만, 이것저것 찾아 보고 공부하다 보니 웬걸 이론적으로도 흥미로운 내용이 많이 있더군요. 이번 기회에 공부한 내용을 정리하는 겸하여 이 글을 적습니다.
다만 본문의 내용은 제가 이해한 내용을 바탕으로 제 방식대로 재해석하여 적은 것입니다. 따라서 원래 인공지능 분야에서 이해되는 방식과는 다를 수 있습니다. 이점 양지하시고 본문을 읽어 주시기를 부탁 드립니다.
본문은 다익스트라 알고리즘(Dijkstra's algorithm)을 알고 있다는 가정 하에 작성되었습니다. 이에 대한 자세한 내용은 아래 글을 참고하세요.
다익스트라의 알고리즘 (Dijkstra's Algorithm)
최단 경로 문제(shortest path problem)는 가장 유명한 조합론적 최적화 문제 중 하나로, 이름에서 유추할 수 있듯이 다양한 분야에서 널리 활용되는 문제입니다. 지난 포스트에서는 이 문제를 정확히
gazelle-and-cs.tistory.com
문제 정의
A* 알고리즘은 일반적으로 문제 해결 에이전트(problem-solving agent)의 초기 상태(initial state)에서 목적 상태(goal state)까지의 최적해를 구하는 문제로 정의됩니다만, 이는 최단 경로 문제와 크게 다르지 않습니다. 따라서, 본문에서는 어떤 방향 그래프 \(G = (V, E)\)와 음이 아닌 간선 비용 (혹은 거리) \(c:E \to \mathbb{Q}_+\), 그리고 출발지 \(s \in V\)와 목적지 \(t \in V\)가 주어졌을 때, \(s\)에서 \(t\)까지 가는 최단 경로를 구하는 문제를 고려하겠습니다.
다익스트라의 알고리즘
이전에 우리는 다익스트라의 알고리즘을 공부하였습니다. 이는 아래와 같았습니다. 원래 다익스트라 알고리즘은 출발지에서 각 정점으로 향하는 최단 경로를 모두 찾는 알고리즘입니다만, 이번에는 목적지가 정해져 있으므로, 목적지로 향하는 최단 경로를 찾으면 종료하는 알고리즘으로 기술하였습니다.
알고리즘 1. Dijkstra's algorithm
입력: 방향이 있는 그래프 \(G = (V, E)\), 간선 비용 \(c : E \to \mathbb{Q}_+\), 출발지 \(s \in V\), 목적지 \(t \in V\)
출력: \(s\)에서 \(t\)까지 향하는 최단 경로
- 정점을 \(1, \cdots, |V|\)라고 하고, \(Q\)는 우선순위 큐(priority queue)라고 하자.
- \(d[s] \gets 0 \text{ & } d[v] \gets \infty, \forall v \in V \setminus \{s\}\)
- \(S \gets \emptyset\)
- \(Q.\mathsf{enqueue}(s, 0)\)
- \(Q\)에 저장된 정점이 없을 때까지 아래를 반복한다.
- \( u \gets Q.\mathsf{dequeue}() \)
- \( S \gets S \cup \{ u \}\)
- 만약 \(u = t\)이면, 반복을 탈출한다.
- \(u\)에서 나가는 방향으로 인접한 모든 정점 \(v\) 중 \( d[v] > d[u] + c(u, v) \)를 만족하면 아래를 수행한다.
- \(d[v] \gets d[u] + c(u,v)\)
- \(\pi(v) \gets u\)
- 만약 이전에 \(d[v] = \infty\)였다면, \( Q.\mathsf{enqueue}(v, d[v]) \); 그렇지 않았다면, \( Q.\mathsf{decreasekey}(v, d[v]) \)
- \(t\)부터 \(s\)가 나올 때까지 \(\pi(\cdot)\)를 따라서 역순으로 얻어지는 경로를 반환한다. 만약 \(s\)가 나오지 않으면 \(t\)에 도달할 수 없다고 반환한다.
다익스트라의 알고리즘이 갖는 흥미로운 특징 중 하나는 \(S\)에 정점들이 들어갈 때, 출발지 \(s\)로부터 가까운 정점에서 멀어지는 정점 순서대로 들어간다는 것입니다.
정리 1. \(d[v]\)의 단조성(monotonicity)
두 정점 \(v, v' \in S\)에 대해, 알고리즘 1에서 \(v\)가 \(v'\)보다 먼저 \(S\)에 들어갔다면, \(d[v] \leq d[v']\)이다.
[증명] 일반성을 잃지 않고 \(v\)가 \(S\)에 들어간 직후 \(v'\)이 \(S\)에 들어간 경우에 대해서만 정리가 성립함을 보이겠습니다. 알고리즘에서 \(v\)가 \(S\)에 들어갔을 때를 생각해 보겠습니다. 만약 단계 5-iv에 의해 \(d[v']\)의 값이 변경되었다면, 분명히 \[ d[v'] = d[v] + c(v, v') \geq d[v] \]를 만족하여 정리가 성립합니다. 이때, 부등식은 간선 비용이 음이 아니기 때문에 성립합니다. 반대로 \(d[v']\)의 값이 변경되지 않았다고 해 보겠습니다. 그러면 \(v\)가 \(S\)에 들어가기 직전에도 \(d[v']\)의 값은 동일하였을 것입니다. \(Q\)는 우선순위 큐이므로 \(d[v] \leq d[v']\)이 성립합니다. ■
따라서 시간의 흐름에 따라 \(S\)가 확장되어 가는 모습을 따라가면, 우리는 출발지 \(s\)로부터 점점 퍼지는 일종의 등고선(contour)을 얻을 수 있습니다. 예를 들어, 다음과 같은 그래프가 주어졌다고 하겠습니다. 각 간선마다 양방향으로 모두 다닐 수 있으며, 그 비용은 정수로 주어졌다고 하겠습니다.
이제 위 입력에 대해 다익스트라의 알고리즘을 수행하여 보겠습니다. 이때, 시간이 흐르면서 \(S\)가 확장되어 가는 것을 따라가 봅시다. 아래 그림은 거리가 증가하기 직전 혹은 종료할 때의 \(S\)만을 나타낸 것입니다.
위 그림에서 \(S\)가 확장되어 가는 것이 \(s\)에서부터의 거리에 대한 등고선을 나타낸다는 것을 확인하시기 바랍니다. 반대로 말하자면, 다익스트라의 알고리즘은 출발지 \(s\)에서 가까운 거리의 정점들부터 하나씩 확인해 나가다가 언젠가 목적지 \(t\)에 도착하면 종료하는 알고리즘으로 볼 수 있습니다. 이는 가중치가 없는 그래프(unweighted graph)에서의 너비 우선 탐색(breadth first search, BFS)과도 유사합니다.
휴리스틱 함수(heuristic function)
그림 2를 살펴 보면, 목적지 \(t\)는 다른 모든 정점을 \(S\)에 넣은 후에야 \(S\)에 들어갑니다. 이는 다익스트라의 알고리즘이 거리 순서대로 방문하는데, 목적지 \(t\)는 출발지 \(s\)에서 가장 멀리 떨어져 있기 때문입니다. 다익스트라의 알고리즘이 이런 식으로 동작하는 것은 목적지 \(t\)에 대한 추가적인 정보가 전혀 없는 일반적인 경우에는 불가피한 선택일 수 있습니다. 예를 들어, 목적지가 어디있는지 잘 모르지만 그냥 동쪽에 있을 것 같아서 출발지로부터 동쪽의 정점들을 계속 확인했는데 사실은 출발지의 서쪽에 있었다고 해 보죠. 그러면 거리 순서대로 방문하는 것보다 훨씬 늦게 도착하는 큰 대가를 감수해야 할 것입니다.
하지만 목적지에 대한 믿을만한 추가 정보를 얻을 수 있다면, 해당 정보를 활용하여 더 빠른 시간에 목적지를 찾는 것이 가능할 터입니다. 예를 들어, 그림 1의 예시 그래프가 사실은 어떤 2차원 평면 상에 있다고 한다면, 아무래도 \(s\)의 서쪽에 있는 정점들은 \(t\)의 최단 경로를 구성하지 않을 공산이 크다는 것을 유추할 수 있습니다.
A* 알고리즘이 활용하는 추가적인 정보, 혹은 휴리스틱(heuristic)은 각 정점에 대한 정보로 주어집니다. 직관적으로 설명하자면, 각 정점의 휴리스틱 값은 그 정점에서 목적지까지 도달하기 위해서 남은 거리가 대략적으로 어느 정도인지를 나타내야 합니다. 이 정보가 "적절히" 주어진다면 다음에 방문할 정점을 선택할 때 적잖이 도움이 될 것입니다. 예를 들어, 출발지 \(s\)에서 다음에 방문할 정점을 찾고 있다고 해 보죠. \(s\)에 인접한 정점이 두 개 있는데, 각각 다음과 같은 상황이라고 해 보겠습니다.
- 정점 1은 \(s\)에서 매우 가까이 있지만, 그 정점의 휴리스틱 값은 매우 크다.
- 정점 2는 정점 1보다는 멀리 있지만, 그 정점의 휴리스틱 값은 매우 작다.
기존 다익스트라의 알고리즘이라면 분명히 정점 1을 골랐을 것입니다. 하지만 만약 휴리스틱 값이 "적절"하다면, 이는 좋은 선택이 아닐 것입니다. 그림 1의 예시에서 \(s\)의 왼쪽 정점들과 같이 오히려 멀어지는 결정일 수 있는 것이죠. 따라서 정점 2를 선택하는 것이 오히려 더 좋은 선택일 것입니다. A* 알고리즘의 목표는 이렇게 추가로 주어진 휴리스틱을 잘 활용하여 보다 빠른 시간에 목적지에 도달하는 것입니다.
A* 알고리즘을 소개하기 전에 한 가지 짚고 넘어가야 할 부분이 있습니다. 도대체 "적절한" 휴리스틱이란 무엇일까요? 앞에서 휴리스틱은 정점들에 대해 정의된 함수 \(h : V \to \mathbb{R}\)이며, 각 정점 \(v \in V\)에 대해, \(h(v)\)는 해당 정점 \(v\)에서 목적지 \(t\)까지 도달하기 위해 남은 거리를 대략적으로 나타낸 것이라고 하였습니다. 이제 어떤 간선 \(\langle v, v' \rangle \in E\)를 하나 고려해 보겠습니다. 만약 우리가 \(v'\)에서 목적지 \(t\)까지 가기 위해서 남은 거리를 대략적으로 계산해 놓았다고 해 보겠습니다. 그러면 우리는 \(v\)에서 목적지 \(t\)까지 가기 위해 남은 거리도 얼추 계산해 낼 수 있습니다. 바로 \(v\)에서 \(v'\)으로 간 다음 \(t\)에 가는 것 보다는 길지 않을 것이라는 점입니다. \(h(v)\)는 \(v\)에서 \(t\)까지의 거리를 개략적으로 계산한 값이고, \(h(v')\)은 \(v'\)에서 \(t\)까지의 거리를 추측한 값입니다. 따라서 위 논의를 바탕으로 우리는, 각 간선 \(\langle v, v' \rangle \in E\)에 대해, \[ h(v) \leq c(v, v') + h(v') \tag{1}\]을 만족해야 적절한 휴리스틱이 된다는 것을 유추할 수 있습니다. 이 조건은 특별히 휴리스틱의 일관성(consistency)이라고 불립니다. 삼각 부등식(triangle inequality)으로도 볼 수 있습니다.
A* 알고리즘
이제 A* 알고리즘을 소개하겠습니다. 기본적인 구조는 놀랍게도 다익스트라의 알고리즘과 매우 유사합니다.
알고리즘 2. A* algorithm
입력: 방향이 있는 그래프 \(G = (V, E)\), 간선 비용 \(c : E \to \mathbb{Q}_+\), 출발지 \(s \in V\), 목적지 \(t \in V\), 휴리스틱 \(h : V \to \mathbb{R}\)
출력: \(s\)에서 \(t\)까지 향하는 최단 경로
- 정점을 \(1, \cdots, |V|\)라고 하고, \(Q\)는 우선순위 큐(priority queue)라고 하자.
- \(d[s] \gets 0 \text{ & } d[v] \gets \infty, \forall v \in V \setminus \{s\}\)
- \(f[v] \gets d[v] + h(v), \forall v \in V\)
- \(S \gets \emptyset\)
- \(Q.\mathsf{enqueue}(s, f[s])\)
- \(Q\)에 저장된 정점이 없을 때까지 아래를 반복한다.
- \( u \gets Q.\mathsf{dequeue}() \)
- \( S \gets S \cup \{ u \}\)
- 만약 \(u = t\)이면, 반복을 탈출한다.
- \(u\)에서 나가는 방향으로 인접한 모든 정점 \(v\) 중 \( d[v] > d[u] + c(u, v) \)를 만족하면 아래를 수행한다.
- \(d[v] \gets d[u] + c(u,v)\)
- \(f[v] \gets d[v] + h(v)\)
- \(\pi(v) \gets u\)
- 만약 이전에 \(d[v] = \infty\)였다면, \( Q.\mathsf{enqueue}(v, f[v]) \); 그렇지 않았다면, \( Q.\mathsf{decreasekey}(v, f[v]) \)
- \(t\)부터 \(s\)가 나올 때까지 \(\pi(\cdot)\)를 따라서 역순으로 얻어지는 경로를 반환한다. 만약 \(s\)가 나오지 않으면 \(t\)에 도달할 수 없다고 반환한다.
다익스트라의 알고리즘과 달라진 부분은 우선순위 큐 \(Q\)에 넣을 때 키(key)를 \(d[v]\)로 넣지 않고 \(f[v] := d[v] + h(v)\)로 넣었다는 점입니다. 이에 해당하는 부분은 빨간색으로 표시하였습니다.
과연 이 알고리즘은 올바르게 동작할까요? 흥미롭게도, 만약 휴리스틱 \(h\)가 이전 절에서 소개한 일관성 조건을 만족한다면, 이 알고리즘은 항상 출발지 \(s\)에서 목적지 \(t\)까지 가는 최단 경로를 출력한다는 것을 보장할 수 있습니다. 이를 증명해 보도록 하겠습니다. 증명의 큰 틀은 이전 글을 그대로 따릅니다. 먼저 \(S\)는 \(s\)에서 도달 가능한 정점들로만 이루어져 있다는 점입니다. 이는 기존 다익스트라의 알고리즘과 동일한 방식으로 증명할 수 있으므로 증명을 생략하겠습니다.
정리 2. \(S\)의 도달 가능성
알고리즘 2가 모두 끝난 후 \(S\)는 \(s\)에서 도달 가능한 정점들로만 이루어져 있다.
정리 2를 통해서 \(t\)가 \(s\)에서 도달 가능했다면 분명 \(S\)에 들어간다는 것을 알 수 있습니다.
다익스트라의 알고리즘에서 어떤 정점 \(v\)가 \(S\)에 들어가면 \(s\)에서 \(v\)까지의 최단 경로가 결정되었습니다. 즉, 그때의 \(d[v]\)가 최단 경로의 길이가 되고 \(\pi[v]\)는 최단 경로 상의 직전 정점이 되었습니다. A* 알고리즘도 동일한 성질을 갖습니다. 다익스트라의 알고리즘에서는 우선순위 큐 \(Q\)에서 고려하는 키가 \(d[v]\)인데 반해 A* 알고리즘에서는 \(f[v] = d[v] + h(v)\)임에도 말입니다. 단, 항상 성립하는 것은 아니고, 적어도 휴리스틱이 일관적일 때, 즉, 조건 (1)을 만족하는 상황에서는 성립함을 보일 수 있습니다.
정리 3. \(S\)의 최적성
휴리스틱이 조건 (1)을 만족한다고 하자. 어떤 정점 \(v \in V\)가 \(S\)에 들어가면 그때의 \(d[v]\)는 \(s\)에서 \(v\)까지의 최단 경로의 비용이며, \(v \neq s\)면 \(\pi[v]\)는 최단 경로 상 직전의 정점이다. 또한 기존에 \(S\)에 있던 다른 정점 \(w \in S\)에 대해서 \(d[w]\)와 \(\pi[w]\)의 값은 변하지 않는다. 즉, 알고리즘이 진행되는 동안 \(d[w]\)는 \(s\)에서 \(w\)까지의 최단 경로의 비용이며, \(\pi[w]\)는 최단 경로 직전의 정점이다.
[증명] 알고리즘이 수행되는 시간에 따라 귀납적으로 보이겠습니다. 가장 처음에 출발지 \(s\)가 \(S\)에 들어갑니다. 이때, \(d[s] = 0\)으로 설정됩니다. \(\pi[s]\)는 정의되지 않습니다. 기존에 \(S\)에 있던 정점은 존재하지 않습니다. 이것으로 기저 조건(base case)이 만족함을 보였습니다.
이제 어떤 정점 \(v\)가 \(S\)에 들어간 때를 생각해 보겠습니다. \(v\)는 출발지가 아니고 우선순위 큐 \(Q\)에 들어있었으므로 \(\pi[v]\)가 정의되어 있을 것입니다. 편의 상, \(u := \pi[v]\)라고 하겠습니다. 알고리즘의 동작에서 우리는 \(u\)가 원래 \(S\)에 들어있었다는 것과 \(d[v] = d[u] + c(u, v)\)로 설정되었다는 것을 유추할 수 있습니다.
먼저, \(v\)가 \(S\)에 들어온 후 기존에 \(S\)에 있던 \(w\)의 \(d[w]\)와 \(\pi[w]\)의 값을 변화시키지 않음을 보이겠습니다. 그 값이 변하려면 분명 알고리즘의 단계 6-iv에서 \(d[w] > d[v] + c(v, w)\)를 만족했어야 합니다. 이때, 귀납 가정을 통해 우리는 두 가지를 알 수 있습니다. 첫 번째는 좌변의 \(d[w]\)가 \(s\)에서 \(w\)까지 향하는 최단 경로의 비용이라는 것입니다. 두 번째는 우변의 \(d[v] + c(v, w) = d[u] + c(u, v) + c(v, w)\)가 \(s\)에서 \(u\)까지 최단 경로를 이용해 간 후 \(v\)를 거쳐 \(w\)에 도달하는 경로의 비용이라는 점입니다. 따라서 좌변의 값이 우변의 값보다 클 수 없으며, \(d[w]\)와 \(\pi[w]\)는 갱신되지 않습니다.
이제, \(d[v]\)가 \(s\)에서 \(v\)까지 가는 최단 경로의 비용이라는 것을 보이겠습니다. \(s\)에서 최단 경로를 타고 \(u\)에 간 후 \(v\)로 향하는 경로를 \(P\)라고 하겠습니다. 이 경로의 비용은 \[c(P) = d[u] + c(u, v) = d[v]\]입니다. 이 경로가 최단 경로가 아니라면 분명 \(s\)에서 \(v\)까지 가는 다른 최단 경로 \(P'\)이 존재할 것입니다. 이때, \(s\)는 원래부터 \(S\)에 속해 있었고, \(v\)는 이번에야 \(S\)에 들어왔으므로 \(P'\)을 \(s\)에서 \(v\)까지 따라가다 보면 분명 기존부터 \(S\)에 속해 있던 정점에서 \(S\)에 속하지 않은 정점으로 향하는 간선이 하나는 존재할 것입니다. 그중 \(s\)에서 출발하여 처음 나오는 간선을 \(\langle u', v' \rangle\)이라고 하겠습니다. 또한 \(v'\)에서 시작하여 \(P'\)을 따라 \(v\)에 도달할 때까지 지나는 정점들을 순서대로 \(v'_1 := v', v'_2, \ldots, v'_k, v'_{k + 1} := v\)라고 이름을 붙이겠습니다. 그러면 \(P'\)은 \(s\)에서 출발하여 \(u'\)을 거친 후 \(v'_1, \ldots, v'_k\)를 지나 \(v'_{k + 1} = v\)에 도달하는 경로이므로 그 비용은 \[ c(P') \geq d[u'] + c(u', v') + \sum_{i = 1}^k c(v'_i, v'_{i + 1}) \]을 만족합니다. \(c(P) > c(P')\)이라고 하였으므로, \[ d[v] > d[u'] + c(u' v') + \sum_{i = 1}^k c(v'_i, v'_{i + 1}) \tag{2} \]을 이끌어 낼 수 있습니다.
알고리즘에서 \(v\)가 \(S\)에 들어갈 때, \(u'\)은 기존에 \(S\)에 들어가 있지만, \(v'\)은 \(S\)에 들어가 있지 않습니다. 이는 우선순위 큐 \(Q\)에서 \(v\)가 \(v'\)보다 먼저 나왔다는 뜻입니다. 따라서, 그때의 \(f\)에 대해, \[ f[v] \leq f[v'] \tag{3} \]을 만족합니다. 먼저, \(f[v] = d[v] + h(v)\)입니다. 이제 \(f[v']\)의 값을 고려해 보겠습니다. \(u'\)은 \(S\)에 들어가 있었고, \(u'\)에서 \(v'\)으로 향하는 간선이 존재하므로, 단계 6-iv에 의해 \[ d[v'] \leq d[u'] + c(u', v') \]을 만족합니다. 또한 앞의 \(P'\)에서 각 \(i = 1, \ldots, k\)에 대해 \(\langle v'_i, v'_{i + 1} \rangle \in E\)이 존재하므로, 휴리스틱의 조건 (1)에 의해 \( h(v'_i) \leq c(v'_i, v'_{i + 1}) + h(v'_{i + 1}) \)이 성립합니다. 이를 모두 더해 주면, \[ h(v') \leq \sum_{i = 1}^k c(v'_i, v'_{i + 1}) + h(v) \]을 이끌어 낼 수 있습니다. 따라서 우리는 \[ f[v'] = d[v'] + h(v') \leq d[u'] + c(u', v') + \sum_{i = 1}^k c(v'_i, v'_{i + 1}) + h(v) \]를 알 수 있습니다. 앞에서 얻은 \(f[v]\)와 \(f[v']\)에 대한 (부)등식을 식 (3)에 적용하여 정리하면 \[ d[v] \leq d[u'] + c(u', v') + \sum_{i = 1}^k c(v'_i, v'_{i + 1}) \]을 얻을 수 있습니다. 이는 앞에서 얻은 식 (2)와 모순이 됩니다. 이로써 \(P\)가 \(s\)에서 \(v\)로 향하는 최단 경로가 됨을 보였습니다.
마지막으로 \(\pi[v]\)는 \(P\)에서 \(v\)의 바로 직전 정점인 \(u\)로 설정된다는 것을 확인하시기 바랍니다. ■
위 정리들을 통해 우리는 A* 알고리즘에 일관적인 휴리스틱이 주어지면 항상 \(s\)에서 \(t\)로 가는 최단 경로를 출력함을 알 수 있습니다. 이 알고리즘의 시간 복잡도는 다익스트라의 알고리즘과 동일합니다.
직관적 이해
이전 절에서 우리는 어떻게 A* 알고리즘이 적절한 휴리스틱을 활용하여 다익스트라의 알고리즘보다 목적지까지의 최단 경로를 더 빠르게 찾을 수 있는지 논의하였습니다. 또한 휴리스틱이 일관적이라면 항상 최단 경로를 보장한다는 것을 증명하였습니다. 이번 절에서는 일관적인 휴리스틱을 입력 받은 A* 알고리즘이 어째서 다익스트라의 알고리즘보다 빠르게 목적지까지의 최단 경로를 찾을 수 있는지 예시 도식과 함께 직관적으로 알아 보도록 하겠습니다.
앞에서 살펴 본 예시 그래프에 다음과 같은 휴리스틱이 주어졌다고 해 보겠습니다.
이 휴리스틱은 일관적입니다. 이 입력에 대해 A* 알고리즘을 수행하면 어떻게 될까요? 알고리즘이 \(t\)를 찾았을 때 끝내지 않고 우선순위 큐 \(Q\)에 남은 게 없을 때까지 수행했다고 해 보겠습니다. 그러면 각 정점 \(v \in V\)가 \(S\)에 들어갔을 때, 정리 3에 의해, \(f[v]\)는 \(s\)에서 \(v\)까지의 최단 경로의 비용(\(d[v]\))과 그 정점에서의 휴리스틱 값(\(h(v)\))의 합이 되고 끝날 때까지 죽 유지됩니다. 또 흥미로운 사실은 휴리스틱이 일관적이라면 A* 알고리즘도 정리 1과 같은 단조성을 갖는다는 것입니다.
정리 4. \(f[v]\)의 단조성
휴리스틱이 조건 (1)을 만족한다고 하자. 두 정점 \(v, v' \in S\)에 대해, 알고리즘 2에서 \(v\)가 \(v'\)보다 먼저 \(S\)에 들어갔다면, \(f[v] \leq f[v']\)이다.
[증명] 일반성을 잃지 않고 \(v\)가 \(S\)에 들어간 직후 \(v'\)이 \(S\)에 들어간 경우에 대해서만 정리가 성립함을 보이겠습니다. 알고리즘에서 \(v\)가 \(S\)에 들어갔을 때를 생각해 보겠습니다. 만약 단계 6-iv에 의해 \(d[v']\)와 \(f[v']\)의 값이 변경되었다면, 분명히 \[ f[v'] = d[v'] + h(v') = d[v] + c(v, v') + h(v') \geq d[v] + h(v) = f[v] \]를 만족하여 정리가 성립합니다. 이때, 부등식은 휴리스틱의 일관성 때문에 성립합니다. 반대로 \(f[v']\)의 값이 변경되지 않았다고 해 보겠습니다. 그러면 \(v\)가 \(S\)에 들어가기 직전에도 \(f[v']\)의 값은 동일하였을 것입니다. \(Q\)는 우선순위 큐이므로 \(f[v] \leq f[v']\)이 성립합니다. ■
이를 통해서 우리는, 다익스트라의 알고리즘에서와 마찬가지로, \(S\)가 확장되어 가면서 \(S\)의 정점들이 같은 \(f[v]\) 값을 기준으로 등고선을 이룬다는 것을 알 수 있습니다. 위 예시에 대해서 적용을 하면 아래와 같은 도식을 얻을 수 있습니다.
A* 알고리즘에서도 다익스트라의 알고리즘과 마찬가지로 출발지 \(s\)에서 점차적으로 퍼져 나가는 모습을 확인할 수 있습니다. 하지만 그림 2와 그림 4의 가장 큰 차이점은 목적지 \(t\)가 포함된 때입니다. 그림 2에서는 다른 모든 정점보다 \(t\)가 \(S\)에 포함되는 것이 늦지만, 그림 4에서는 \(s\)의 왼쪽과 아래쪽 정점들보다 \(t\)가 먼저 \(S\)에 들어갑니다. 그러므로 다익스트라의 알고리즘에서보다 A* 알고리즘에서 더 일찍 \(s\)에서 \(t\)로 향하는 최단 경로를 찾게 되는 것입니다.
이 현상을 보다 직관적으로 설명해 보죠. 다익스트라의 알고리즘은 목적지의 위치에 대한 아무런 정보도 없기 때문에, 편평한 물 위에 물방울 하나를 톡 떨어뜨렸을 때와 같이 출발지에서 동심원을 그려 가면서 목적지를 찾아 가는 알고리즘이라고 생각해 볼 수 있습니다. 반면 일관적인 휴리스틱은 이러한 동심원들의 위상이나 순서는 유지하면서 목적지 쪽으로 원들을 일그러뜨리는 역할을 한다고 보면 좋겠습니다. 동심원들의 위상이나 순서가 유지된다는 뜻은, 안쪽의 동심원이 일그러지면서 그보다 바깥에 있는 원을 침범하지 않는다는 것입니다. 따라서 A* 알고리즘은 이렇게 일그러진 동심원들을 순서대로 방문하는 것으로 더 빠르게 목적지에 도달할 수 있게 됩니다.
마치며
이것으로 A* 알고리즘에 대한 설명을 모두 마칩니다. 예전 인공지능 수업을 들을 때 수박 겉 핥기 식으로 배웠던 것에 이렇게 흥미로운 내용들이 숨어 있었어서 적잖이 놀랐습니다. 이번 기회에 A* 알고리즘의 동작 원리를 잘 이해하게 된 것 같아서 기쁩니다.
서두에서 밝혔듯이 본문의 내용은 제가 공부한 내용을 제 방식으로 재해석한 것으로 인공지능 교과서에서 일반적으로 볼 수 있는 내용은 아니리라 생각합니다. 적어도 제가 참고했던 교과서에서는 제 방식과 달리 상태 공간(state space)에서의 탐색 트리(search tree)를 활용하여 A* 알고리즘을 분석하였습니다. 게다가 적절한 휴리스틱이 만족해야 하는 성질도 몇 가지 빼 먹었는데, 언급하자면 아래와 같습니다.
- 목적지 \(t\)에서 휴리스틱 \(h\)는 \(h(t) = 0\)을 만족시키면 좋습니다. 그러면 \(f[t]\)의 값이 곧 최단 경로의 길이와 같습니다. 또한, 휴리스틱 \(h\)가 각 정점에서 목적지 \(t\)까지 도달하기 위해 남은 경로의 대략적인 비용이라는 의미와도 맞아 떨어집니다. 이미 목적지에 도착했으니 그 비용은 0이 되는 것이 적합하겠습니다.
- 휴리스틱은 "낙관적인" 것이 좋습니다. 다시 말하면, 임의의 \(v \in V\)에 대해, \(h(v)\)는 \(v\)에서 \(t\)까지 향하는 최단 경로 비용보다 더 저렴한 값을 갖는 것이 좋다는 뜻입니다. 만약 더 비싼 값을 가졌다고 해 보겠습니다. 그러면 A* 알고리즘의 입장에서 \(f[v]\)의 값은 원래 \(s\)에서 \(v\)를 거쳐 \(t\)로 가는 최단 경로의 비용보다 더 비싼 값이 들어갈 것입니다. 그러면 알고리즘이 \(v\)를 방문하는 것이 올바른 선택임에도 잘못된 휴리스틱으로 인해 방문하지 않는 상황이 발생할 수 있겠습니다. 이 조건을 특별히 휴리스틱의 허용성(admissibility)이라고 부릅니다.
이 두 조건은 매우 일반적인 조건이지만, 본문의 증명에서는 활용되지 않아서 과감히 제외하였습니다. 다만, 한 가지 더 언급하자면, 어떤 휴리스틱이 목적지에서 0의 값을 가지면서 일관적이라면, 그 휴리스틱은 허용 가능(admissible)하다는 점입니다.
정리 5. 휴리스틱의 일관성과 허용성
목적지에서 0의 값을 갖는 일관적인 휴리스틱은 허용 가능하다. 즉, \(h(t) = 0\)이면서 조건 (1)을 만족하는 휴리스틱 \(h\)는 임의의 \(v \in V\)에 대해, \(h(v)\)의 값이 항상 \(v\)에서 \(t\)로 가는 최단 경로의 비용을 넘지 않는다.
[증명] 만약 \(v\)에서 \(t\)가 도달 가능하지 않다면 비용은 \(\infty\)이므로 정리는 자연스레 성립합니다. 이제, \(v\)에서 \(t\)로 가는 최단 경로를 \(P\)라고 하고, 그것의 정점들을 순서대로 \(v_1 := v, v_2, \ldots, v_k, v_{k + 1} := t\)라고 해 보겠습니다. 그러면 각 \(i = 1, \ldots, k\)에 대해, 조건 (1)에 의해 \(h(v_i) \leq c(v_i, v_{i + 1}) + h(v_{i + 1})\)이 성립하므로, 이를 모두 더하면, \[ h(v) \leq \sum_{i = 1}^k c(v_i, v_{i + 1}) + h(v_{k + 1}) = c(P) \]를 얻을 수 있습니다. 여기서 등식은 \(h(v_{k + 1}) = h(t) = 0\)이기 때문에 성립합니다. ■
추가로 목적지가 하나가 아닌 여러 개가 있는 경우도 생각해 볼 수 있습니다만, 이는 새로운 목적지를 하나 만들고 기존의 모든 목적지에서 새로운 목적지로 향하는 비용이 0인 간선을 만듦으로써 해결이 가능합니다.
읽어 주셔서 고맙습니다.
참고 문헌
[1] Stuart Russell and Peter Norvig. Artificial intelligence: a modern approach (4th Edition). Pearson, 2020. (국문 번역본: 류광 옮김, 제이펍)
'조합론적 최적화 > Shortest path' 카테고리의 다른 글
| 다익스트라의 알고리즘 (Dijkstra's Algorithm) (0) | 2021.10.09 |
|---|---|
| 최단 경로 문제 & 벨만-포드 알고리즘 (Shortest Path Problem & Bellman-Ford Algorithm) (1) | 2021.08.22 |
