3장. 탐색

탐색 탐색(Search)은 인공지능 시스템이 문제해결을 위해서 흔히 사용하는 기법이다. 만약 우리가 문제 해결을 위해서 취해야 할 행동들이 무엇인지 알고 있지만 어떤 순서로 행동을 취해야 문제가 해결되는지 알지 못한다면 가능한 모든 순서의 조합을 다 시도해 보아야 할 것이다.

간단한 마을지도

탐색 따라서 탐색 방법에는 모든 길을 다 찾아 보는 방법인 무 정보 탐색도 있고 가능성이 높은 곳만을 선별하여 찾아 보는 방법인 휴리스틱 탐색도 있다. 초기상태(Initial State) 목표상태(Goal State) 상태공간(State Space):어떤 문제 공간에서 만들어 질 수 있는 모든 상태들의 집합 = 탐색공간(Search Space)

3.1 무정보 탐색기법 여기서는 무정보 탐색 - 맹목적 탐색(Blind Search) 또는 Brute Force Search - 으로 깊이우선 탐색, 너비우선 탐색 등을 알아본다. 무정보 탐색은 탐색공간에 대한 아무런 정보도 없이 순서만 정해놓고 탐색을 수행한다.

3.1.1 깊이우선 탐색 도서관 병원 초등학교 공원 중학교 상가 대학교 교회

깊이우선탐색 알고리즘 빈 스택에 초기상태 노드를 넣는다. (e.g., STACK ={도서관}) 답 = 찾지못함. 스택이 비어 있지 않고 답 =찾지못함 이면 다음을 반복한다. 스택에서 하나의 노드 N 을 빼낸다. 만약 N 이 목적상태노드 이면 답 = 찾음 으로한다. N의 자노드가 있으면 이를 스택에 넣는다. (e.g., STACK={병원 초등학교})

스택의 내용 1) STACK = {도서관}, 답 = 찾지못함. 2) STACK = {병원 초등학교}, 답 = 찾지못함 스택(STACK)에는 노드의 이름만이 기록된다. 따라서 ‘도서관에서 출발하여 대학교까지 갈 수 있다(i.e.,가는 길이 있다)’ 는 것은 알 수 있지만 어느 길을 어떻게 따라가야 하는지에 대한 정보는 최종스택에 남지 않는다.

지금까지 지나온 길에 대한 정보를 알려면 빈 스택에 초기상태 노드를 넣는다. (e.g., STACK ={도서관}) 지금까지 지나온 길에 대한 정보를 알려면 빈 스택에 초기상태 노드를 넣는다. (e.g., STACK ={도서관}) LIST = { } ; 초기의 리스트는 비어 있음 답 = 찾지못함. 스택이 비어 있지 않고 답 =찾지못함 이면 다음을 반복한다. 스택에서 하나의 노드 N 을 빼낸다. N과 N의 부모노드를 쌍(Pair)으로 만들어 LIST에 넣는다. (e.g., 리스트={(도서관, NIL)} 만약 N 이 목적상태노드 이면 답 = 찾음 으로한다. N의 자노드가 있으면 이를 스택에 넣는다. (e.g., STACK={병원 초등학교})

스택과 리스트의 내용 1) STACK = {도서관}, 답 = 찾지못함 LIST={ } . LIST ={(도서관, NIL)} . 3) STACK = {공원 중학교 초등학교}, 답 = 찾지못함 LIST ={(병원, 도서관)(도서관, NIL)} 4) STACK = {중학교 초등학교}, 답 = 찾지못함 LIST ={(공원, 병원)(병원, 도서관)(도서관, NIL)} 5) STACK = {대학교 교회 초등학교}, 답 = 찾지못함 LIST ={(중학교, 병원)(공원, 병원)(병원, 도서관)(도서관, NIL)} 6) STACK = {교회 초등학교}, 답 = 찾음 LIST ={(대학교, 중학교)(중학교, 병원)(공원, 병원)(병원, 도서관)(도서관, NIL)}

그래프 탐색공간 도서관 병원 초등학교 공원 중학교 상가 대학교 교회

