[인공지능] Goal Reduction (문제축소 기법)

 

문제축소

- 문제 묘사를 문제 축소 연산자를 사용하여 부분 문제 묘사로 변환, 즉 간단한 문제로 분할하는 과정

- 상태공간 탐색 문제

    @ 출발상태들의 조합, S

    @ 상태묘사를 다른 상태묘사로 변환시키는 연산자들의 조합, F

    @ 목표상태의 조합, G

- 부분문제는 상태공간에서의 중요한 중간상태들 사이의 경로를 찾는 문제에 해당

- 문제축소의 목적은 궁극적으로 해가 분명한 원시문제들로 변환시키자는 것

 

문제축소기법

: 상태공간 탐색문제를 보다 간단한 탐색 문제로 연속적으로 축소하는 방법

1) 문제분리의 기점

2) 키 연산자의 발견

 

AND-OR Graph

: 주어진 문제를 후계문제들의 조합으로 축소하는 과정을 표현하는 그래프

- AND/OR 그래프로 표현되는 문제는 상태공간 탐색과 문제축소의 기법을 요구

- AND/OR 그래프에서의 탐색의 목적은 출발 노드가 풀이될 수 있음을 증명하는 것

- 풀이그래프: 출발노드가 풀이되었음을 보이는 것으로 풀이된 노드들로서 구성된 부분 그래프

    · 출발노드: 원래의 문제 묘사

    · 종단노드: 원시문제 묘사

 

AND-OR Graph 탐색

: 풀이 그래프를 찾았을 때 탐색 작업을 성공적으로 종료 -> 출발노드가 풀이되었음을 보이는 것

1) 출발노드는 초기 문제묘사와 관계된다.

2) 후계노드들의 조합은 적용가능한 문제축소 연산자를 가하여서 얻어진다.

3) 포인터들이 설정되어 각 후계노드에서 부모노드를 가리키게 된다.

4) 노드확장 과정은 출발노드가 풀이된 것 또는 풀이될 수 없는 것으로 표시될 때까지 지속된다.