내용 보기
1. Informed search란?
Uninformed search는 넓은 범위의 문제에 곧바로 적용할 수 있는 방법이나, 문제의 크기가 조금만 커져도 체크해야 하는 상태와 해답에 대한 경우의 수가 기하급수적으로 늘어나는 치명적인 단점이 있다. 이를테면 이전에 알아보았던 청소기 문제에서 2x1 크기에서 가능한 상태의 수는 8개이지만 이 것이 2x2로 늘어나면 64, 3x3으로 늘어나면 4608, 4x4로 늘어나면 1048576개에, 가능한 경로의 수는 헤아리기 어려울 정도이다. 이는 해당 문제에 대한 정보가 전혀 없기 때문에 가능한 모든 경우의 수를 고려해야 하기 때문에 발생하는 일로, 이는 마치 캄캄한 미로에서 출구를 찾는 것에 비유할 수 있다.
하지만 만약 미로의 지도를 주고, 그 지도에서 출구까지의 경로를 찾는 문제라면 이는 훨씬 쉬운 문제가 된다. 미로에 대한 정보가 주어진 상태이기 때문이다. 이처럼 모든 문제에 있어서 아무런 정보가 주어지지 않는 것은 아니다. 이를테면 주어진 지도에 대해 최적 경로를 찾아야 한다고 가정해보자. 이 경우 아주 특수한 경우가 아닌 이상 서울에서 대전까지 가는데 부산을 경유하는 경로를 고려해야 할 까닭은 없다. 직관적으로 볼 때 이는 서울에서 대전까지 가는 거리에 비해 서울에서 부산까지 가는 직선 경로가 훨씬 길기 때문에 애초에 경로를 탐색할 때 초반부터 고려 대상에서 제외할 수 있는 것이다.
이 때 서울에서 부산까지의 직선 거리는 실제 거리와는 좀 차이가 있겠지만 실제 거리와 밀접한 상관 관계를 가지므로 적절하게 활용하면 최적 해답을 찾는데 큰 도움이 될 수 있다. 거리에 대한 예상 정보는 컴퓨터 스스로 논리적인 절차를 통해 알아낸 정보가 아니라 사람에 의해 따로 '발견된' 정보이므로 휴리스틱 함수라 한다. 휴리스틱 함수는 보통 특정 상태와 목표 상태 사이의 예상 비용을 계산하는 함수로, 엄밀하게 수학적, 논리적인 절차를 통해 구해낸 함수일 수도 있고 경험과 실험을 통해 얻어낸 함수일 수도 있다. (단, 뒤에서 언급하겠지만 후자의 경우는 최적의 해답을 찾지 못할 가능성도 있다.)
적절한 휴리스틱 함수가 주어진다면 (혹은 구한다면) 문제를 훨씬 빠르게 풀 수 있다. Uninformed search를 하면서 불필요하게 탐색 대상으로 오르는 상태들을 제거하기만 해도 지수적으로 증가하는 시간 복잡도에서 밑 값이 크게 줄어들기 때문이다.
2. Best-first search
앞에서도 말했지만 휴리스틱 함수는 실제 해답의 비용과 밀접한 연관 관계를 맺는 경우가 대부분이다. 따라서 이 함수를 이용하면 주어진 여러 개의 상태(state) 중 어느 경우가 가장 목표에 가까울지를 예측해 볼 수 있다. (아래부터 우리가 다루는 것은 결과적으로 트리 탐색, 혹은 그래프 탐색과 같으며, 이 때 각 상태는 선택한 행동에 따라 추가되는 노드로 볼 수 있으므로 편의상 노드라 하자.)
우리가 원하는 것은 목표에 최적의 경로로 접근하는, 즉 최적의 해답을 구하는 것이다. 여지까지 알아본 탐색 알고리즘들에서 다음 번에 확인할 노드를 고르는 기준은 LIFO(DFS), FIFO(BFS), 행동(Uniform-cost search)의 비용 세 가지 뿐 이었다. 만약 이 기준에 휴리스틱 함수를 활용한다면 어떨까? 직관적으로 볼 때, 목표 지점까지 최대한 가까운 경로로 이동하기 위해서는 현 상태에서 '목표에 가장 가까워 보이는 노드'로 전이하는 방법은 충분히 설득력이 있어 보인다. 이러한 아이디어에서 나온 것이 바로 Best-first search이다.
이 때 휴리스틱 함수 h(n)을 특정 노드 n에서 목표까지 경로의 예상 비용이라 두자. 위에서 언급한 길 찾기 문제라면 h(n)은 현재 위치와 목표 위치 사이의 유클리드 거리로 표현할 수 있을 것이다. 이 경우 기존의 Uninformed search에서 다음 번 노드를 고르는 기준은 h(n)이 최소값인 경우로, 기존 알고리즘에서 h(n)을 키 값으로 하여 다음 번 노드를 우선 순위 큐에 넣는 방법으로 쉽게 구현할 수 있다. 이는 현 상태의 정보만을 토대로 최적의 행동을 수행하기 때문에 Greedy 알고리즘으로 분류된다.
그러나 이 알고리즘에는 문제가 있다. 앞서 탐색 방법을 평가하는 기준으로 completeness, optimality를 들었는데, 둘 다 성립하지 않는다. 우선 문제에 따라서는 무한 루프에 빠질 우려가 있기 때문에 complete하지 않다. 예를 들어 특정 그래프가 있는데, 휴리스틱 함수에 따르면 노드 a는 목표 지점까지 10의 거리를 가지고 있고, b는 20의 거리, c는 30의 거리를 가지고 있으며 a - b - c - (그래프) - 목표와 같이 연결되어 있다고 치자. (⊃꼴을 상상하면 될 것이다.) 여기에 길찾기를 위해 Best-first search를 적용해보자. b가 시작 지점인 경우, a와 c 중 가장 작은 휴리스틱 값을 가진 a로 이동하며, a로 이동한 뒤에는 이동할 수 있는 노드가 b 밖에 존재하지 않으므로 다시 b로 이동할 것이다. 이런 식으로 무한 루프가 발생할 수 있기 때문에 답을 얻을 수 없는 경우가 존재한다. 또한 Greedy 알고리즘의 특성 상 최적 해답 역시 보장되지 않는다.
3. A* search
- 소개
위와 같은 이유로 Best-first search는 실제 활용되기 어렵다. 이 때 문제의 가장 큰 원인은 아이러니하게도 다음 번에 전이할 노드를 선택하는 기준이 휴리스틱 함수 뿐이라는 것이다. Greedy한 알고리즘의 특성 상 다음 번 노드를 택하는 기준으로 휴리스틱 함수 자체는 괜찮은 선택일지언정 전체 경로를 찾는데에는 부적합하다. 해답을 찾아내는 과정에 실제 거쳐온 경로의 거리가 전혀 반영되지 않기 때문이다.
그렇다면 다음번 노드를 택할 때 uniform-cost search와 같이 현재 노드까지 오는데 소모된 비용도 같이 반영하는 것은 어떨까? 이러한 아이디어에서 나온 방법이 바로 A* search이다. 우선 다음번 노드를 택할 때 사용할 평가 함수를 아래와 같이 정의하자.
- g(n) : 노드 n까지 도착하는데 소요된 비용
- h(n) : 노드 n에서 목표까지 가는데 소모될 것으로 예상되는 비용
- f(n) : 노드 n을 거치는 경로에서 목표까지 가는데 소모될 것으로 예상되는 비용
이 때 f(n) = g(n) + h(n)이다. 직관적으로 봐도 이렇게 예상되는 전체 경로의 거리를 토대로 다음 노드를 택하는 것이 '목표에 가장 가까워 보이는 노드'를 택하는 것보다는 합리적이다. 또한 Best-first search를 이용하는 경우에 발생하는 무한 루프 역시 이 경우 실제 비용이 반영되므로 자연스레 도태되어 completeness 역시 보장된다. (단, 목표에 도달하기 위한 노드가 무한히 많은 경우는 예외이다.)
- 성질
그렇다면 optimality는 어떨까? A* 알고리즘은 이론적으로 최적의 해답을 도출할 수 있는데, 이 때 전제 조건이 있다. 휴리스틱 함수 h(n)이 용납될 수 있어야(admissible) 하는 것이다. 이 조건을 구체적으로 설명하자면, h*(n)이 n에서 목표까지의 실제 거리의 함수라면 h(n) ≤ h*(n)일 것이다. 이 경우 용납될 수 있는 휴리스틱 함수(admssible heuristic function)이라 하며, h(n)은 실제 비용을 과대평가(overestimate)하지 않는다 표현한다.
어째서 optimality가 보장되는 지에 대해 생각해보자. 목표까지 가는 경로 중에는 최적의 경로 G1과 최적이 아닌 노드 G2가 존재할 것이다. 이 때 최단 경로 위에 존재하는 경로 중 임의의 하나를 잡아 n이라 하자. 이 때 G2는 목표에 도달했으므로 h(G2) = 0, 따라서 f(G2) = g(G2)이며, G2는 최적 경로가 아니므로 g(G2) ≥ g(G1)이다. g(G1) = g(n) + h*(n) ≥ g(n) + h(n) = f(n) 이므로 f(G2) > f(G1) ≥ f(n)이며, 따라서 n을 선택하기 이전에는 G2가 다음 노드로 선택될 일은 없다. 고로 optimality가 보장되는 것이다.
휴리스틱 함수의 조건 중 하나로는 일관성(consistency)이 있다. 노드 n과 그 다음 노드 n'가 있다 할 때 h(n) ≤ d(n, n') + h(n')인 경우 일관성을 만족한다고 하는데, 이를 만족하는 경우 f(n') ≥ f(n)이 되어 f(n)은 값이 감소하지 않는 함수가 된다. 일관성은 용납 가능함에 비해 더 엄격한 조건으로, 이런 함수를 휴리스틱으로 사용하는 경우 f는 절대 감소하지 않으므로 동일한 경로를 두 번 이상 계산할 여지가 사라져 더욱 효율적인 계산이 가능하게 된다. (사실 대부분의 용납 가능한 함수는 일관성 역시 만족한다.) 또한 일관성은 그래프 탐색을 이용한 A* 알고리즘에서 더더욱 중요해지는데, 그래프 탐색을 이용하는 경우 일관성을 만족하는 경우 optimality를 만족하기 때문이다.
- 휴리스틱 함수
A* 알고리즘을 적용하는 데에 있어 중요한 것은 휴리스틱 함수를 구하는 것이다. 최적 해답을 구하기 위해서는 휴리스틱 함수는 용납 가능해야 한다. 그러나 단순히 용납 가능하기만 해서는 A* 알고리즘을 적용하는 의미가 없다. 이를테면 h(n) = 0 인 경우도 용납 가능한 휴리스틱 함수이지만, 실상을 알고 보면 Uniform-cost search와 똑같다. 즉, h(n)을 얼마나 잘 만드느냐에 따라 최적 해답을 구하기 위한 비용이 결정되는 것이다.
물론 가장 이상적인 경우라면 휴리스틱 함수와 실제 비용이 똑같은 경우겠지만, 이를 쉽게 구할 수 있었다면 Search 알고리즘을 적용할 까닭이 없었을 것이다. 휴리스틱 함수를 정하는 것은 생각보다 쉽지 않은 일로, A* 알고리즘 자체를 구현하는 것 보다 휴리스틱 함수를 정하는 것이 더 어려운 경우가 대부분이다.
이 때 휴리스틱 함수를 정하는 테크닉 중 하나로는 문제의 조건 중에서 일부를 삭제한 뒤 변경된 문제에서의 비용을 구하는 것이다. 설명이 좀 추상적인데, 길 찾기 문제를 예로 들자면 이는 문제의 조건에서 특정 경로를 따라간다는 조건을 삭제하고 직선 거리로 이동하는 것을 허용한 뒤 유클리드 거리를 계산하는 방식으로 비용을 구하였다.
어떤 경우에는 최적 해답을 구하는 것 보다는 해답 자체를 빠르게 구하는 게 더 중요할 수 있는데, 이 경우는 h(n)이 용납 가능하지 않아도 된다. 일반적으로 h(n)이 클수록 A*에서 답을 찾아내는 속도가 빨라지는 경향이 있는데, 이를 토대로 이미 사용하고 있는 h(n)의 값에 1보다 큰 상수를 곱하여 더 빠르게 답을 구하는 것도 가능하다. 이 때 h(n) + c ≤ h*(n), 최적 해답의 비용을 f(G1) 구한 해답의 비용을 f(G2)라 할 때 f(G2) ≤ f(G1) + c임이 보장된다.
