Uninformed search

내용 보기

 1. Search란 무엇인가?

 

무언가 문제를 풀 때, 보통 필요한 것은 초기 조건, 목표, 제약 조건, 그리고 해당 문제를 푸는 방법이다. 그리고 그 결과로 문제를 푸는 과정, 즉 해답을 얻을 수 있다. 이를 컴퓨터를 이용하여 문제를 푸는 것에 비교해보면 각각 초기 상태(initial state), 목표 상태(goal state), 사용 가능한 연산자(operator), 알고리즘 정도로 볼 수 있으며, 그 해답은 연산자의 순서로 표현될 수 있다. 이 때 연산자란 특정 상태에서 다른 상태로 전이(transition)하는 행동(action)을 표현하는 개념이라 해두자.

 

 이렇게만 표현하면 너무 추상적이니 책에서도 나오는 조금 더 구체적인 예를 들어보자. 두 개의 방 A, B가 있고, 이 두 방은 깨끗한 상태와 더러운 상태로 나뉜다. 그리고 청소 로봇이 이 두 방을 청소하려고 한다면 초기 상태는 청소 로봇의 위치와 두 방의 상태가 될 것이고, 목표 상태는 두 방이 모두 깨끗해지는 것이다. 여기에서 로봇이 택할 수 있는 행동, 즉 연산자는 A로 이동, B로 이동, 청소 세 가지이며, 이 행동을 하면 그에 맞게 전체 상태가 변한다. 두 방을 깨끗하게 청소하기 위해 로봇은 어떤 행동을 할지를 결정해야 하는데, 그 행동 패턴을 결정하기 위해서는 적절한 알고리즘이 필요하다. 그리고 해당 알고리즘이 적합하다면 그 결과로 두 방을 깨끗히 하기 위한 행동 순서, 즉 해답을 구할 수 있을 것이다.

 

 이 때, 답을 구하는 방식은 문제에 따라 여러 가지가 있을 수 있고, 특수한 경우는 매우 효율적으로 풀 수 있다. 그러나 특정한 제약 조건에 의존하지 않고 일반적인 모든 경우에 대해 적용할 수 있는 해법은 사실상 가능한 조합들을 하나 하나 테스트 해보는 것 뿐이다. 이는 문제를 푼다기보다는 해답을 찾아 나가는 것에 가깝기 때문에 이를 탐색(search)라 부르며, 가능한 모든 해답의 집합을 Search space라 한다.

 

 이 때 search는 크게 두 가지로 나뉘는데, 그 중 하나는 Uninformed search다. 이는 문제에 대해 아무런 정보가 주어지지 않은 상태에서 무식하게 해답을 찾아나가는 방법으로, 일반적으로 brute-force algorithm으로 더 잘 알려져 있다. 나머지 하나는 Informed search이다. 이는 문제의 제약 조건에 의해 생기는 search space의 구조를 알고 있는 경우 그에 기반한 휴리스틱 함수를 만들어 검색에 적용, 좀 더 효율적으로 해답을 찾아 나가는 방법이다.

 

 

 2. Uninformed search

 

 Uninformed search는 말 그대로 아무런 정보가 없는 상태에서 해답을 찾는 것으로, 무식하게 해답을 찾아 나간다는 그 성격 상 지극히 비효율적이나 문제에 대한 정보가 없는 상황에서도 적용될 수 있는 방법이라는 점과 더불어 현대 프로세서 연산 능력의 눈부신 발달에 힘 입어 여전히 널리 쓰이고 있다.

 

 선험적인 정보가 필요 없는 Uninformed search라고 해도 기본적으로 틀은 필요하다. 일단 문제를 공식화하자면 아래의 네 요소와 그에 따른 해답으로 정의될 수 있다.

 

