제5장 문제 축소에 의한 풀이방식.

Presentation on theme: "제5장 문제 축소에 의한 풀이방식."— Presentation transcript:

1 제5장 문제 축소에 의한 풀이방식

2 차 례 5.1 문제축소 5.2 AND/OR 그래프 5.3 AND/OR 그래프 표현의 예 5.4 문제축소기법
차 례 5.1 문제축소 5.2 AND/OR 그래프 5.3 AND/OR 그래프 표현의 예 5.4 문제축소기법 5.5 AND/OR 그래프 탐색 5.6 넓이우선 탐색 5.7 깊이우선 탐색 5.8 휴리스틱 탐색

3 5.1 문제축소 5.1.1 문제묘사 어떠한 상태공간 탐색문제도 다음의 세 가지 요소의 문제묘사에 의하여 표현 한다.
① 출발 상태들의 조합 -> S ② 상태묘사를 다른 상태묘사로 변환시키는 연산자들의 조합 -> F ③ 목표상태의 조합 -> G 이러한 3개의 조(S,F,G) 가 한 문제를 정의 한다. 문제와 부분문제가(S,F,G)의 조로 묘사될 때, 부분문제는 상태 공간에서의 중요한 중간 상태들 사이의 경로를 찾는 문제에 해당된다.

4 5.1.2 문제축소 연산자 문제축소 연산자는 주어진 문제묘사를 간단한 문제로 분할한다. 축소된 문제묘사 ->후계문제묘사
축소된 문제묘사 ->후계문제묘사 후계문제묘사 를 생성 -> 부모문제묘사 문제축소의 목적은 궁극적으로는 해가 분명한 원시문제(primitive pro-blem)로 변환시키자는 것이다.

5 5.2 AND/OR 그래프 5.2.1 AND/OR 그래프란? 에이전트가 주어진 문제를 후계 문제들의
조합으로 축소하는 과정을 그래프와 비슷한 그림으로서 나타낸 것 이다.

6 A B C D E F A를 위해 선택할 수 있는 부분문제의 조합을 나타내는 구조

7 A N M F B C D E AND/OR 그래프

8 5.2.2 AND/OR 그래프에 의한 표현 문제축소방식을 표현하는 구조는 AND/OR 그래프이다. 이 그래프에서 출발노드는 원래의 문제묘사 해당되고, 원시문제 묘사에 해당되는 노드를 종단노드(terminal node)라고 한다. AND/OR 그래프에서 행하는 탐색의 목적은 출발노드가 풀이될 수 있음(solvable)을 보이는 것이다.

9 AND/OR 그래프에서 풀이될 수 있는 노드에
대한 정의. ① 종단 노드들은 풀이될 수 있다. ② 종단 노드가 아니면서 OR 후계 노드들을 갖는 노드는, 적어도 후계노드 중의 어느 하 나라도 풀이되면 풀이될 수 있다. ③ 종단 노드가 아니고 AND 후계노드들을 갖고 있다면, 모든 후계노드들이 풀이되어야 이 노드도 풀이된다. 풀이 그래프 -> 출발노드가 풀이됨 -> 풀이된 노드들로서 구성된 부분 그래프로 구성

10 AND/OR그래프의 몇 가지 예와 풀이 그래프
c b c b c b e d e f d e f d t t t f g t t t t t t t t AND/OR그래프의 몇 가지 예와 풀이 그래프

11 풀이될 수 없는 노드에 대한 정의. ① 종단이 아닌 노드로서 후계노드를 갖고 있지 않다면 풀이될 수 없는 노드이다. ② 종단이 아닌 노드로서 OR 후계 노드들을 갖게 되었을 때, 모든 후계노드가 풀이 될 수 없다면 이 노드도 풀이될 수 없다. ③ 종단이 아닌 노드로서 AND 후계 노드들을 갖고 있고 후계노드 중 어느 하나라도 풀이 될 수 없다면, 이 노드도 풀이될 수 없다.

12 5.3 AND/OR 그래프 표현의 예 적분식을 입력으로 받아, 이의 해를 제공해 주는 일을 생각해 보자.
예를 들면 부분 적분법칙은 udv  u dv = u  dv -  v du dv vdu <그림 5-4>적분문제의 표현

