인공지능 - [3] 탐색에 의한 문제풀이(1)

인공지능 - 탐색에 의한 문제풀이(1)

• 눈금이 없는 4리터들이 및 3리터들이 물병과 무제한 물을 제공할 수 있는 펌프가 있을 때, 4리터들이 물병에 정확히 2리터의 물을 채우는 문제가 주어졌다. 이 문제를 해결하기 위해 4리터들이 및 3리터들이 물병에 들어 있는 물의 양을 나타내는 2개의 수 x와 y를 저장하는 벡터 (x, y)로 나타내는데 이것을㉠상태묘사(이)라고 한다. 두 물병이 모두 비어있는 처음의 상태는 (0, 0)으로 이를㉡초기상태(이)라고 하고, 문제가 풀이된 상태는 (2, 0)으로 이를㉢목표상태(이)라고 한다. 이제 각각의 물병에 물을 채우거나 비우거나 옮기는 등의 행동을 할 수 있는데, 이에 따라 물병 속의 물의 양이 변화한다. 즉, (x, y)가 새로운 값 (x’, y’)로 바뀐다. 이와 같이 어떠한 상태를 다른 상태로 변환하는 역할을 하는 것을㉣연산자(이)라고 한다.　문제를 풀이하는 것은㉡초기상태(으)로부터 시작하여 적용할 수 있는㉣연산자을(를) 선택해 적용함으로써 상태를 변화시켜㉢목표상태에 이르는 방법을 찾는 것이다.

1. 그래프 탐색에서 주어진 노드(상태)에 적용할 수 있는 모든 연산자를 가하여 모든 후계노드(후계상태)를 생성하는 것을 그 노드를 확장한다고 한다.
2. 맹목적 탐색은 다음 확장할 노드를 선택할 때 목표노드의 위치에 대한 정보를 사용하지 않는다.
3. 경험적 탐색은 문제영역에서 사용할 수 있는 목표노드의 위치와 관련된 경험적 정보를 사용하는 탐색 방법
4. 깊이우선 탐색에서는 가장 최근에 생성된 노드를 가장 먼저 확장함으로써 탐색 진행방향(깊이 방향)으로 계속 전진하여 목표를 탐색한다.
5. 너비우선 탐색에서는 생성된 순서에 따라 노드를 확장함으로써, 트리의 레벨 순서에 따라 노드를 확장한다. 만일 해가 존재한다면 출발노드에서 목표노드까지의 최단길이 경로를 찾는 것을 보장한다.
6. 균일비용 탐색에서는 출발노드로부터의 경로비용이 가장 작은 노드를 먼저 확장한다. 탐색 결과는 경로비용이 가장 적은 노드를 선택한다.