• 초기 상태 - 문제에서 주어진 제일 처음의 상태
• 연산자 - 상태 간 전이를 표현하는 함수
• 목표 상태 평가 - 현재 상태가 목표 상태인가를 평가하는 함수
• 경로 비용 - 초기 상태에서 특정 상태에 다다르기까지 소모된 비용의 정의
• 해답 - 초기 상태에서 목표 상태에 다다르기 위한 연산자의 순서

 

 이 외에도 문제에 따라 다양한 유형이 존재한다. 이는 비단 uninformed search에만 적용되는 것이 아니라 "지능"적으로 해결하려는 모든 문제에 적용 가능한 분류인데, 이 역시 한번 간단하게 알아보자. 예를 들자면 문제에 주어진 제약 조건이 모든 상태(state)를 관찰할 수 있는 경우일 수도 있고, 아닐 수도 있다. 혹은 연산자, 혹은 행동에 의한 결과가 예측 가능한 경우가 있으며 아닌 경우도 있을 수 있다. 이를 표로 표현하자면 아래와 같다.

 

 

observable?	fully-observable	partially-observable
deterministic?	deterministic	strategic	non-deterministic
episodic?	episodic	sequential
static?	static	semi-dynamic	dynamic
discrete?	discrete	continuous
single agent?	single-agent	multi-agent

 

 

 observable은 현 상태(state)를 완전하게 관측할 수 있느냐 아니면 부분적으로만 알 수 있느냐의 여부이다. 이는 스타크래프트에서 컴퓨터가 맵핵을 쓰느냐 마느냐라고 생각하면 된다. deterministic은 연산자(operator) 혹은 행동(action)이 가져오는 결과가 완전히 결정론적인가 아닌가, 즉 완벽하게 예측 가능한가 아닌가의 여부이다. 이를테면 스타크래프트의 경우는 모든 데미지가 완전히 고정되어 있으므로 deterministic이라 볼 수 있지만, 워크래프트3는 각 공격의 데미지를 주사위를 굴려서 결정하므로 non-deterministic이다. 이 때 strategic은 행동 자체는 결정론적이지만 마찬가지로 최적의 결과를 내기 위해 움직이는 또 다른 개체의 행동은 예측할 수 없을 때이다.

 

 episodic은 해당 문제가 여러 번 계속 된다 할 때 각각이 독립적인가, 혹은 이전 문제를 푸는 것이 현 문제에도 영향을 주는가의 여부이다. 이를테면 한판 한판이 분명하게 구분되어 있는 카드 게임에서 각 판을 승리하는 것이 목표라면 episodic이라 할 수 있지만, 여기에 판돈이 걸려 최대 이득을 얻는 것이 목표가 된다면 sequential이 된다고 볼 수 있다. static은 문제를 푸는 사이에 상태가 동적으로 변하느냐의 여부로, 실시간 게임인 경우라면 dynamic, 턴제 게임이라면 static이라고 볼 수 있다. discrete는 문제 자체가 이산적으로 명확하게 구분되는 행동과 입력, 변수들로 구분될 수 있는가의 여부이다. 이를테면 길을 찾으려 할 때 타일 간의 경계가 명확하게 구분되어 이동 방향과 거리에 대한 경우의 수가 유한하게 제한된 환경이라면 discrete라 볼 수 있으며, 360도 어느 방향을 어느 속도로라도 이동 가능한 경우라면 continuous한 문제이다. 그 외에 agent는 문제를 해결하려는 개체가 나 하나인가 혹은 여럿이 경쟁하는가의 여부이다.

 

 이야기가 딴 길로 샜는데, 이렇게 문제를 정의하는 까닭은 풀고자 하는 실세계의 문제는 대개 지나치게 복잡하여 일반적으로 적용할만한 해법을 찾기 어렵기 때문이다. 따라서 어느 정도의 추상화를 통해 문제를 공식화하여 조금 더 풀기 쉬운 형태로 바꾸는 것이 그 목표라 할 수 있겠다. 이러한 추상화는 보통 실세계의 상태를 문제에서 정의된 형식의 상태(state)로 적절하게 맵핑시키고, 각 상태 간의 전이를 행동(action)으로 추상화하는 방식으로 이루어진다. 일단 uninformed search를 적용할 문제에 대해서는 문제가 discrete, fully-observable, deterministic하다 가정하자.

 

 그런데 이를 조금 더 유심하게 관찰해보면 자료 구조에서 배운 그래프 문제와 유사성을 쉽게 발견할 수 있다. vertex는 상태(state), edge는 행동(action), edge cost는 행동에 따르는 비용, start vertex는 시작 상태, goal vertex는 목표 상태, start vertex에서 goal vertex까지의 최단 경로는 목표 상태를 이루기 위한 최적의 해답이라고 본다면 이는 명백하게 그래프 탐색 문제로 치환된다. 따라서 BFS, DFS 등 기본적인 그래프 탐색 알고리즘은 uninformed search 알고리즘이라고도 볼 수 있다.

 

 

 3. Uninformed search 알고리즘의 종류 및 특징

 

 Uninformed search 알고리즘의 종류를 알아보기 이전에 우선 이들을 평가할 요소부터 생각해보자. 탐색 알고리즘을 평가하기 위한 중요한 기준은 여러 가지가 있는데 이는 아래와 같다.

 

