Page 82 - 고등학교 인공지능 기초

3 탐색 트리를 이용한 탐색 방법

1. 맹목적 탐색

맹목적 탐색(blind search)은 현재 상태부터 목표 상태까지 정해진 순서에 따라
맹목적 탐색 알고리즘
1. 현재 상태에서 시작하여 모든 상태를 순차적으로 찾는 방법이다. 여러가지 맹목적 탐색 기법 중 너비 우선
모든 이동가능한 다음 탐색 과정을 살펴보자.
상태들을 탐색한다.
2. 모든 다음 상태들에 대
한 탐색을 마치면 다음
레벨의 모든 이동가능
한 상태들을 탐색한다.
❶
2 3
1 8 4
7 6 5
1. 현재 상태에서 시작한다.

2. 현재 상태에서 이동 가능한 다음 상태를 탐색해 ❷로 이동한다.
❷ ❸ ❹
3. ❷는 목표 상태가 아니므로 ❶에서 이동 가능한 다음 상태인 2 3 2 8 3 2 3
❸으로 이동한다.
1 8 4 1 4 1 8 4
4. ❸도 목표 상태가 아니므로 ❶에서 이동 가능한 다음 상태인 7 6 5 7 6 5 7 6 5
❹로 이동한다.

5. ❹도 목표 상태가 아니다. ❶에서 이동 가능한 다음
❺ ❻ ❼ ❽
상태가 없으므로 ❷의 다음 상태인 ❺로 이동한다.
1 2 3 2 8 3 2 8 3 2 8 3
6. ❺가 목표 상태가 아니다. ❷에서 이동 가능한 8 4 1 4 1 6 4 1 4
다음 상태가 없으므로 ❸의 다음 상태인 ❻으로 7 6 5 7 6 5 7 5 7 6 5
이동한다.
7. 이와 같은 과정을 반복하며 목표 상태를 찾아낸다. 그림Ⅱ-31 l 맹목적 탐색 과정

맹목적 탐색은 정해진 순서에 따라 모든 상태를 탐색하므로 단순하고 간단

한 문제는 정답을 쉽게 찾을 수 있다는 장점이 있다. 하지만 목표 상태에 도달
할 때까지 모든 경우를 살펴보기 때문에 복잡한 도로에서 목적지를 찾는 내비
게이션처럼 처리할 정보가 많을 때는 속도가 느리다는 단점이 있다.

80 Ⅱ 인공지능의 원리와 활용