탐색 알고리즘
1. 개요
방대한 데이터에서 목적에 맞는 데이터를 찾아내기 위한 알고리즘. 일반적으로 탐색 알고리즘이라고 하면 트리 검색 알고리즘을 떠올리는 경우가 많으나, 탐색 알고리즘의 이론적인 정의는 본 문서와 같은 다양한 범위를 포함한다.
초기의 컴퓨터는 단순한 계산의 편의성을 높이기 위해서 만들어졌으나, 컴퓨터의 유용성을 인식한 수학자들이 더 많은 문제를 컴퓨터를 통해서 해결하기 위하여 문제의 논리적 해결법을 컴퓨터에 적용하면서 탐색 알고리즘 분야가 널리 활용되기 시작했다.
탐색 알고리즘을 적용하기 위해서는 논리적인 문제 정의 방법을 통해 해당 문제가 어떤 종류의 문제인지를 평가하여야 하며, 탐색 알고리즘이 해결할 수 있는 문제의 종류는 제약 만족 문제, 트리 탐색 문제, 경쟁 문제, 국소 탐색 문제 등으로 분류된다.
일반적으로 컴퓨터를 통해서 특정한 영역에 도움을 주는 프로그램을 구현한다면 의도하지 않아도 자신도 모르게 특정 알고리즘을 사용하고 있는 경우가 대부분일 정도로 탐색 알고리즘이 정의하고 있는 영역은 그 범위가 넓으며, 반대로 탐색 알고리즘에서 말하는 특정 알고리즘을 공부할때에는 고작 이런 걸 알고리즘이라고 불러도 되나 싶은 수준의 알고리즘도 존재한다.
하지만 체계적으로 프로그램을 구현하고, 개발자들간의 의사소통의 편의성을 위해서 특정 프로그램 단위를 부르는 이름이 존재한다는 것은 여러모로 유용한 면이 있으므로, 프로그램 개발자로서 일정 수준을 넘어가기 위해서는 한번쯤은 거쳐야 하는 이론 기반에 해당한다.
2. 분류
아래는 탐색 알고리즘의 대표적 분류에 대한 정의를 나열한다.
2.1. 제약만족 문제(Constraint Satisfaction Problem)
문제의 해가 주어진 제약조건을 만족하는 형태로 정의되는 종류의 문제들을 칭하며, 대표적인 문제로 4색 문제[1]나 아인슈타인 문제[2] 등이 이에 포함된다.
제약 만족 문제는 값을 지정할 수 있는 변수, 변수 내에 할당할 수 있는 값의 정의역, 문제의 해로서 만족해야 하는 제약조건들 등으로 문제가 구성된다.[3]
제약 만족 문제를 해결하기 위한 전략은 트리 탐색 문제와는 달리 문제를 푸는 방법이 다양하지 않으며, 무언가 드라마틱한 해결 방법이 전혀 아닌 단지 하나씩 변수에 값을 대입해보는 가정법을 통해 연역적으로 문제를 해결하는 방법 밖에는 존재하지 않는다. 다만 변수에 값을 대입하는 순서를 선택할때 더 유리한 방법에 대해 이론적으로 연구된 바가 있어 제약만족 문제에 적용되고 있다.
2.1.1. 최소 제약 값 선택법
어떠한 변수에 값을 할당할때 주변에 가장 적게 영향을 끼치는 값을 선택해야 하는 전략을 말한다. 주변에 영향을 적게 끼치는 값은 일반적으로 문제의 해가 될 가능성이 높은데, 반대로 많은 제약을 끼치는 값을 선택하게 되면 탐색을 진행함에 따라 다른 변수에 값을 선택할 수 있는 폭이 줄어들기 때문에 해를 찾지 못할 가능성이 높아지게 된다. 제약만족 문제는 아주 아름다운 해를 찾기 보다는 해당 제약조건을 만족하기만 하면 충분하기 때문에 이러한 방법을 선택하는 것이 유용하다.
2.1.2. 최대 제약 변수 선택법
값을 할당하기 위한 변수를 선택할때 인접한 변수가 가장 많은 변수를 우선적으로 선택하는 전략을 말한다. 인접해 있는 변수가 많은 변수를 선택하게 되면 탐색에 따라 확인하게 되는 가상의 해가 제약조건을 만족하지 못하는 경우를 빠르게 찾아낼 수 있게 되는 장점이 있어, 문제 해결에 필요한 비용을 줄이는 데에 중요한 전략이라고 할 수 있다.
2.2. 트리 탐색 문제(Tree Search Problem)
일반적으로 탐색 알고리즘이라고 하면 트리 탐색 문제를 가장 먼저 배우며, 가볍게 탐색 알고리즘을 배운 사람이라면 제일 먼저 떠올리게 되는 문제의 종류이다. 트리 탐색 문제는, 그래프나 트리와 같은 자료구조로 구성되는 환경에서 목적지에 도달하기 위한 경로를 구하기 위한 문제이다.[4]
트리 탐색 문제는 BFS, DFS 와 같은 기초적인 알고리즘과 A*와 같은 비교적 복잡해 보이는 알고리즘이 일반적으로 유명하여 다양한 알고리즘 전략이 복잡하게 구성되어 있는 것으로 알고 있는 사람들이 많으나, 트리 탐색 문제의 분류는 상당히 체계적으로 구성되고, 각 분류간의 차이가 명확하므로 간단한 이해를 통해 트리 탐색 문제의 전체적인 구성을 파악할 수 있다.
트리 탐색 문제는 구하는 해의 최초 시작점(Initial State), 현재 상태가 최종 도착지인지를 확인하기 위한 해 평가(Goal Test), 하나의 상태에서 다른 상태로 옮겨가기 위해 선택해야 할 행동(Successor function), 추가적으로 필요하다면 선택지마다 소요되는 비용(Path Cost) 등으로 구성된다. 하나의 상태에서 다른 상태로 옮기기 위한 행동은 각 상태마다 다른데, 행동을 정의할때는 '어느 상태의 어떤 행동이 다른 어느 상태로 전이시킨다' 라고 정의하기 때문에 사실상 행동에는 상태의 정보까지 함께 포함된다.
트리에서는 하나의 요소를 노드라고 표현하는데 노드와 상태는 엄밀히 말하면 동의어는 아니다. 노드는 트리의 구성요소에 불과하며, 그 안에 어떤 정보를 담고 있는지에 대해서는 정의되지 않는 단순한 자료구조의 일부이다. 상태는 문제에서 정의되는 조건들이 포함된 정보의 구조로서, 예를 들어 길찾기 문제를 푸는 와중에 서울에서 대전으로 갔다가 길을 잃어 다시 서울로 돌아와 길을 찾고 있다고 가정한다면 현재의 노드는 서울을 루트노드로 펼처진 노드 중 대전 상태의 노드를 다시 펼쳤을때 나타난 서울 노드로 표현할 수 있지만 최초의 서울 노드와 깊에 3에 존재하는 서울 노드는 동일한 상태를 지니고 있다고 해석할 수 있다.
문제를 푸는 방법은 크게 세가지 영역으로 나뉘는데 그 기준은 다음의 수식을 통해 쉽게 이해할 수 있다.
$$ F(s) = g(s) + h(s) $$
위의 수식에서 s는 각 상태를 말한다. F는 평가 함수로서, 해당 상태가 답으로 구성되기 위하여[5] 적합한지를 나타내는 함수이다. g는 현재까지 지나쳐 온 행동들에 소모된 비용의 총 합이다.[6] 해당 상태의 h는 추정치(heuristic)로서, 문제에서 추가적으로 주어진 정보를 통해서 얻을 수 있는 값이다. 지도에서 경로를 찾는 문제를 예를 들면 직선거리 등이 이에 해당한다.
트리 탐색 알고리즘은 이 수식을 통해서 F(s)의 값이 제일 작은 s를 우선적으로 탐색하는 전략을 통해서 탐색을 수행하며, 알려져있는 대부분의 전략은 저 수식의 어떤 방법으로 참조해서 활용하는가로 분류된다.
2.2.1. Uninformed 전략
Uninformed 전략은 위의 수식에서 h(s)를 배제한 전략으로 해석할 수 있다. 즉, g(s)는 특정 값을 활용하되 h(s)의 값은 0으로 고정하여 여기까지 도착하는데 얼마나 고생스러운지만 판단하고 덜 고생스러운 방향을 찾아나가는 방법이다.
Uninformed 전략은 다시 g(s)를 어떤 식으로 참조하는지에 따라 다음과 같은 분류로 나뉜다
g(s)를 0으로 고정하고 마지막으로 발견한 노드를 우선적으로 탐색한다. 즉, 한쪽 방향으로만 우선적으로 깊게 탐색하는 방식이다. 해당 문서 참조.
g(s)를 트리의 깊이 값으로 고정하여 탐색한다. 깊이 값으로 고정하면 덜 펼쳐진 노드를 우선적으로 탐색하므로, 현재까지 발견된 노드를 모두 펼쳐가며 탐색하게 된다. 해당 문서 참조.
- Uniform-Cost Search
- Depth-limited search
- Iterative Deepening Search
이 방법은 탐색하는 시간은 상당히 오래걸리지만, DFS 방법과 메모리의 소비가 큰 차이가 없다는 큰 장점이 있으며, 어떠한 경우에도 반드시 답을 찾아내어 DFS 방식 특유의 단점을 해결한 우수한 탐색 전략이다. 물론 탐색했던 곳을 제한 깊이가 늘어날때마다 반복적으로 탐색하므로 시간은 비교적 오래걸리지만, 일반적으로 컴퓨터의 연산속도는 사람에 비해서 매우 빠르기 때문에 이는 그다지 신경쓸 필요가 없는 것으로 알려져있다.[7]
2.2.2. Informed 전략
Informed 전략은 문제를 정의하는데에 필요한 정보 외에 추가적인 정보를 활용하여 탐색을 수행한다.
추가되는 정보란 각 상태에 정의된 값이며, 앞의 수식에서 언급된 추정치(Heuristic)을 말한다.
예를 들어 지도상의 도로를 이용하여 서울에서 부산까지 이동하는 최적경로를 찾는 문제에서, 실제로 들어가는 비용은 도로상의 거리에 비례하지만, 거점 위치(대전이나 대구)와 목표 지점(부산)의 직선거리는 추가적인 정보로서 유용하게 활용될 수 있다.
- 허용 추정치(Admissible Heuristic)
일반적으로 추정치는 실제 비용에 가까울수록 좋은 값이 되는데, 만약 실제 비용하고 동일하게 되면, 탐색시 실제로 유용한 값만 탐색하게 되므로 알고리즘의 효율을 높일 수 있기 때문이다.
욕심쟁이 알고리즘은 g(s)를 무시하고 추정치만을 이용하여 탐색하는 방법이다. 일반적으로 최적해를 찾는다는 보장은 없지만, 동적 알고리즘 등에 활용하기에 좋기 때문에 때에 따라서는 성능을 향상시킬 수 있는 특징이 있다. 해당 항목 참조.
현존하는 단일 알고리즘 중에서 가장 성능이 좋은 것으로 평가되는 알고리즘이다. 현재까지의 비용과 추정치를 동시에 사용하여 해를 찾으며, 허용 추정치의 범위 내에서 반드시 최적의 해를 구할 수 있는 것으로 평가된다. 해당 항목 참조.
2.2.3. 메타 전략
메타 전략은 앞서 언급한 알고리즘들과는 달리 여러가지의 알고리즘을 동시에 사용하거나 다른 접근방법을 이용하는 것이다.
시작지점->도착지점과 도착지점->시작지점의 양방향으로 검색을 진행하는 등의 방법이 존재한다.
2.3. 경쟁 문제(Adversarial Search)
경쟁 문제는 문제를 푸는 주체인 프로그램 자신이 선택할 수 없는 영역이 존재하여 일부의 선택과정을 다양한 형태로 가정하고 그 결과를 바탕으로 전체적으로 최적의 해를 구하는 문제 풀이 방법이다.
쉽게 말해서, 체스라던가 장기와 같이 상대가 존재하는 경쟁형으로 구성된 문제에서의 탐색 알고리즘이 바로 이 영역에 속한다.
경쟁 문제는 문제의 해를 찾는 과정에서 중간중간 자신이 선택할 수 없는 영역이 존재하기 마련이다. 이 경우 상대방은 당연히 자신에게 최적의 결과를 가져 오기 위한 방법을 선택할 것이고, 따라서 선택할 수 없는 영역에 대해서는 자신에게 있어서는 최악의 수를 선택한 다는 것을 가정하고 해를 찾아야만 한다.
경쟁 문제를 해결하는 탐색 전략으로서 이론적으로 정립된 것은 거의 없으며, 대체적으로 문제마다 매우 달라져야 하는 것이 일반적인데, 유일하게 상대와 내가 교대로, 혹은 주기적으로 순서가 바뀌는 경우에 대해서 유용한 Pruning 이라는 전략만이 이론적으로 정립되어 있다.
2.3.1. α-β Pruning
α-β Pruning은 앞서 설명한 바와 같이 내가 선택할 수 없는 상황에서는 상대방이 나에게 있어서 최악의 수를 선택할 것이라는 것을 가정하고 문제를 풀어나간다. 이 전략은 어떤 노드를 선택하여 더 좋은 답을 구하겠다는 전략이라기 보다는 무한정 늘어날 수 있는 탐색 범위를 최대한 좁히기 위한 전략이라고 할 수 있는데, pruning이라는 단어에서 암시하듯, 상대방이 어차피 내가 탐색해야 하는 다른 노드보다 불리한 선택을 할 가능성이 있다면 그 방향의 나뭇가지는 그대로 무시하겠다는 것을 주요 목표로 하고 있다.
2.4. 지역 탐색(Local Search)
- CS (Compass Search)
- GPS(Generalized Pattern Search)
- MADS: 비용함수의 미분정보를 필요로 하지 않는 non-gradient 지역 최적화 기법으로서 지역해로의 빠른 수렴성을 갖는 반면 수학적으로 그 수렴성이 증명된 최신의 최적화 알고리즘이다. 기본 원리는 탐색영역 내에서 현재해를 기준으로 이웃해를 발생시켜, 목적함수 결과에 대한 비교 평가를 통해 최적해로 개선해가는 방식이다. GPS의 성능을 개선한 알고리즘으로서, 탐색영역 상에서의 탐색방향이 제한적이지 않으므로 다양한 탐색전략이 구현가능하다.
- SPSA(simultaneous perturbation stochastic approximation)
2.5. 광역 탐색 알고리즘
- 유전 알고리즘. 예를 들면 구글 오프라인 시 할 수 있는 공룡게임에 적용시킨 유전알고리즘 동영상
- PSO (particle swarm optimization)
- 공분산 행렬 이용 진화 전략 (CMA-ES; covariance matrix adaptiation strategy)
[1] 4색 문제는 간단히 설명하면 지도의 국가나 지역을 4가지 색 만으로 구분하여 칠할 수 있는가 하는 문제로, 여기서는 4가지 색을 이용해 칠할 수 있는가 여부에 대한 증명 문제로서가 아니라, 실제로 접경지역간에 동일 색깔이 접하지 않도록 색을 칠하는 문제 자체를 말한다.[2] 다섯 집에 지붕색깔, 다섯 동물, 다섯 담배, 다섯 음료, 다섯 나라 사람 어쩌고 하는 그 문제[3] 4색 문제로 예를 들면, 변수는 지역, 정의역은 색깔, 제약조건은 한 변수와 인접한 변수가 같은 색일 수 없다. 와 같이 정의된다.[4] 목적지를 찾는 문제로 착각하기 쉬운데, 목적지를 탐색하는 것이 아니라, 그 과정에서 어떤 경로를 지나가면 가장 효과적으로 목적지에 도달하는가를 찾는 문제이다.[5] 답은 결국 행동의 연속이고, 행동에는 상태가 포함되기 때문에, 상태의 연속이라고도 생각할 수 있다. 상태의 연속이란 여기, 여기 간다음 여기로 가면 돼! 라는 말의 여기에 해당하므로, 결국은 해를 구성하는 구성요소라 볼 수 있다.[6] 여기까지 오는데 얼마나 힘들었나? 를 표현한다.[7] 이러한 연구가 진행되던 시절은 메모리가 고작해야 640KB가 최대이던 시절이므로 받아들여진 이야기이다. 하지만 지금은 그의 10000배가 넘는 메모리를 활용하고 있으므로 무조건 빠르기만 하면 문제 없다는게 일반적이다.