탐색공간이 그래프인 경우에도 효율적인 탐색이 가능한 깊이우선 탐색 알고리즘 빈 스택에 초기상태 노드를 넣는다. (e.g., STACK ={도서관}) LIST = { } ; 초기의 리스트는 비어 있음 답 = 찾지못함. 스택이 비어 있지 않고 답 =찾지못함 이면 다음을 반복한다. 스택에서 하나의 노드 N 을 빼낸다. N과 N의 부모노드를 쌍(Pair)으로 만들어 LIST에 넣는다. (e.g., 리스트={(도서관, NIL)} 만약 N 이 목적상태노드 이면 답 = 찾음 으로한다. N의 자노드가 있으면 자노드중 LIST에 없는 자노드만 스택에 넣는다. (e.g., STACK={병원 초등학교})

깊이우선 탐색의 특징 깊이우선 탐색의 특징 중 하나는 시작노드에서 목적노드까지의 가장 짧은 거리를 처음에 찾는 것을 보장 할 수 없다는 것이다. 하나의 길이 찾아진 후에 더 짧은 길이 발견될 수 있는 것이다. (그래프에서 두 노드를 연결하는 길은 하나 이상이 있을 수 있다.) 하지만 너비우선 탐색은 깊이우선 탐색과는 달리 처음 찾은 길이 가장 짧은 길이 된다.

3.1.2 너비우선 탐색 달리 탐색트리의 상위 노드를 하위 노드보다 먼저 탐색한다. 도서관 병원 초등학교 공원 중학교 상가 병원 초등학교 공원 중학교 상가 대학교 교회 [그림 3.4] 너비우선 탐색순서

너비우선 탐색 알고리즘 빈 큐(Queue)에 초기상태 노드를 넣는다. (e.g., QUEUE ={도서관}) LIST = { } ; 초기의 리스트는 비어 있음 답 = 찾지못함. 큐가 비어 있지 않고 답 =찾지못함 이면 다음을 반복한다. 큐에서 하나의 노드 N 을 빼낸다. N과 N의 부모노드를 쌍(Pair)으로 만들어 LIST에 넣는다. (e.g., 리스트={(도서관, NIL)} 만약 N 이 목적상태노드 이면 답 = 찾음 으로한다. N의 자노드가 있으면 자노드중 LIST에 없는 자노드만 큐에 넣는다. (e.g., QUEUE ={병원 초등학교})

리스트(LIST)의 내용 1) QUEUE = {도서관}, 답 = 찾지못함 LIST={ } . LIST ={(도서관, NIL)} . 3) QUEUE = {초등학교 공원 중학교}, 답 = 찾지못함 LIST ={(병원, 도서관)(도서관, NIL)} 4) QUEUE = {공원 중학교 상가}, 답 = 찾지못함 LIST ={(초등학교, 도서관)(병원, 도서관)(도서관, NIL)} 5) QUEUE = {중학교 상가}, 답 = 찾지못함 LIST ={(공원, 병원) (초등학교, 도서관)(병원, 도서관)(도서관, NIL)} 6) QUEUE = {상가 대학교 교회}, 답 = 찾지못함 LIST ={(중학교, 병원)(공원, 병원) (초등학교, 도서관)(병원, 도서관)(도서관, NIL)} 7) QUEUE = {대학교 교회}, 답 = 찾지못함 LIST ={(상가, 초등학교)(중학교, 병원)(공원, 병원) (초등학교, 도서관)(병원, 도서관) (도서관, NIL)} 8) QUEUE = {교회}, 답 = 찾음 LIST ={(대학교, 중학교)(상가, 초등학교)(중학교, 병원)(공원, 병원)(초등학교, 도서관) (병원, 도서관)(도서관, NIL)}

3.2 휴리스틱 탐색기법 탐색에서 휴리스틱은 탐색공간에 관한 정보를 탐색에 활용하여 탐색공간을 줄이거나, 정확한(최선의) 답은 아닐지라도 답으로 사용 가능한 근사치를 빨리 찾을 수 있도록 하는 유용한 정보이다.

휴리스틱 탐색은 기본적으로 다음과 같은 두 가지 경우에 더욱 유용하다 모호성 때문에 문제의 해가 정확히 존재하지 않을 때 주어진 시간 내에 모든 탐색공간을 다 방문 할 수 없을 때.

방문상인 문제 방문상인 문제(Traveling Salesman Problem) 휴리스틱 도시 수 가 N 개 이면 (N – 1)! / 2 가지의 서로 다른 경로가 가능하다. 도시의 수가 20개만 되더라도 가능한 조합의 수는 60,822,550,204,416,000 도시의 수가 많아지면 모든 경로를 정해진 시간에 다 계산해 본다는 것은 불가능하다. 휴리스틱 현재의 도시에서 가장 가까운 도시로 이동한다. 바다쪽으로 돌아 가면서 이동한다.

