Download presentation
Presentation is loading. Please wait.
1
문제의 표현 Ai3
2
지난 시간의 강의 내용 - 인공지능에서 다루는 문제의 특징 - 문제 풀이 접근 단계 - 문제 풀이 기법
1. 문제를 정확하게 정의 2. 문제를 분석 3. 문제를 풀이하기 위해 사용할 수 있는 지식을 표현 4. 적절한 문제 풀이 기법을 선택 적용 - 문제 풀이 기법 1. 탐색에 의한 문제 풀이 2. 문제 축소 Ai3
3
오늘의 학습내용 - 상태 묘사 - 연산자의 정의 - 상태공간의 그래프 표현 - 문제 표현의 예 Ai3
4
상태 묘사 - 상태 : 문제 풀이 과정 중 어느 한 지점에서의 문제의 형태 - 상태묘사 :
문제의 상태를 컴퓨터 내에 저장하기 위한 적절한 자료구조로 표현한 것 Ai3
5
상태 묘사 I - 문제의 상태를 컴퓨터를 이용하여 묘사할 방법을 강구 - 데이터 구조
- 문제의 상태를 컴퓨터를 이용하여 묘사할 방법을 강구 - 데이터 구조 symbol string, 벡터 (vector), 2차원 배열(two dimensional array) 트리(tree), 리스트(list), 등 Ai3
6
상태묘사의 예 벡터 x리터 y리터 (x, y) Ai3
7
상태묘사의 예 행렬 #typedef struct { int BlankX, BlankY; char Borad[3][3];
} PuzzleType; 1 2 3 4 5 6 7 8 Ai3
8
상태묘사의 예 트리 + x A 2 B A2 + 2AB + B2 Ai3
9
상태 묘사 II 상태 묘사의 선택 - 문제에 따라 - 보다 자연스럽고 - 운영에 효율적인 상태 표현 Ai3
10
상태묘사의 선택 (예) 산술 표현 A2 + 2AB + B2 ==> (A+B)2
- 이진화 트리(binary tree) 표현 - 선형문자열 표현 Ai3
11
이진화 트리 표현 - 종단노드(terminal node) - 그 밖의 노드 <그림 슬라이드 6> 산술표현의 변수
상수 심볼 - 그 밖의 노드 연산 부호 : +, -, x, <그림 슬라이드 6> Ai3
12
선형문자열 표현 - linear string - 전위표현(prefix notation) ++xAAx2xABxBB
산술부호들은 적확히 2개의 피연산자와 관계 x+AB+AB Ai3
13
오늘의 학습내용 - 상태 묘사 - 연산자의 정의 - 상태공간의 그래프 표현 - 문제 표현의 예 Ai3
14
연산자의 정의 주어진 상태를 다른 상태로 변화시키는 것 연산자의 정의 방법
1. 모든 가능한 상태묘사에 대하여 가능한 모든 출력상태묘사를 저장한 테이블 사용 2. 일반화된 변환 규칙으로 정의 Ai3
15
연산자의 정의 방법 1 모든 가능한 상태묘사에 대하여 가능한 모든 출력상태묘사를 저장한 테이블 사용 방대한 기억공간 필요
모든 규칙을 일일이 지정해 주기 어렵다. Ai3
16
연산자의 정의 방법 2 일반화된 변환 규칙으로 정의 하나의 상태묘사를 다른 상태묘사로 변화시키는 일종의 연산 능력을 지닌 함수
Ai3
17
연산자 정의 예 1 물병 문제 눈금이 없는 물병이므로 임의의 양의 물을 넣거나 옮기거나 버리는 연산은 의미가 없다.
조건부여 : 불필요한 연산자를 반복 선택하여 적용하는 노력을 줄일 수 있다. Ai3
18
연산자의 정의 예 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
19
연산자의 정의 예 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
20
연산자의 정의 예 2 - 상태묘사가 문자열 형태일 경우 - 연산자의 연산을 나타내는 방법
생성규칙(production rules) 다시쓰기 규칙(rewriting rules) 어떻게 하나의 문자열이 다른 문자열로 변환될 것인가를 정의 Ai3
21
생성규칙 Si Sj 문자열 Si가 문자열 Sj로 변환될 수 있음을 의미 예) A$ B$
‘$’부호는 아무 것도 없는 것(empty string, )을 포함한 부분문자열(string) 상기 생성규칙에서는, 원래의 문자열에서 ‘A’만 ‘B’로 바뀔 뿐 나머지 부분은 변화되지 않음을 의미 Ai3
22
생성규칙 연산자의 예 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
23
생성규칙 적용 문제 예 ‘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
24
생성규칙 적용 문제 예 ABCBABC Ai3
25
생성규칙 적용 문제 예 ABCBABC Ai3
26
생성규칙 적용 문제 예 ABCBABC ABABCBABC Ai3
27
생성규칙 적용 문제 예 ABCBABC 3 ABABCBABC Ai3
28
생성규칙 적용 문제 예 ABCBABC 3 ABABCBABC Ai3
29
생성규칙 적용 문제 예 ABCBABC 3 ABABCBABC ABABC Ai3
30
생성규칙 적용 문제 예 ABCBABC 3 ABABCBABC 4 ABABC Ai3
31
생성규칙 적용 문제 예 ABCBABC 3 ABABCBABC 4 ABABC Ai3
32
생성규칙 적용 문제 예 ABCBABC 3 ABABCBABC 4 ABABC 4 ABC Ai3
33
오늘의 학습내용 - 상태 묘사 - 연산자의 정의 - 상태공간의 그래프 표현 - 문제 표현의 예 Ai3
34
상태공간의 그래프 표현 - 그래프 : - 상태 : 노드 - 연산자 : 아크 * 방향성 아크
노드의 집합과 노드를 연결하는 아크의 집합으로 구성 - 상태 : 노드 - 연산자 : 아크 * 방향성 아크 * 비용이 결부될 수 있다 Ai3
35
상태공간의 그래프 표현 N N1 N2 Nk ... OP1 OP2 OPk Ai3
36
상태공간의 예 - 물병문제 4 1 3 2 6 7 Ai3
37
상태 공간의 내부 표현 (0, 0) (4, 0) (0, 3) (4, 3) (1, 3) (3, 0) 1 2 6 7 Ai3
38
오늘의 학습내용 - 상태 묘사 - 연산자의 정의 - 상태공간의 그래프 표현 - 문제 표현의 예 Ai3
39
문제표현의 예 - 외판원 문제 B 8 10 7 10 A 12 E C 6 8 5 9 6 D Ai3
40
외판원 문제 상태묘사 : 방문한 도시의 리스트 초기상태 : (A) 목표상태 : (A ... A), 모든 도시를 1회씩 포함
Ai3
41
외판원 문제 연산자 A 도시 방문 B 도시 방문 C 도시 방문 D 도시 방문 E 도시 방문 Ai3
42
외판원 문제 상태 공간 방문한 도시의 리스트를 노드로 하는 그래프 아크에는 비용이 첨부 Ai3
43
(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
44
문제표현의 예 – 원숭이와 바나나 문제 - 어느 방 안에 원숭이가 한 마리 있고, 천장에는 바나나가 매달려 있다.
문제표현의 예 – 원숭이와 바나나 문제 - 어느 방 안에 원숭이가 한 마리 있고, 천장에는 바나나가 매달려 있다. 바나나의 높이는 원숭이가 잡기에는 너무 높다. 방 안에는 상자가 있어 그 상자 위에 올라 서면 원숭이가 바나나를 잡을 수 있다. 원숭이가 바나나를 갖기 위해서는 어떻게 행동해야 하는가? Ai3
45
Ai3
46
원숭이와 바나나 문제 상태 : (w, x, y, z) w : 원숭이의 좌표 x : 원숭이가 상자 위에 있는가?
Ai3
47
원숭이와 바나나 문제 연산자 ① (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
48
c b a 초기상태(a,0,b,0) Ai3
49
c 목표상태(c,1,c,1) Ai3
50
c b a (a,0,b,0) Ai3
51
c b a (b,0,b,0) Ai3
52
c b a (c,0,c,0) Ai3
53
c b a (c,1,c,0) Ai3
54
c b a (c,1,c,1) Ai3
55
출발노드 (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
56
오늘 학습 정리 문제의 표현 : 초기상태, 목표상태, 연산자
문제의 표현 : 초기상태, 목표상태, 연산자 상태묘사 : 문제의 상태를 표현하기에 적합한 적절한 자료구조를 사용하여 표현하고, 이를 이용하여 초기상태 및 목표상태를 표현할 수 있다. 연산자 : 한 상태로부터 천이할 수 있는 차기 상태들을 만들어 내는 일반화된 변환 규칙으로 정의 한다. Ai3
Similar presentations