A* Search를 처음 접하는 사람들을 위해, 기본적인 BFS에서 시작해 A* Search를 설명하는 글입니다 👍

개념을 이해하기 위한 글과 사진 그리고 조금의 식만 있으며 직접적인 코드를 다루지는 않습니다!

Search Algorithm

프로그래밍을 하고, 코딩 테스트를 준비하다 보면 적어도 한 번 쯤은 들어봤을 법한 유명한 알고리즘이 2개 있다. 바로 DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)이다.

이 두 알고리즘은 이름에서 나타나 있듯이, 탐색 알고리즘에 속한다. 그렇다면 탐색 알고리즘은 무엇일까?

탐색 알고리즘은 그래프에서 구현되며, 한 노드에서 출발해 그래프 내의 노드 중 종료 조건에 부합하는 노드를 찾는 알고리즘이다. 이 과정에서 출발지로부터 도착지까지의 거리를 구하거나, 이제까지의 경로를 구하는 계산도 자주 동반된다.

탐색 알고리즘의 공통적인 요소가 있는데, 바로 모든 탐색은 우선순위 큐를 사용하며, 이 큐에서 노드 하나를 가져와 확인하고 이 큐에 해당 노드의 자식 노드들을 다시 넣는 expension 과정을 반복하는 알고리즘이다.

또한 그래프 탐색에서는 효율을 위해 방문 여부를 저장한다.

BFS

많은 사람이 들어봤을 Breadth First Search은 너비 우선 탐색으로 우선순위 큐의 우선순위가 시작 노드로부터의 거리이다. 이때 모든 간선의 비용은 1로 동일하다고 가정하기 때문에, 트리의 경우 아래와 같은 순서의 탐색이 가능해진다.

노드의 번호는 탐색하는 순서이며 이는 구현에 따라 조금씩 달라질 수 있다.

BFS에서는 우선순위가 시작 노드로부터 얼마나 가까운지에 따라 결정되기 때문에, 일반적인 Queue를 이용해서 구현할 수 있다.

Uniform Cost Search

Uniform Cost Search는 BFS와 동일한 우선순위 조건을 가지지만, 각 간선의 가중치가 동일하지 않은 경우에 해당한다.

다익스트라 알고리즘은 동일한 방법을 사용해 MST를 생성하는 알고리즘이다. 차이점이라면 탐색의 경우에 원하는 종료 노드를 찾음과 동시에 종료되지만 다익스트라 알고리즘은 모든 노드를 연결하기 전까지 계속 이 과정을 반복한다.

BFS와 동일하게 일반적인 Queue를 이용해 구현할 수 있다.

Un-informed vs Informed

앞서 살펴본 두 가지 알고리즘은 현재 노드가 시작 노드로부터 얼마나 떨어져있나를 기준으로 작동한다. 따라서 이 알고리즘들은 현재 노드가 종료 노드와 얼마나 가까운지에 대한 정보를 전혀 사용하지 않는다.

BFS, Uniform Cost Search와 같이 Un-informed Search라고 하며, 이와 반대로 현재 노드로부터 종료 노드 사이의 정보를 사용하는 탐색 알고리즘을 Informed Search라고 한다.

Greedy Search

가장 유명한 Informed Search인 Greedy Search는 이전 두 알고리즘과 반대로 오직 현재 노드와 종료 노드 사이의 정보만을 사용해 작동한다.

예를 들어 아래와 같은 2차원 그리드에서 물체가 상하좌우로만 이동 가능하다고 할 때, X 표시가 있는 목적지로 가는 경로를 찾아보자.

현재 좌표로부터 목적지 좌표가 얼마나 가까운지를 계산한 다음 거리가 가까워지는 위치로 이동하는 걸 반복하면 목적지로 가는 경로를 쉽게 찾을 수 있다. 가령 거리를 측정하기 위해 맨해튼 거리를 사용한다고 하면 $d = |x_1 - x_2| + |y_1 - y_2| = 4 + 2 = 6$이 될 것이다.

그리드의 전체 정보를 아는 우리로서는 이런 식으로 경로를 찾는 것이 너무나 당연한 선택이다.