• completeness : 답이 존재하는 경우 그 답을 항상 찾아낼 수 있는가?
• optimality : 찾아낸 답이 최소의 비용을 가지는가, 다시 말해 최적 해답인가?
• time complexity : 답을 찾아내는 알고리즘의 시간 복잡도
• space complexity : 답을 찾아내는 알고리즘의 공간 복잡도

 

 이 때 시간과 공간 복잡도는 각 상태에서 전이 가능한 상태의 최대 숫자(b), 그래프 상에서 최적 해답의 까지의 깊이(d), 전체 상태 공간(state space)의 최대 깊이(m)에 따라 달라진다.

 

 가장 일반적인 그래프 탐색 알고리즘으로는 Breadth-first search와 Depth-first search가 있는데, 이 둘 역시 Uninformed search에서 활용될 수 있다. BFS의 경우는 현재 체크 중인 상태에서 전이 가능한 모든 상태를 FIFO queue에 넣은 뒤 queue에서 다음 상태를 꺼내어 체크하는 것을 반복하는 형태로 쉽게 구현할 수 있으며, DFS는 queue 대신 LIFO stack을 이용하면 된다.

 

 이 때 위 네 가지 평가 요소를 따져보자. BFS를 사용한다 가정할 때 특정 상태에서 전이될 수 있는 다른 상태의 수가 유한하다면, 다시 말해 b가 유한하다면 이는 언젠간 반드시 답을 찾을 수 있을 것이다. 따라서 complete하지만 BFS를 통해 처음으로 찾아낸 해답이 optimal하다고는 볼 수 없다. 그래프의 깊이로 따지면 가장 얕은 해답을 찾아내지만 이 깊이가 해답의 비용에 정비례한다고 볼 수는 없기 때문이다. (단, 모든 행동의 비용이 동일한 경우는 정비례하므로 optimal이다.) 그 외에 한 단계 더 깊게 들어갈수록 다음에 체크하기 위해 컨테이너에 삽입하는 상태의 수가 지수적으로 증가하므로 time complexity나 space complexity는 O(b^(d+1))이다. 이러한 특성으로 인해 문제의 크기가 커질수록 메모리 사용량이 폭발적으로 증가하는 관계로 BFS는 실용적으로는 큰 의미를 가지지 못한다.

 

 여기에서 해답의 optimality를 보증하기 위해 나온 방법이 Uniform-cost search이다. 이는 가장 적은 비용을 가지는 상태를 우선적으로 체크하는 방법으로, 컨테이너로 queue나 stack 대신 해당 경로의 행동 비용 합을 키로 가지는 우선 순위 큐, 즉 힙을 사용한다. 다만 행동에 들어가는 비용이 0인 경우는 해당 행동을 무한히 반복하는 것이 최적으로 간주되어 무한 루프가 발생할 여지가 있으므로 각각의 행동에는 최소한 ε만큼의 비용이 들어간다고 가정한다. 이 경우 BFS의 특성에 따라 complete하며, 또한 찾아낸 답 역시 optimal함이 보장된다. 이 때 C*를 최적 해답에서의 비용이라 할 때, time complexity와 space complexity는 O(b(C*/ε))이다.

 

 반면 DFS는 깊이가 무한한 경우 - 이를테면 중간에 동일 상태가 반복된다거나 - 무한 반복에 빠질 가능성이 있기 때문에 반드시 답을 찾아낸다는 보장은 없다. 또한 깊이를 우선하여 탐색하는 특성상 optimal하지 않은 답을 해답으로 내놓을 가능성이 있다. 그 외에 그래프의 가장 깊은 부분까지 탐색을 하므로 time complexity는 O(b^m)이며, 이 때 각 상태마다 최대 b개의 상태를 stack에 추가하므로 space complexity는 O(bm)이다.

 

 DFS의 문제는 무한 루프에 빠질 우려가 있다는 것인데, 이를 해결하는 방법으로는 탐색 깊이에 제한을 두는 방법이 있다. 이는 Depth-limited search라 불리며, l 이상의 깊이는 탐색하지 않는 것이다. 이는 현재 체크 중인 그래프의 깊이가 l인 경우 stack에 다음 상태를 추가하지 않는 것으로 쉽게 구현할 수 있다. 이 경우 깊이가 l 이하인 모든 상태를 전부 확인할 것이므로 해답의 깊이가 l 이하라면 complete하다. 하지만 여전히 깊이 우선이므로 optimal 하지는 않다. DFS에서 m이 l로 바뀐 것이므로 time complexity는 O(b^l), space complexity는 O(bl)이다.

 

 DLS는 optimal한 답을 찾지 못한다는 문제를 가지고 있는데, 이는 l 값을 1부터 꾸준히 증가시키면서 DLS를 반복하여 해결할 수 있다. 이를 Iterative deepening search라 한다. DLS를 반복하는 것이므로 당연히 complete하며, 해답이 최초로 발견되는 순간의 l 값이 최소 깊이이므로 행동들의 비용이 동일하다 가정한다면 optimal한 해답을 얻을 수 있다. (만약 동일하지 않다면 DLS 대신 비용 합의 최대 값을 제한하는 Uniform-cost search를 적용하는 방법으로 optimal한 해답을 얻을 수 있을 것이다.) 이 때 time complexity를 계산하면 O(b^d)이며, space complexity는 O(bd)이다.

 

 아래는 각 알고리즘들을 비교한 표이다.

 

 

	BFS	Uniform-cost	DFS	DLS	IDS
completeness	yes	yes	no	yes (l >= d)	yes
time complexity	O(b^(d+1))	O(b^(C*/ε))	O(b^m)	O(b^l)	O(b^d)
space complexity	O(b^(d+1))	O(b^(C*/ε))	O(bm)	O(bl)	O(bd)
optimality	yes (cost is equal)	yes	no	no	yes (cost is equal)

 

 

 이러한 Uninformed search 알고리즘 전반에 있어서 문제가 되는 것은 탐색에서 반복되는 상태가 나타나는 것이다. DFS에서는 무한 루프의 위험이 존재하며, 기타 탐색 알고리즘들에서도 반복되는 상태를 계속해서 체크하는 것은 무의미한 중복으로 인한 오버헤드를 수반한다. 특히나 이렇게 complexity가 지수적인 형태로 나타날 때 밑 값의 크기가 매우 중요해지는데 무의미한 중복을 제거하는 것은 이 밑 값을 작게 만드므로 중복되는 상태가 계속 나타나는지 역시 검사하는 것이 좋다.