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

현재 상태와 목표 상태가 [그림Ⅱ-33]과 같다면 현재 상태에서 선택할 수 있는
현재 상태 목표 상태
2 3 1 2 3 다음 상태는 모두 3가지이다. 그러나 최상 우선 탐색은 모든 상태를 탐색하지
1 8 4 8 4
7 6 5 7 6 5 않고 경험적 정보를 이용해 다음 상태를 선택한다.
경험적 정보를 이용해 각 상태를 평가해 보자. [그림Ⅱ-34]와 같이 상태 ❷에
그림Ⅱ-33
서 목표 상태와 같은 위치에 있는 퍼즐의 수는 6개이다. 즉 경험적 정보 값이 6
현재 상태와 목표 상태
이다. 같은 원리로 ❸의 경험적 정보 값은 5, ❹는 4이다. 그러므로 최상 우선 탐
색 알고리즘은 ❷를 선택한다.

이와 같은 방법으로 최상 우선 탐색을 계속하면 다음과 같은 과정을 거쳐 목

표 상태에 도달하게 된다.
❶
2 3
1 8 4
7 6 5
선택
❷ 목표 상태 ❸ 목표 상태 ❹ 목표 상태
❷ ❸ ❹ 2 3 1 2 3 2 8 3 1 2 3 2 3 1 2 3
2 3 2 8 3 2 3 1 8 4 8 7 6 5 4 1 7 6 5 4 8 7 6 5 4 1 8 4 8 7 6 5 4
7 6 5
7 6 5
1 8 4 1 4 1 8 4
7 6 5 7 6 5 7 6 5
경험적 정보 값 6개 경험적 정보 값 5개 경험적 정보 값 4개

고려하지 않는다 선택
❺ 목표 상태
❺
1 2 3 1 2 3 ❷에서 다음 선택할 상태를 탐색할 때는 다음 상태
2 3 1 2 3 8 4 8 4
1 8 4 8 4 7 6 5 7 6 5 인 ❺와 선택되지 않은 ❸, ❹를 비교하여 경험적
7 6 5 7 6 5 정보 값이 7인 ❺을 선택한다.
경험적 정보 값 7개

선택
❻ ❼ ❻ 목표 상태 ❼ 목표 상태 ❻, ❼은 이전에 선택되지
1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 않은 ❸, ❹와 함께 비교
7 8 4 8 4 7 8 4 8 7 6 5 4 8 7 6 5 4 8 7 6 5 4 된다. 여기서 경험적 정보
6 5
6 5 7 6 5 값이 가장 큰 ❼이 선택
경험적 정보 값 6개 경험적 정보 값 8개 된다.
그림Ⅱ-34 l 최상 우선 탐색 과정

가능한 모든 경우를 탐색하는 맹목적 탐색에 비해 탐색 횟수가 상당히 줄어

든 것을 확인할 수 있다. 즉, 정보를 이용한 탐색은 복잡한 문제를 해결하는 데
매우 효율적일 수 있다.

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