[인공지능] 문제 표현 요약

상태공간이란?

초기 상태와 목표상태를 포함하여 임의의 상태로부터 연산자를 통해 생성 가능한 모든 상태들의 집합

 

상태공간 구성요소

• 상태 묘사 형태 : 연산자 적용이 용이한 상태 묘사방식을 선택
• 초기상태와 목표상태에 대한 묘사
• 연산자의 종류

 

상태 묘사란?

다양한 형태의 자료 구조를 사용하여 문제의 상태를 표현하는 것

 

목표 상태 : 탐색과정이 끝났는가 하는 결정

• 새로 생성된 상태묘사들이 목표상태를 묘사하고 있는지 검토하는 정합과정
• 최적화 문제의 경우 최적해를 탐색하는 과정까지 수행

상태 공간 표현(방향성 그래프)

• 상태공간에서 목표를 탐색하는데 유용
• 노드 (node): 상태 묘사를 나타낸다.
• 아크 (arc): 연산자를 표현
• C(Ni, Nj ): 두 노드 사이의 경로에 드는 비용

 

문장 분석

초기 상태: abaab

연산자는 생성 규칙으로 정의하자.

1. ($1)ab($2)→($2)S($2) :부분 스트링 ab는 문장을 나타내는 S로 대치될 수 있다.
2. ($1)aS($2)→($1)S($2)
3. ($1)Sb($2)→($1)S($2)
4. ($1)SS($2)→($1)S($2)

abaab (1번규칙) → Saab (1번규칙) → SaS (2번규칙) → SS (4번규칙) → S

 

스키마: 변수에 따라 달라지는 상태들의 집합 또는 연산자들의 집합

스키마 변수: 변화 가능한 상태를 표현

 

원숭이와 바나나문제

어떤 방에 원숭이, 상자, 바나나가 있다.

상태묘사 : 리스트로 표현

• w =원숭이의 수평위치(2차원 벡터)
• x =원숭이가 상자의 위에 있는지(0 or 1)
• y =상자의 수평위치(2차원 벡터)
• z =원숭이가 바나나를 가졌는지(0 or 1)

스키마 (schema)를 이용한 연산자: 원숭이의 네 가지 행동 표현

• goto(u)：원숭이는 수평위치 (변수)로 간다.
• pushbox(u) ：원숭이는 수평위치 (변수)로 상자를 밀고 간다.
• climb box：원숭이는 상자 위로 올라간다.
• grasp(u) ：원숭이는 바나나를 잡는다.

(w, 0, y, z) goto(u) → (u, 0, y, z)

(w, 0, w, z) pushbox(v) → (v, 0, v, z)

(w, 0, w, z) climbbox → (w, 1, w, z)

(c, 1, c, 0) grasp → (c, 1, c, 1)

 

원숭이와 바나나 문제 풀이