13 5.4 문제축소기법 5.4.1 키 연산자－하노이 탑 예 (1)문제분리의 기점 분할을 위해 기점이 되는 상태임을 알아
낼 수 있다고 가정. 초기 문제를 (S,F,{g1}),({g1}, F,{g2}), …, ({g2},F,G )들로 규정된 문제들의 조합으로 축소.

14 (2) 키 연산자의 발견 원판 C를 말뚝 3으로 이동하는 연산자가 문제해결에서 중요한 단계. 이러한 키 연산자(key operator)를 얻을 수 있으면, 문제축소과정을 위한 주요 기점을 결정하는 데 사용.

15 5.4.2 차이－원숭이 바나나 예 키 연산자의 후보가 될 수 있는 것을 구하는 한 가지 방법으로, 주어진 문제(S,F,G)
에서의 차이를 이용하는 방법. 차이란 출발노드의 집합 S 의 원소들이 왜 목표노드가 될 수 없나를 말하는 것이다. 차이가 발견되면 그 차이를 해소할 수 있는 연산자 f∈F를 선택할 수 있다.

16 F S G F F f G1 G 키 연산자 에 의한 문제축소

17 (2) 원숭이 바나나 문제에서 차이 상태묘사 스키마 ( W,X,Y,Z ) 로 이용하여 묘사 W= 원숭이의 수평 위치로, 2차원 벡터 X= 원숭이가 상자 위에 있으면 1, 아니면 0 Y= 상자의 수평 위치로, 역시 2차원 벡터 Z= 원숭이가 바나나를 잡았으면 1, 아니면 0 연산자는 goto, pushbox,dlimbbox, grasp의 4가지, 원숭이와 상자의 초기위치 는 각각 A와 B 바나나의 위치는 C 이다.

18 V X=0 w=y x=0 X=C Y=C X=1 Z=0 연산자 차이 goto(u) pushbox(v) climbbox grasp
있지 않다. V 2.상자가 v 위치에 3.원숭이가 상자 위에 있지 않다. 4.원숭이가 바나나 를 쥐고 있지 않다. 전제조건 X=0 w=y x=0 X=C Y=C X=1 Z=0 적용 결과 (u,-,y,z) (v,0,v,z) (w,1,w,z) (C,1,C,1) 연산자 차이

