탐색과 제어전략

인공지능 개론 : Dan W. Patterson 저서, 김영렬.김우성.김정규.박용법.정목동 옮김, 지성출판사, 1995  (원서 : Introduction to Artificial Intelligence and Expert Systems, 1990)

1. 소개

2. 서론 개념 (preliminary concepts)

3. 탐색 문제들의 예

4. 무정보 또는 블라인드 탐색 (Uninformed or Blind Search)

나비우선 탐색 (Breadth-First Search)

깊이우선 탐색 (Depth-first search)

깊이우선 반복 심화 탐색 (Depth-first Iterative Deepening search)

양방향 탐색 (Bidirectional Search)

5. 정보가 있는 탐색 (Informed Search)

경험적 정보 (Heuristic Information)

언덕 오르기 탐색 (Hill Climbing Methods)

최적우선 탐색 (Best-first Search)

분기와 한정탐색 (Branch-and-Ground Search)

최적 탐색과 A^* (Optimal Search and A^*)

반복 심화 A^* (Iterative Deepening A^*)

6. AND-OR 그래프 탐색 (Searching AND-OR Graphs)

7. 요약

나비 우선 탐색 (Breadth First Search)

BFS 방법은 다음 레벨의 노드를 조사하기 앞서 트리의 같은 레벨이 있는 레벨의 노드를 먼저 조사하는 방법이다.  이것은 자식의 자식들이 고려되기 전에 현 노드의 바로 밑에 있는 자식 노드가 조사된다는 것을 의미한다.

 BFS 를 다음그림에 나타낸다. 그것은 항상 만일 최소길이의 길이가 존재하면 그것을 찾는 장점이 있다. 그러나 만일 트리가 꽉 차있다면 해답이 발견되기 전까지 많은 노드를 조사해야 할 필요가 있다. BFS 알고리즘은 매우 단순하다. 그것은 조사되지 않은 노드들을 제외한 모든 생성된 노드를 저장하기 위해 노드구조를 사용한다. 노드의 제거나 조사를 하기위해 노드들이 위치해 있는 순서는 탐색의 형태를 결정한다. BFS 알고리즘은 다음과 같다.

    Breadth First Search

1. 시작노드를 큐(Queue)에 배정한다.
2. 큐(Queue)가 비어있다면 실패하게 되어 멈춘다.
3. 만일 큐(Queue)의 첫번째 요소가 목표 노드 'g'이면 성공하게 되어 멈춘다. 그렇지 않으면
4. 큐(Queue)로 부터 첫번째 요소를 제거하고 확장시키며 모든 자식들을 어떤 순서이든지 큐(Queue)의 마지막에 배정한다.
5. 단계2로 돌아간다.

  BFS의 시간 복잡도는 이다. 이것은 목표 깊이 까지의 모든 노드가 생성됨을 주목하면 알 수 있다. 그러므로 생성되는 노드 수는 , 즉 임을 알 수 있다. 공간 복잡도는 역시 이다. 왜냐하면 주어진 깊이의 모든 노드들은 다음 깊이의 모든 노드들을 생성하기 위해 저장되야만 한다. 즉 깊이 인 노드들이 깊이 의 노드를 생성하기 위해 저장되야만 한다. 결국 공간 복잡도는 가 된다. 이러한 지수 함수적인 시간 공간 특성이 BFS 을 잘 적용하지 못하게 하는 이유중의 하나이다.

깊이 우선 탐색 (Depth-first search)

DFS은 가능한 빨리 탐색 트리속으로 들어가서 수행된다. 이것은 최근에 확장된 노드의 자노드(chidren node)를 생성함으로써 가능하다. 다음에 자노드(children node)의 자노드를 생성하여 목표가 발견되기까지 혹은 임계 깊이(cutoff depth) d에 이를 때까지 반복된다. 잎노드(leaf node)에 이를 때 까지 또는 임계점(cutoff point)에서 목표가 발견되지 않으면 프로그램은 최근에 확장된 노드로 역행(back tracking)하여 그 노드의 다른 자노드 를 생성한다. 이 과정은 목표가 발견되기까지 혹은 실패하게 될 때까지 계속된다.
 DFS알고리즘은 Queue 에 위치하는 노드의 순서를 제외하고는 breadth-first search 과 동일하다. DFS은 새로 생성된 자식을 Queue 의 앞에 위치시켜 그것들이 먼저 선택되도록 한다.

탐색과정은 다음과 같다.

1. DFS
2. 초기 노드 를 Queue 에 배정한다.
3. 만일 Queue 가 비어있다면, 실패를 알리고 멈춘다.
4. 만약 Queue 의 첫번째 요소가 목표노드 '' 이면 성공을 알리고 멈춘다. 그렇지 않으면
5. 첫번째 요소를 Queue 로부터 제거하고, 그 요소의 자식들이 있다면 그 노드들을 Queue 의 앞(front)에 추가한다. (어떤 순서든지)
6. 단계 2로 돌아간다.

DFS은 탐색 트리가 매우 많은 목표를 갖고 있는 경우에 breadth-first search 보다 더 선호된다. 그렇지 않으면 깊이 우선 탐색은 해답을 발견하지 못할 수도 있다. 깊이 임계값(depth cutoff) 역시 몇가지 문제를 야기시킨다. 만약 임계값이 너무 얕으면 목표를 찾지 못할 수 있고, 임계값이 너무 깊으면 추가적인 계산이 필요하게 된다.
DFS 의 시간 복잡도(time complexity)는 breadth-first search 의 복잡도 즉 와 같다. 초기 시작 노드로부터 현재 노드로의 path 만 저장되기 때문에 공간은 덜 차지하게 된다. 그러므로 만일 깊이 임계값(depth cutoff)이 이면, 공간 복잡도는 이다.