문제의 표현 Ai3

지난 시간의 강의 내용 - 인공지능에서 다루는 문제의 특징 - 문제 풀이 접근 단계 - 문제 풀이 기법 1. 문제를 정확하게 정의 2. 문제를 분석 3. 문제를 풀이하기 위해 사용할 수 있는 지식을 표현 4. 적절한 문제 풀이 기법을 선택 적용 - 문제 풀이 기법 1. 탐색에 의한 문제 풀이 2. 문제 축소 Ai3

오늘의 학습내용 - 상태 묘사 - 연산자의 정의 - 상태공간의 그래프 표현 - 문제 표현의 예 Ai3

상태 묘사 - 상태 : 문제 풀이 과정 중 어느 한 지점에서의 문제의 형태 - 상태묘사 : 문제의 상태를 컴퓨터 내에 저장하기 위한 적절한 자료구조로 표현한 것 Ai3

상태 묘사 I - 문제의 상태를 컴퓨터를 이용하여 묘사할 방법을 강구 - 데이터 구조 - 문제의 상태를 컴퓨터를 이용하여 묘사할 방법을 강구 - 데이터 구조 symbol string, 벡터 (vector), 2차원 배열(two dimensional array) 트리(tree), 리스트(list), 등 Ai3

상태묘사의 예 벡터 x리터 y리터 (x, y) Ai3

상태묘사의 예 행렬 #typedef struct { int BlankX, BlankY; char Borad[3][3]; } PuzzleType; 1 2 3 4 5 6 7 8 Ai3

상태묘사의 예 트리 + x A 2 B A2 + 2AB + B2 Ai3

상태 묘사 II 상태 묘사의 선택 - 문제에 따라 - 보다 자연스럽고 - 운영에 효율적인 상태 표현 Ai3

상태묘사의 선택 (예) 산술 표현 A2 + 2AB + B2 ==> (A+B)2 - 이진화 트리(binary tree) 표현 - 선형문자열 표현 Ai3

이진화 트리 표현 - 종단노드(terminal node) - 그 밖의 노드 <그림 슬라이드 6> 산술표현의 변수 상수 심볼 - 그 밖의 노드 연산 부호 : +, -, x,  <그림 슬라이드 6> Ai3

선형문자열 표현 - linear string - 전위표현(prefix notation) ++xAAx2xABxBB 산술부호들은 적확히 2개의 피연산자와 관계 x+AB+AB Ai3

오늘의 학습내용 - 상태 묘사 - 연산자의 정의 - 상태공간의 그래프 표현 - 문제 표현의 예 Ai3

연산자의 정의 주어진 상태를 다른 상태로 변화시키는 것 연산자의 정의 방법 1. 모든 가능한 상태묘사에 대하여 가능한 모든 출력상태묘사를 저장한 테이블 사용 2. 일반화된 변환 규칙으로 정의 Ai3

연산자의 정의 방법 1 모든 가능한 상태묘사에 대하여 가능한 모든 출력상태묘사를 저장한 테이블 사용 방대한 기억공간 필요 모든 규칙을 일일이 지정해 주기 어렵다. Ai3

연산자의 정의 방법 2 일반화된 변환 규칙으로 정의 하나의 상태묘사를 다른 상태묘사로 변화시키는 일종의 연산 능력을 지닌 함수 Ai3

연산자 정의 예 1 물병 문제 눈금이 없는 물병이므로 임의의 양의 물을 넣거나 옮기거나 버리는 연산은 의미가 없다. 조건부여 : 불필요한 연산자를 반복 선택하여 적용하는 노력을 줄일 수 있다. Ai3

연산자의 정의 예 1 물병 문제 현 상태 차기 상태 1 (x,y), x<4 (4,y) 현 상태 차기 상태 1 (x,y), x<4 (4,y) 2 (x,y), y<3 (x,3) 3 (x,y), x>0 (0,y) 4 (x,y), y>0 (x,0) Ai3

연산자의 정의 예 1 물병 문제 현 상태 차기 상태 5 (x,y), x+y≥4 and y>0 (4,y-(4-x)) 현 상태 차기 상태 5 (x,y), x+y≥4 and y>0 (4,y-(4-x)) 6 (x,y), x+y≥3 and x>0 (x-(3-y),3) 7 (x,y), x+y≤4 and y>0 (x+y,0) 8 (x,y), x+y≤3 and x>0 (0,x+y) Ai3

연산자의 정의 예 2 - 상태묘사가 문자열 형태일 경우 - 연산자의 연산을 나타내는 방법 생성규칙(production rules) 다시쓰기 규칙(rewriting rules) 어떻게 하나의 문자열이 다른 문자열로 변환될 것인가를 정의 Ai3

생성규칙 Si  Sj 문자열 Si가 문자열 Sj로 변환될 수 있음을 의미 예) A$  B$ ‘$’부호는 아무 것도 없는 것(empty string, )을 포함한 부분문자열(string) 상기 생성규칙에서는, 원래의 문자열에서 ‘A’만 ‘B’로 바뀔 뿐 나머지 부분은 변화되지 않음을 의미 Ai3

생성규칙 연산자의 예 1. A$A  A 2. $1BAB$2  $1BB$2 3. $1$2$3  $1$2$2$3 3. $1$2$3  $1$2$2$3 (어떤 부분문자열이든지 반복될 수 있다) 4. $1$2$2$3  $1$2$3 Ai3