3.2.1 언덕등반 탐색 [그림 3.6] 언덕등반 탐색

언덕등반 알고리즘 현재상태 = 시작노드 현재상태 = 목적노드 이거나 현재상태에 변화가 없을 때까지 다음을 반복 한다. 현재상태에 있는 노드의 자녀노드들을 구하고 각각에 평가함수 값을 부여한다. 자녀노드의 평가함수 값이 현재상태에 있는 노드의 평가함수 값보다 좋은 것이 있으면 그 중 가장 좋은 평가함수 값을 갖는 자녀노드를 현재상태의 노드로 만든다. %현재상태에는 항상 하나의 노드만 있음

깊이우선 탐색과 언덕등반 탐색이 다른점 깊이우선 탐색에서는 아무런 정보도 사용하지 않고 정해진 순서대로 탐색을 수행한다. 깊이우선 탐색과 언덕등반 탐색이 다른점 깊이우선 탐색에서는 아무런 정보도 사용하지 않고 정해진 순서대로 탐색을 수행한다. 하지만 언덕등반 탐색에서는 다음 노드를 선택할 때 자녀노드 중 목적노드로 인도할 가능성이 가장 높은 노드를 선택한다. 이때 가능성은 평가함수(Evaluation Function)를 사용하여 계산한다.

8-퍼즐을 언덕등반 탐색에 의해 푸는 과정 [그림 3.7] 참조

8-퍼즐에서 지역최고에 빠진 경우 [그림 3.8]참조

3.2.2 최고우선 탐색 최고우선 탐색(Best-First Search)은 우선순위큐(Priority Queue)를 사용하여 언덕등반 탐색에서 생길 수 있는 지역최고에 빠지지 않고 탐색을 수행 할 수 있게 한다. 우선순위큐는 큐내의 요소 중 우선순위가 가장 높은 것이 큐의 항상 가장 앞에 놓이는 큐이다.

최고우선 탐색 알고리즘 대상노드 = 시작노드 대상노드가 비어있지 않으면 다음을 반복 한다. 대상노드에서 평가함수 값이 가장 좋은 노드를 빼낸다. % 대상노드는 우선순위큐를 사용하여 구현하면 효과적임 빼낸 노드가 목적노드이면 탐색을 성공적으로 끝내고, 목적노드가 아니면 빼낸 노드의 자녀노드들을 구한다. 구한 각각의 자녀노드에 평가함수 값을 부여하고 이들을 대상노드에 추가한다. % 대상노드에는 여러 개의 노드가 있을 수 있음

가상의 상태공간 A/5 B/6 C/4 D/3 E/3 F/2 G/7 H/8 I

OPEN = {A/5}; CLOSED = { } - 노드 A 가 시작노드 OPEN = {B/6, C/4, D/3}; CLOSED = {A/5} - 평가함수 값이 가장 높은 노드가 OPEN의 가장 왼쪽에 오고 다음 방문 노드가 된다. OPEN = {C/4, D/3, E/3, F/2}; CLOSED = {B/6, A/5} - 노드 C의 평가함수 값이 가장 크므로 노드 B의 자녀노드 가 아니라 노드 C가 다음에 방문할 노드이다. OPEN = {H8, G/7, D/3, E/3, F/2}; CLOSED = {C/4, B/6, A/5} OPEN = {G/7, D/3, E/3, F/2}; CLOSED = {H8, C/4, B/6, A/5} - 목적노드 H/8이 찾아짐

평가함수 휴리스틱 탐색에서는 평가함수를 어떻게 만드느냐에 따라 탐색의 효율이 크게 달라진다. 위의 8-퍼즐 문제에서 목적상태와 일치하는 타일의 개수를 평가함수 값으로 사용하였는데 이는 각 타일이 움직여야 하는 거리는 고려하지 않은 것이다. 실제로 목적상태에 도달하기 위해서는 제 위치에 있지 않는 노드들이 제자리를 찾아가야 하는데 그 거리 정보까지를 이용하면 더 효율적인 탐색이 가능하다.

3.2.3 A* 알고리즘 지금 까지는 현재의 노드에서 목적노드까지 어떻게 하면 빨리 찾아갈 수 있는가에 관심을 갖고 있었다. 어떤 문제는 목적노드만을 찾는 것이 중요한 것이 아니고 시작노드에서 목적노드까지 최단경로를 찾아야 하는 경우도 있다.

