인공지능 2강 (탐색에 의한 문제풀이)

학습개요

1. 인공지능의 초기 연구는 인간이 지능적으로 문제를 해결하는 과정을 어떻게 컴퓨터를 이용할 수 있을까에 집중된다. 이를 위해서는 우선 해결해야 할 문제를 컴퓨터를 통해 표현해야 한다. 이것은 외부 세계를 컴퓨터에 적절한 형식으로 모델링하는 것이며, 여기에는 문제를 풀이하는 과정에서 변화되는 상태를 표현하고, 이러한 상태를 변화시키는 적절한 수단을 정의하는 것을 포함한다. 알고리즘으로 해결하기 어려운 문제를 풀이하는 것은 이렇게 표현된 문제의 상태공간에서 어떻게 목표에 이르는 경로를 탐색하는 것으로 볼 수 있다. 목표상태를 탐색하는 것은 다양한 기준에 따라 순서를 정하여 탐색할 수 있다. 이번 시간에는 문제 풀이를 위한 문제표현 방법 및 문제풀이의 기본적 접근방법과 맹목적 탐색으로 분류되는 탐색 기법들에 대하여 학습하고자 한다.

 학습목표

1. 문제풀이 시스템에서 문제의 표현방법에 대해 설명할 수 있다.
2. 주어진 문제에 대한 상태묘사, 연산자, 초기상태, 목표상태 등을 정의할 수 있다.
3. 문제풀이와 탐색의 관계를 설명할 수 있다.
4. 맹목적 탐색이 무엇인지 설명할 수 있다.
5. 깊이우선 탐색과 너비우선 탐색 알고리즘을 설명할 수 있다.
6. 균일비용 탐색 알고리즘을 이용하여 최소비용 경로를 탐색하는 과정을 설명할 수 있다.

 주요용어

1. 상태묘사 : 풀이하고자 하는 문제의 상태를 컴퓨터로 처리하기 위한 적절한 자료구조로 표현한 것
2. 연산자 : 어떠한 상태로부터 변화할 수 있는 다른 상태로 변환하는 도구로서, 변환 테이블이나 변환 함수로 구현함
3. 상태공간 : 정의된 연산자의 집합을 이용하여 초기상태로부터 얻을 수 있는 모든 상태의 집합
4. 맹목적 탐색 : 목표노드에 대한 정보를 사용하지 않고 정해진 순서에 따라 탐색을 하는 방법
5. 경험적 탐색 : 문제영역에서 사용할 수 있는 목표노드의 위치와 관련된 경험적 정보를 사용하는 탐색 방법
6. 깊이우선 탐색 : 탐색 진행방향(깊이 방향)으로 계속 전진하여 목표를 탐색하는 방법
7. 너비우선 탐색 : 트리의 레벨 순서에 따라 노드를 확장하여 탐색을 진행하는 방법
8. 균일비용 탐색 : 출발노드로부터의 경로비용이 가장 작은 노드를 먼저 선택하여 검사하고 확장하는 탐색 방법

 

정리하기

1. 상태묘사란 풀이하고자 하는 문제의 상태를 컴퓨터로 처리하기 위한 적절한 자료구조로 표현한 것이다.
2. 연산자는 문제의 어느 한 상태로부터 변화할 수 있는 다른 상태로 변환하는 역할을 한다.
3. 상태공간은 정의된 연산자 집합을 이용하여 초기상태로부터 얻을 수 있는 모든 상태의 집합으로, 그래프 형태로 표현할 수 있다.
4. 상태묘사 및 초기상태의 정의, 목표상태의 정의, 연산자의 정의를 함으로써 상태공간에서 문제를 표현한다.
5. 상태공간의 탐색에 의한 문제풀이 방식은 시행착오를 통해 초기상태로부터 목표상태에 도달하는 경로를 탐색한다.
6. 그래프 탐색에서 주어진 노드(상태)에 적용할 수 있는 모든 연산자를 가하여 모든 후계노드(후계상태)를 생성하는 것을 그 노드를 확장한다고 한다.
7. 맹목적 탐색은 다음 확장할 노드를 선택할 때 목표노드의 위치에 대한 정보를 사용하지 않는다.
8. 깊이우선 탐색에서는 가장 최근에 생성된 노드를 가장 먼저 확장함으로써 탐색 진행방향(깊이 방향)으로 계속 전진하여 목표를 탐색한다.
9. 너비우선 탐색에서는 생성된 순서에 따라 노드를 확장함으로써, 트리의 레벨 순서에 따라 노드를 확장한다. 만일 해가 존재한다면 출발노드에서 목표노드까지의 최단길이 경로를 찾는 것을 보장한다.
10. 균일비용 탐색에서는 출발노드로부터의 경로비용이 가장 작은 노드를 먼저 확장한다. 출발노드에서 출발하여 목표노드에 도달하는 최소비용경로를 탐색할 수 있다.