이러한 종료 노드의 정보를 토대로 탐색하는 알고리즘이 바로 Greedy Search이며, Greedy Search에서의 우선순위는 BFS와는 다르게 얼마나 출발 노드로부터 가까운가가 아닌, 얼마나 도착 노드와 가까운가이다.

그렇다면 이 탐색은 언제나 효율적일까? 아래의 예시를 살펴보자, 종료 노드로 가는 과정에 벽이 있어 해당 구간을 지날 수 없는 상황이다.

우리는 다음 그림과 같이 아래로 내려갔다가 다시 위로 올라가는 경로를 답이라고 쉽게 유추할 수 있다.

하지만 Greedy Search의 경우에는 얘기가 다르다. 매 순간마다 종료 노드로 가까워지려고 노력하기 때문에 다음과 같은 탐색을 하게 된다. 한 눈에 봐도 최적 경로와는 거리가 먼 것을 알 수 있다.

이렇듯 Greedy Search의 단점은, 매 순간마다 당장 최선의 선택을 하기 때문에 최적의 결과를 보장하지 않는다는 것이다. 반대로 BFS의 경우 최적해를 항상 보장하는 대신 탐색 시간과 공간을 더 많이 필요로 한다.

A* Search

A* Search은 시작 노드로부터 현재 노드까지의 거리와 현재 노드로부터 도착 노드까지의 거리를 모두 사용해서 탐색 시간을 줄이고, 최적해를 보장하는 탐색 알고리즘이다.

위에서 설명한 Uniform Cost Search, Greedy Search의 아이디어를 전부 사용한다.

Hueristic Function

A* Search의 우선순위는 다음과 같은 공식에 의해 결정된다.

$f(n) = g(n) + h(n)$

여기서 $n$은 현재 노드, $g(n)$은 현재 노드가 시작 노드로부터 떨어진 거리, $h(n)$은 현재 노드와 종료 노드 사이의 예상 거리를 계산하는 휴리스틱 함수다.

앞서 살펴본 Uniform Cost Search의 경우에는 $f(n) = g(n)$인 것이고, Greedy Search의 예시는 $f(n) = h(n) = |x_{end} - x_n| + |y_{end} - y_n|$인 것이다.

이러한 휴리스틱 함수는 A* Search의 가장 중요한 부분이며, 각 문제 상황에 대한 이해를 바탕으로 직접 구현해야 한다.

앞서 예시로 든 미로찾기 같은 경우에는 각 노드 사이를 이동하는 비용이 모두 동일하기 때문에 BFS와 Greedy Search를 혼합한 형태로 알고리즘이 구현된다.

위 이미지는 2차원 그리드에서 Uniform Cost와 A*가 얼마나 많은 경우의 수를 탐색하는지를 시각화한 그림이다. 한눈에 봐도 탐색하는 양의 차이가 많다는 것을 알 수 있다.

Optimality

다만 A* Search는 최적해를 보장하지 않는다. 유한한 그래프 내에서 최적해를 보장하기 위해서는 휴리스틱 함수가 다음의 조건을 꼭 만족시켜야 한다.

Admissible

트리 탐색의 경우로만 한정했을 때, A* Search는 휴리스틱 함수가 admissible 할 경우에 최적해를 보장한다.

이는, 휴리스틱 함수가 현재 노드로부터 종료 노드까지의 거리를 과대평가하지 않는다는 뜻이다. 이는 식으로 나타내면 다음과 같다.

$h(n) \le h(n)^{*}$

여기서 $h(n)^*$는 현재 노드에서부터 종료 노드까지의 실제 거리를 의미한다.

예를 들어, 2차원 그리드 공간에서 맨해튼 거리 또는 유클리드 거리는 벽이 있는 경우에도 현재 노드로부터 종료 노드까지의 거리를 절대 과대평가하지 않는다.

위의 예시를 보면 벽이 존재하는 경우에도 실제 거리는 휴리스틱 함수의 값보다 멀거나 같게 된다.

Consistent(monotonic)

그래프 탐색의 경우에는 휴리스틱 함수의 조건이 조금 더 까다로워지는데, 휴리스틱 함수가 consistent 해야 한다. 이는 "휴리스틱 함수가 단조 증가한다"라고 이해해도 좋을 것 같은데 식은 아래와 같다.