최단거리 탐색 경로를 찾기 위해 시작노드에서 현재노드(N)까지 온 실재의 최단거리 (g(n)으로 표시). 평가함수가 다음 두 가지 사항을 고려 하여야 한다. 시작노드에서 현재노드(N)까지 온 실재의 최단거리 (g(n)으로 표시). 현재노드(N)에서 목적노드까지의 실재의 최단거리 (h(n)으로 표시). 평가함수 f -> f(n) = g(n) + h(n)

A 알고리즘 여기에서 g(n)은 지금까지의 탐색 결과에 의하여 구할 수 있다. 하지만 h(n)은 아직 정확히 알지 못하는 거리이다. 따라서 h(n)은 추정치를 사용하여야 한다. h(n)의 추정치를 h*(n)으로 표시하면 f(n)은 다음과 같은 f*(n)으로 바뀐다. f*(n) = g(n) + h*(n) 위의 f*(n)을 평가함수로 사용하고 최고우선 탐색을 수행하는 알고리즘을 A 알고리즘이라고 한다. 그리고 f*(n)에 사용되는 h*(n)이 실재 최단거리인 h(n)보다 크지 않을 때 A 알고리즘은 A* 알고리즘이 된다.

하나의 탐색 그래프 A/7 2 2 B/5 C/4 4 3 D/4 G/6 3 6 E/3 4 F/0

때와 A* 알고리즘을 사용할 때 A* 알고리즘이 최고우선 탐색 알고리즘보다 더 많은 정보(g(n))를 사용한다. 최고우선 탐색 알고리즘에서는 h*(n)만을 사용한다.

3.2.4 A* 알고리즘의 허용성과 단조 증가성 시작노드에서 목적노드사이에 최단경로가 존재할 때 이를 항상 찾을 수 있는 탐색 알고리즘은 허용성(Admisibility)이 있다 고 한다. 그리고 A* 알고리즘에서 사용하는 평가함수 f*(n) = g(n) + h*(n) 에서 h*(n)  h(n) 이므로 A* 알고리즘은 허용성이 있다. 만약 h*(n) = 0 이면 A* 알고리즘은 너비우선 알고리즘과 같아진다.

탐색공간 크기 비교 A* 알고리즘 탐색 공간 너비우선 탐색 공간

A* 알고리즘 탐색에서 0  h1*(n)  h2*(n)  h(n) 이면 탐색공간 h1*(n)을 사용하는 알고리즘의

단조 증가성(Monotonicity) 어떤 휴리스틱 알고리즘을 사용하여 탐색을 수행하는 중에, 한번 찾은 노드를 더 짧은 경로로 다시 발견할 수 없다면 이 알고리즘은 단조 증가성(Monotonicity)을 가지고 있다고 한다. 즉 다음 두 가지 조건을 만족하는 휴리스틱 알고리즘은 단조 증가성을 갖는다. 목적노드의 평가함수 값이 0 이다. h(ni) –h(nj) 이 노드 i 에서 노드 j 로 가는 실제 값(거리)보다 적다. (이때 노드 j 는 노드 i 의 자녀노드 이다.) 어떤 알고리즘이 단조 증가성을 갖으면 그 알고리즘은 A* 알고리즘 이며 허용성도 갖는다.

3.3 게임과 탐색 게임은 8-퍼즐게임처럼 한 사람이 하는 게임도 있지만, 상대가 있는 게임도 많다. 상대가 있는 게임은 상대의 의도 까지를 고려해야 하기 때문에 일반적으로 혼자 하는 게임보다 더욱 복잡하다. 대부분의 게임은 제한된 시간 내에 모든 상태를 전부 탐색 할 수 없으므로 탐색공간을 줄여야 하는데 휴리스틱을 잘 활용하면 탐색공간을 크게 줄일 수 있다.

3.3.1 Minimax기법 Max level 2 -7 Min level 10 2 -7 100 2 -7 Min level 10 2 -7 100 10 6 -2 2 -8 -7 20 100

3.3.2 알파베타 절단 기법 알파베타 절단 기법(Alpha-Beta Pruning)은 상태공간중에 탐색에 고려하지 않아도 최종결과에는 영향을 미치지 않는 노드들을 절단하여 탐색공간을 줄이는 탐색기법이다. 처럼 MAX노드(i.e., 노드C)가 절단된 경우를 알파절단(Alpha Cutoff)이라고 하고 MIN노드가 절단된 경우를 베타절단(Beta Cutoff)이라고 한다.

[그림 3.13] 알파베타 탐색의 예 Max level A 2 2 D B -7 Min level 10 2 E -7 C ? 10 6 -2 2 -8 -7 20 100