19 출발상태는 (A, 0,B ,0)로 표현되며, 목표상태는 (w,x,y,1)이다. 연산자의 집합을 F 라 하면, 초기의 문제 P는 P：({(A,0,B,0)},F , {(w,x,y,1}) 로 나타낼 수 있다.

20 차이를 해소하기 위해서는 grasp연산자 적용. graps을 적용시키기 위해서는 전제조건을 만족 시켜야 한다.
(3) 차이를 해소하기 위한 키 연산자와 전제조건 (A,0,B,0)이 목표 상태가 아닌 차이점은 마지막 요소가 1이 아니기 때문. 차이를 해소하기 위해서는 grasp연산자 적용. graps을 적용시키기 위해서는 전제조건을 만족 시켜야 한다. 전제조건은 원숭이와 상자 모두 C위치에 있고, 원숭이가 상자 위에 있으며, 아직 바나나를 쥐고 있지 않은 상태(C,1,C,0)로 표현.

21 다음으로 (C,1,C,0)에 연산자를 적용하여 (C,1,C,1)을 만들어 내는 원시 문제가 만들어 지고, 결과는 이미 목표 상태이다. 즉, 초기문제는 (C,1,C,0)라는 중간상태를 기준 으로 2개의 부분문제로 축소된다. P1：({(A,0,B,0)},F , {(C,1,C,0)})와 P2：({(C,1,C,0)}, {grasp}, {(C,1,C,1)})

22 (4) 부분문제에서 다시 차이와 키 연산자를 부분문제 을 해결하기 위해서는 다시 (A,0,B,0)
와 (C,1,C,0) 사이의 차이를 발견해야 한다. ① 상자가 C에 있지 않다. -> pushbox(C) ② 원숭이가 C에 있지 않다. -> goto(C) ③ 원숭이가 상자 위에 있지 않다. -> climbbox 이 세 가지 연산자를 적용함으로써 세 가지 형태로 문제를 축소 할 수 있다.

23 ({(A,0,B,0)},{(w,x,y,1)}) ({(A,0,B,0)},{(C,0,C,0)})
({(C,1,C,0)},{(C,1,C,1)}) climbbox goto pushbox ({(C,0,C,0)},{(C,1,C,0)}) ({(A,0,B,0)},{(B,0,B,9)}) ({(B,0,B,0)},{(B,0,C,0)})

24 5.5 AND/OR 그래프 탐색 5.5.1 풀이 그래프 ▣ 풀이된 로드 ① 종단노드(terminal node)는 풀이된
노드로서 이는 원시 문제에 해당된다. ② 후계노드를 갖는 종단이 아닌 노드는, 후계노드 중 적어도 하나가 풀이되면, 이 노드도 풀이된다. ③ AND 후계노드를 갖는 종단이 아닌 노드는, 모든 후계노드가 풀이되면, 이 노드도 풀이된 것으로 한다.

25 ▣ 풀이될 수 없는 로드 ① 후계노드가 없는 종단이 아닌 노드는 풀이될 수 없다. ② OR 후계노드가 갖는 종단이 아닌 노드는, 모든 후계 노드가 풀이될 수 없으면, 이 노드도 풀이될 수 없다. ③ AND 후계노드를 갖는 종단이 아닌 노드는, 후계노드 중 어느 하나라도 풀이 될 수 없으면, 이 노드도 풀이될 수 없다.

26 5.5.2 탐색 과정 ● 앞으로 논의할 탐색과정은 다음 단계를 포함한다. ① 출발 노드는 초기 문제묘사와 관계된다.
② 후계 노드들의 조합은 적용 가능한 문제축소 연산자를 가하여서 얻어진다. ③ 포인터들이 설정되어 각 후계노드에서 부모 노드를 가리키게 된다. ④ 노드확장 과정은 출발노드가 풀이된 것 또는 풀이될 수 없는 것으로 표시될 때가지 지속된다.

27 AND/OR 그래프 탐색과 상태공간 그래프 탐색의 차이 상태공간 탐색에서는 출발 노드로부터 목표 노드까지의 경로를 찾는 것이 문제이지만, 문제축소에서는 출발노드로부터 풀이된 노드들로 구성되는 그래프를 찾는것이 문제이다. 즉, 적용할 연산자들을 찾는 것이다. (2) 탐색종료 테스트 문제축소에서 탐색종료에 대한 테스트를 행하기 위해서는, 우선 그때까지 형성된 AND/OR 탐색 그래프에, 풀이표시 프로시저를 적용. 만일 출발 노드가 풀이된 것으로 표시되면 탐색은 종료.

28 (3) 확장순서 AND/OR 그래프의 탐색방법은 노드들의 확장 순서에 따라 서로 차이가 난다.여기서도 넓이우선 (breadth-first) 방식은 노드가 생성 된 순서에 따라 확장시키는 것이고, 깊이우선(depth-first) 방식은 가장 최근에 생성된 노드를 가장 먼저 확장시키는 방법이다. 탐색방법은 일반적인 그래프의 경우보다 트리 (tree)의 경우가 훨씬 간단하다. AND/OR 트리를 탐색하면, 이의 부분인 탐색트리(search tree)를 얻게된다. 그리고 탐색트리 중에서 해를 나타내는 풀이트리(solution tree)를 얻을 수 있다.

29 5.6 넓이우선 탐색 넓이우선 알고리즘 1. 출발노드 S 를 OPEN이라 부르는 리스트에 넣는다.
2. 출발노드가 풀이된 것 또는 풀이될 수 없다는 표시가 될 때까지 다음을 반복한다. 2.1 OPEN으로부터 제일 앞에 있는 노드를 제거하여 이를 CLOSED에 넣는다. 이 노드를 n 이라고 부른다. 2.2 n 을 확장하여 모든 후계노드를 얻는다. 후계노드들을 OPEN의 끝에 넣고, 포인터들을 마련하여 n 을 가리키게 한다. 2.3 후계노드가 있는가 여부에 따라 2.3.1 후계노드가 있다면 후계노드 중에서 종단 노드가 있다면 탐색트리에 풀이표시(solve-labelling) 프로시저를 적용한다. 출발노드가 풀이된 것으로 표시되면 출발노드가 풀이되었음을 나타낼 수 있는 풀이 트리로서 탐색을 종료한다.

30 2.3.1.1. 3 OPEN으로부터 풀이되었거나 조상이 풀이된
노드들을 제거한다.(이는 문제를 한가지 이상의 방법으로 풀이함으로써 낭비되는 불필요한 노력을 막기 위한 것이다). 2.3.2 후계노드가 없다면  n 을 풀이될 수 없는 것으로 표시한다.  탐색트리에 풀이불가표시(unsolvable-labelling) 프로시저를 적용한다. 출발노드가 풀이될 수 없음으로 판명된다면 탐색은 실패로 끝난다. OPEN에서 풀이될 수 없는 조상(ancestor)을 가진 노드들은 제거한다(이는 풀이될 수 없는 문제들을 풀기 위하여 불필요하게 노력이 낭비되는 것을 막기 위한 것이다).

31 풀이표시 알고리즘 1. S-LIST라는 리스트에 풀이된 노드를 넣는다.
될 때까지 다음을 반복한다. 2.1 S-LIST에서 하나의 노드를 꺼낸다. 이 노드를 n 이라 하자. 2.2 만일 노드n 이 그 노드의 부모노드(노드 p 라 하자)의 AND 후계 노드라면 2.2.1 노드 n 의 모든 형제노드에 풀이표시가 되어 있으면, 노드  p 에 풀이표시를 하고, 노드 p 를 S-LIST에 넣는다. 2.3 만일 노드 n 이 노드 p 의 OR 후계노드라면 2.3.1 노드 p 에 풀이표시를 하고, S-LIST에 노드 p 를 첨가한다.

32 풀이불가표시 알고리즘 1. S-LIST라는 리스트에 풀이 불가표시 된 노드를 넣는다.
표시가 될 때까지 다음을 반복한다. 2.1 S-LIST에서 하나의 노드를 꺼낸다. 이 노드를 n 이라 하자. 2.2 만일 노드n 이 그 노드의 부모노드(노드 p 라 하자)의 AND 후계 노드라면 2.2.1 노드 p 에 풀이불가표시를 하고, 노드 p 를 S-LIST에 넣는다. 2.3 만일 노드 n 이 노드 p 의 OR 후계노드라면 2.3.1 노드 n 의 모든 형제노드에 풀이불가표시가 되어 있으면, 노드 p 에 풀이불가표시를 하고,S-LIST에 노드 p를 첨가한다

33 출발노드 1 3 2 4 5 6 7 8 9 10 t B C t t A t <그림 5-7> 넓이우선 탐색에서 노드의 확장순서를 보이는 AND/OR 탐색 트리

34 5.7 깊이우선 탐색 깊이우선 알고리즘 1. 출발노드 S 를 OPEN이라 부르는 리스트에 넣는다.
2. 출발노드가 풀이된 것 또는 풀이될 수 없다는 표시가 될 때까지 다음을 반복한다. 2.1 OPEN으로부터 제일 앞에 있는 노드를 제거하여 이를 CLOSED에 넣는다. 이 노드를 n 이라고 부른다. 2.2 n 의 깊이가 깊이 제한과 같다면, n 은 풀이될 수 없으므로 확장하지 않고, 그렇지 않으면 n 을 확장하여 모든 후계노드들을 생성한다. 이러한 후계노드들을 (임의의 순서로) OPEN의 앞쪽에 넣고  n 으로의 포인터를 첨부한다. 2.3 후계노드가 있는가의 여부에 따라 2.3.1 후계노드가 있다면 후계노드 중에서 종단 노드가 있다면 탐색트리에 풀이표시(solve-labelling) 프로시저를 적용한다.

35 2.3.1.1.2 출발노드가 풀이된 것으로 표시되면 출발노드가
풀이되었음을 나타낼 수 있는 풀이트리로서 탐색을 종료한다. OPEN으로부터 풀이되었거나 조상이 풀이된 노드들을 제거한다. 2.3.2 후계노드가 없다면  n 을 풀이될 수 없는 것으로 표시한다.  탐색트리에 풀이불가표시(unsolvable-labelling) 프로시저를 적용한다. 출발노드가 풀이될 수 없음으로 판명된다면 탐색은 실패로 끝난다. OPEN에서 풀이될 수 없는 조상(ancestor)을 가진 노드들은 제거한다.

36 5.8 휴리스틱 탐색 ● 노드의 확장순서를 휴리스틱 평가함수를 사용하여 정함. ● 평가함수를 정의하는 데 중요한 것은 어떤
노드에서 목표까지의 최적경로(optimal path)의 비용을 예측(estimate)하는 휴리스틱 함수이다. ● AND/OR 트리에서는 주어진 노드에서 시작되는 풀이트리의 비용을 어떻게 예측 할 것인가를 정해야 한다.