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

2 탐색 트리

탐색 과정을 표현하기 위한 여러 방법 중 탐색 경로를 나무 모양의 그래프로

표현한 구조를 탐색 트리(search tree)라고 한다. 트리의 맨 위에는 퍼즐의 시작
점인 ‘현재 상태’를 둔다. 그리고 ‘현재 상태’에서 이동할 수 있는 각각의 경우
를 아래에 나타낸다.

예를 들면, [그림Ⅱ-30]에서 현재 상태인 ❶에서 숫자 조각이 빈칸으로 이동
하는 방법에는 2, 8, 3이 움직이는 3가지 경우가 있다.

❶
2 3
1 8 4
7 6 5

2 3 2 3 2 3
1 8 4 1 8 4 1 8 4
7 6 5 7 6 5 7 6 5

❷ ❸ ❹
2 3 2 8 3 2 3
1 8 4 1 4 1 8 4
7 6 5 7 6 5 7 6 5

숫자 조각 2가 오른쪽으로 이동하는 경우 숫자 조각 8이 위쪽으로 이동하는 경우 숫자 조각 3이 왼쪽으로 이동하는 경우
그림Ⅱ-30 l 숫자 조각이 빈칸으로 이동하는 방법 3가지

잠깐 활동

다음은 8조각 숫자 퍼즐의 탐색 트리 중 일부를 나타
낸 것이다. 현재 상태에서 선택할 수 있는 경우를 모 2 8 3
1 6 4 현재 상태
두 고려하여 탐색 트리를 완성해 보자. 7 5

2 8 3 2 8 3
1 6 4 1 6 4
7 5 7 5

2 3 2 8 3
1 8 4 1 4
7 6 5 7 6 5

79
4. 문제 해결과 탐색