$h(n) \le c(n, n') + h(n')$

이는 2차원 평면 공간에서 삼각 부등식과 동일한 의미이며, $n'$은 노드 $n$에서 진행할 수 있는 임의의 노드이고 $c(n, n')$은 노드 $n$에서 $n'$ 사이의 실제 거리이다.

추가적으로 consistent한 휴리스틱 함수는 반드시 admissible 하다. 일반적으로 구간을 나눠서 휴리스틱 함수를 정의하지 않았다면, 두 가지 조건을 같이 성립하는 경우가 많다.

어떻게 휴리스틱 함수를 떠올리는가?

앞서 예시로 들었던 2차원 평면의 미로찾기 문제 같은 경우에는 흔한 예제라서 쉽게 '맨해튼 거리나 유클리드 거리를 사용하면 되겠네!'가 떠오른다.

하지만 익숙하지 않은 문제들에 대해 휴리스틱 함수를 설계할 때에는 다음의 방법을 사용하면 된다.

다음과 같은 문제에 대해 휴리스틱 함수를 어떻게 설계할지 생각해보자.

Start State에서 타일을 빈 칸으로 밀어 Goal State를 만드는 게임이다. 우리는 어떤 순서대로 밀어야 Goal State를 만들 수 있는지 찾아야 한다.

문제 조건 완화하기

문제의 조건을 완화해 타일의 위치들을 임의로 변경할 수 있다고 해보자. 그리고 $h(n)$을 현재 상태에서 Goal State와 위치가 다른 타일의 개수로 정의하자. 그렇다면 이 휴리스틱 함수는 consistent한 휴리스틱 함수가 된다.

또 다른 예시로는 현재 상태에서 모든 번호 타일들의 위치가 Goal State와 맨해튼 거리로 얼마나 차이나는지 더하는 방법이 있다.

$h(n) = \Sigma_i d_i$

이 휴리스틱 함수또한 consistent한 휴리스틱 함수이다.

그렇다면 이런 생각을 할 수 있다.

두 경우 모두 최적해를 보장하는 휴리스틱 함수 아닌가? 어떤 걸 골라야 하지?

두 휴리스틱 함수 $h_1$, $h_2$가 있을 때 모든 노드 $n$에 대해 $h1(n) \ge h2(n)$을 만족할 경우, $h1$이 $h2$를 dominate 했다고 하며, $h_1$을 휴리스틱 함수로 고를 때 더 적은 연산으로 답을 구할 수 있다.

앞서 예시 중 첫 번째 함수는 $h(n) \le 8$이지만, 두 번째 함수는 함수값이 더 크거나 같기 때문에 두 번째 함수를 고르는 것이 효율적이다.

부분 문제 풀기

휴리스틱 함수를 정의하는 또 다른 한 가지 방법으로 문제를 전체를 푸는 것이 아니라, 일부만 푸는 방법이 있다.

예를 들어, 1부터 9까지 모든 타일을 Goal State에 배치하는 것이 아닌, 1에서 4까지의 타일만 Goal State와 동일하게 만들고 나머지 타일은 동일한 타일로 취급한다면 이 휴리스틱 함수 또한 consistent한 함수가 된다.

마치며

결론적으로 A* Search는 Uniform Cost Search와 Greedy Search를 결합한 중간 형태의 탐색 알고리즘이다. 위 두 알고리즘은 쉽게 이해할 수 있기 때문에 이러한 방식을 사용해 A* Search를 구현하는구나 이해하면 되겠다.

이 글이 A* Search를 처음 접하는 사람들에게 도움이 됐으면 좋겠다. 항상 최적해를 찾을 수 있다는 것에 대한 증명은 생략했는데 증명이 굉장히 직관적이기 때문에, 관심있는 사람들은 증명도 한번 찾아보면 좋을 것 같다.

또 A* Search의 변형 알고리즘 종류도 몇 가지 있는데 대표적으로 다음과 같은 알고리즘이 있다.

• Anytime A*
• Beam Search
• Iterative Deepening A*
• Simplified Memory-Bounded A*