생성규칙 적용 문제 예 ‘ABCBABC’를 ‘ABC’로 변환 연산자 1. A$A  A 2. $1BAB$2  $1BB$2 3. $1$2$3  $1$2$2$3 4. $1$2$2$3  $1$2$3 Ai3

생성규칙 적용 문제 예 ABCBABC  Ai3

생성규칙 적용 문제 예 ABCBABC  Ai3

생성규칙 적용 문제 예 ABCBABC  ABABCBABC Ai3

생성규칙 적용 문제 예 ABCBABC  3 ABABCBABC Ai3

생성규칙 적용 문제 예 ABCBABC  3 ABABCBABC  Ai3

생성규칙 적용 문제 예 ABCBABC  3 ABABCBABC  ABABC Ai3

생성규칙 적용 문제 예 ABCBABC  3 ABABCBABC  4 ABABC Ai3

생성규칙 적용 문제 예 ABCBABC  3 ABABCBABC  4 ABABC  Ai3

생성규칙 적용 문제 예 ABCBABC  3 ABABCBABC  4 ABABC  4 ABC Ai3

오늘의 학습내용 - 상태 묘사 - 연산자의 정의 - 상태공간의 그래프 표현 - 문제 표현의 예 Ai3

상태공간의 그래프 표현 - 그래프 : - 상태 : 노드 - 연산자 : 아크 * 방향성 아크 노드의 집합과 노드를 연결하는 아크의 집합으로 구성 - 상태 : 노드 - 연산자 : 아크 * 방향성 아크 * 비용이 결부될 수 있다 Ai3

상태공간의 그래프 표현 N N1 N2 Nk ... OP1 OP2 OPk Ai3

상태공간의 예 - 물병문제 4 1 3 2 6 7 Ai3

상태 공간의 내부 표현 (0, 0) (4, 0) (0, 3) (4, 3) (1, 3) (3, 0) 1 2 6 7 Ai3

오늘의 학습내용 - 상태 묘사 - 연산자의 정의 - 상태공간의 그래프 표현 - 문제 표현의 예 Ai3

문제표현의 예 - 외판원 문제 B 8 10 7 10 A 12 E C 6 8 5 9 6 D Ai3

외판원 문제 상태묘사 : 방문한 도시의 리스트 초기상태 : (A) 목표상태 : (A ... A), 모든 도시를 1회씩 포함 Ai3

외판원 문제 연산자 A 도시 방문 B 도시 방문 C 도시 방문 D 도시 방문 E 도시 방문 Ai3

외판원 문제 상태 공간 방문한 도시의 리스트를 노드로 하는 그래프 아크에는 비용이 첨부 Ai3

(A) (AB) (AC) (AD) (AE) (ACB) (ACD) (ACE) (ACDB) (ACDE) (ACDEB) 8 12 6 9 (AB) (AC) (AD) (AE) 8 7 5 (ACB) (ACD) (ACE) 10 6 (ACDB) (ACDE) 10 (ACDEB) 8 (ACDEBA) Ai3

문제표현의 예 – 원숭이와 바나나 문제 - 어느 방 안에 원숭이가 한 마리 있고, 천장에는 바나나가 매달려 있다. 문제표현의 예 – 원숭이와 바나나 문제 - 어느 방 안에 원숭이가 한 마리 있고, 천장에는 바나나가 매달려 있다. 바나나의 높이는 원숭이가 잡기에는 너무 높다. 방 안에는 상자가 있어 그 상자 위에 올라 서면 원숭이가 바나나를 잡을 수 있다. 원숭이가 바나나를 갖기 위해서는 어떻게 행동해야 하는가? Ai3

Ai3

원숭이와 바나나 문제 상태 : (w, x, y, z) w : 원숭이의 좌표 x : 원숭이가 상자 위에 있는가? Ai3

원숭이와 바나나 문제 연산자 ① (w, 0, y, z) (u, 0, y, z) ② (w, 0, w, z) (v, 0, v, z) ③ (w, 0, w, z) (w, 1, w, z) ④ (c, 1, c, 0) (c, 1, c, 1) goto(u) pushbox(v) climbbox grasp Ai3

c b a 초기상태(a,0,b,0) Ai3

c 목표상태(c,1,c,1) Ai3

c b a (a,0,b,0) Ai3

c b a (b,0,b,0) Ai3

c b a (c,0,c,0) Ai3

c b a (c,1,c,0) Ai3

c b a (c,1,c,1) Ai3

출발노드 (a,0,b,0) (u,0,b,0) (v,0,v,0) (b,1,b,0) (v,1,v,0) (u,0,v,0) goto(u) goto(u) (u,0,b,0) u←b, climbbox u←b, pushbox(v) pushbox(v) (v,0,v,0) (b,1,b,0) goto(u) climbbox (v,1,v,0) (u,0,v,0) u←v goto(u) v←c, grasp (c,1,c,1) 목표노드 Ai3

오늘 학습 정리 문제의 표현 : 초기상태, 목표상태, 연산자 문제의 표현 : 초기상태, 목표상태, 연산자 상태묘사 : 문제의 상태를 표현하기에 적합한 적절한 자료구조를 사용하여 표현하고, 이를 이용하여 초기상태 및 목표상태를 표현할 수 있다. 연산자 : 한 상태로부터 천이할 수 있는 차기 상태들을 만들어 내는 일반화된 변환 규칙으로 정의 한다. Ai3