인공지능 - 문제 표현

인공지능의 문제

---

  인공지능 문제의 특징은 조합에 따른 최적화 문제로서 일반적으로 절차적인 해를 구하는 것이 곤란하고 탐색을 통한 접근 시 고려해야 할 문제가 폭팔적으로 증가한다는 특징을 가진다

  한 세일즈맨이 사업상 여행을 해야 한다고 가정해 보자. 이 세일즈맨은 A지점을 출발하여 B, C, D, E 도시를 순서에 관계없이 한 번만 통과하여 A로 돌아오기를 원한다. 각 도시 사이의 숫자는 여행 비용을 의미하며 이를 최소화하는 경로를 구하는 것이 목표이다.

여행경로

  이 문제는 도시의 수가 증가하면 탐색경로의 수가 지수함수적으로 증가한다. 따라서 지적인 문제해결 방법을 고려해야 한다

 

문제해결 방법

탐색형 추론을 이용	절차에 기반을 둔 방법	사례에 기반을 둔 방법
풀어야 할 문제의 방정식을 세울 수 있다면 공식을 이용하여 해결할 수 있다. 문제의 명확화에는 풀어야 할 초기상태 (또는 전제조건) 와 목표상태 2 가지를 명확하게 기술하는 것이 필요하고, 결국 초기상태에서 목표상태 또는 그 반대의 탐색경로를 발견하는 문제로 귀결된다   이 방법은 시행착오적 방법으로 문제를 해결하는 것으로, 대부분의 인공지능 문제가 여기에 해당된다	알고리즘이 존재하는 문제. 알고리즘이 존재하므로 문제해결이 좀 더 쉽게 이루어질 수 있다	과거에 유사한 문제해결의 경험을 이용하여 문제를 해결하는 방법이다

 

문제의 표현

---

문제표현의 기본요소

종류	설명
1. 초기상태	문제의 초기상태
2. 목표상태	해결해야 할 문제의 최종상태
3. 연산자	초기상태에서 목표상태로 상태를 변화시키는 변이 규칙
4. 제약조건	문제를 해결하는 데 지켜야 할 제약사항을 의미
5. 목적함수	최종 목적상태에 효율적으로 도달하기 위해 각각의 상태에서 탐색방법을 결정하는 데 필요한 함수

8-퍼즐의 문제

  8-퍼즐은 9개의 구분된 칸을 가진 판 위에 1에서부터 8까지의 번호를 갖는 조각들이 놓여 있다. 따라서 한 칸은 항상 비어 있고, 조각은 인접한 상하좌우 조각 중 어느 하나가 비게 되면 그쪽으로 이동이 가능하다 이 퍼즐의 해를 얻는 가장 간단한 방법은 목표상태의 판 모양을 얻을 때 까지 각 조각들을 가능한 모든 경우로 움직여 보는 것인데, 이런 방법을 시행착오(trial and err)에 따른 탐색 방법이라 한다

8-퍼즐

상태공간 그래프

  상태공간이란 문제해결 과정에서 나타나는 각 국면을 각각의 상태로 잡을 때 이것들의 집합으로 정의되는 공간이며, 이때 문제표현을 위해 자주 이용되는 방법이 그래프에 의한 표현방법이다

  초기상태, 목표상태, 연산자 및 제약조건이 명백해지면 탐색공간은 유일하게 결정되는데, 이 공간을 상태공간 또는 탐색공간이라 한다 앞서 보인 8-퍼즐의 경우 초기상태에서 목표상태를 얻을 때 까지 연산자를 거듭 적용하여 탐색한다. 초기상태에서 연산자를 적용하여 다음 새로운 상태에 도달하고 이 상태에서 다시 연산자를 적용하여 다음 상태를 얻는 과정을 되풀이하여 최종 목표상태에 도달하면 적용된 연산자들이 이 문제의 해가 되는 것이다. 이 때 각 상태가 그래프의 노드, 상태를 변화시키는 연산자는 그래프에서 노드들을 연결하는 아크로 나타낸다

 

트리 구조

  컴퓨터에서는 그래프를 트리 구조로 변환하여 사용한다

  상태 그래프는 2개의 노드를 연결하는 경로들 중 하나를 제외하고 모두 끊어 끝 노드를 복사하여 부모 노드로부터 뻗어 나오는 서로다른 경로 마디에 하나씩 붙이면 트리 구조로 변환할 수 있다

트리 구조

AND-OR 그래프

  생성 시스템의 작용들을 나타내는 데 편리한 그래프 데이터 구조

  한 노드에 대해 AND 또는 OR의 명칭이 주어지는 그래프로서 부모 노드와 자식 노드간의 단계를 나타낸다

  AND 노드는 모두 처리되어야 하며 OR 노드는 하나만 처리되면 끝낼 수 있다

  어떤 노드가 후계 노드를 가진다면 후계 노드는 모두가 OR 노드이거나 모두가 AND 노드이다. 하지만 노드가 오직 하나의 후계 노드만을 가진다면 이 노드는 OR 노드나 AND 노드 어느 것으로 간주해도 무방하다.

AND-OR 그래프