인공지능 과제2

Posted by Patchman
2010.02.15 16:29 Univ Study/인공지능

 

Homework #2

2009. 2학기. 인공지능

 

 

1. 다음 상태공간에서 시작상태는 A이고 목표상태(두개의 겹치는 원)는 F와 J이다(둘 중 어느쪽에 도달해도 목표가 달성되는 것이다). 각각의 노드에는 목표상태까지의 추정값인 heuristic 값 h가 있다. 목표상태에 도달할 수 없는 노드는 h=∞ 값을 가진다. 각각의 노드에서 다음 노드까지의 실제 값은 간선에 표시되어 있다. 아래의 각 탐색 알고리즘에 대하여 노드가 확장되는(선택되는) 순서와 탐색 결과를 구하시오. 동일한 조건의 노드들 중 하나를 선택할 때는 알파벳 순서로 선택한다고 가정하시오. BFS와 DFS에서는 간선 값 및 h 값은 고려되지 않는다. 탐색은 목표상태가 생성되었을 때가 아니라 목표상태가 선택되었을 때 종료됨에 주의하시오.

 

(a) Breadth-first search

(b) Depth-first search

(c) A*

 

(a) BFS: 탐색 순서: A, B, C, D, E, F

탐색 결과: A --> B --> F

(b) DFS: 탐색 순서: A, B, D, E, H, I, F

탐색 결과: A --> B --> F

(c) A*: 탐색 순서: A(0+3), C(2+2), B(3+2), G(5+1), J(6+0)

탐색 결과: A --> C --> G --> J

 

2. 다음은 어떤 공장에서 자동차를 생산하는 단계를 나타낸다. 생산 과정은 A, B, C, D, E 다섯 개의 process로 구성되며, 첫 번째 process는 A이고, 마지막 process는 E이다. XYZ는 X 다음 Y 다음 Z 까지 수행된 상태를 나타내며, ABCDE, ACDBE, ... 등이 완성된 상태로서 goal state에 해당된다. c(S1, S2)는 S1에서 S2 상태까지 진행하는 비용을 나타내며, h(S1)은 S1 상태에서부터 자동차가 완성될 때까지 비용의 추정값이다. 명시되지 않은 비용은 진행할 수 없는 경우로서 ∞이고, *는 임의의 process를 의미한다. 탐색을 이용하여 최소 비용으로 자동차를 완성하는 순서를 찾고자 한다.

 

c(A,AB)=3, c(A,AC)=4, c(A,AD)=2,

c(AB,ABC)=5, c(AB,ABD)=2, c(AC,ACB)=4, c(AD,ADB)=4, c(AD,ADC)=5,

c(ABD,ABDC)=4, c(ADB, ADBC)=5, c(ADC, ADCB)=3, c(****,****E)=1

h(A)=9, h(AB)=9, h(AC)=10, h(AD)=7,

h(ABC)=5, h(ABD)=4, h(ACB)=5, h(ADB)=6, h(ADC)=2, h(****)=1

 

a. f(n) = n 까지의 비용 + h(n) 을 평가함수로 하여 best-first search를 수행하는 과정을 graph로 나타내고, 단계별로 OPEN list가 어떻게 변하는지 쓰시오. 각 state에는 f 값을 명시하시오. 탐색이 끝난뒤 방문한 노드의 순서와 solution path를 쓰시오.

state

open

 

A(9)

A

AD(9) AB(12) AC(14)

AD

ADC(9) AB(12) ADB(12)

ADC

ADCB(11) AB(12) ADB(12)

ADCB

ADCBE(11) AB(12) ADB(12)

ADCBE

 

Solution path : A --> AD --> ADC --> ADCB --> ADCBE

 

b. 위의 search는 최소 비용 생산 순서를 찾지 못한다. 그 이유는 무엇인지 설명하시오.

Admissible heuristic은 0 ≤ h(n) ≤h*(n)이어야 함

h(AB) = 9 > h*(AB) = 7이므로 조건을 만족하지 못함

 

c. 최소 비용 생산 순서를 찾을 수 있도록 h 값을 하나만 바꾸고 a번을 다시 수행하시오.

 

state

open

 

A(9)

A

AD(9) AB(10) AC(14)

AD

ADC(9) AB(10) ADB(12) AC(14)

ADC

AB(10) ADCB(11) ADB(12) AC(14)

AB

ABD(9) ADCB(11) ADB(12) AC(14)

ABD

ABDC(10) ADCB(11) ADB(12) AC(14)

ABDC

ABDCE(10) ADCB(11) ADB(12) AC(14)

ABDCE

 

 

Solution path : A --> AB --> ABD --> ABDC --> ABDCE

 

3. 아래의 그림은 어느 지역의 도로망을 나타낸다. 는 고속도로, 는 국도, 는 일반도로이다. S,A,B,C,D,G 는 각각 도로의 교차 지점이고, 교차 지점 사이의 숫자는 각 지점 사이를 이동하는데 걸리는 운전 시간이다. 즉, S 지점에서 B 지점까지는 5시간이 소요된다. 각 지점의 좌표는 다음과 같다: S(0,0), A(1,0), B(0,1), C(1,1), D(0,2), G(1,2). 고속도로는 가장 빠른 도로로서, 이러한 좌표를 기준으로 거리 1을 이동하는데 1시간이 걸리는 도로이다. S 지점에서 G 지점까지 최소 시간 경로를 A* 알고리즘으로 탐색하려고 할 때 다음에 답하시오.

 

 

a. 각 지점을 state로 하여 탐색 공간을 state space로 나타내시오.

b. 휴리스틱 함수 h(X)는 “X 지점에서 G 지점까지 고속도로가 직선으로 연결되어 있다고 가정했을 때의 소요시간”으로 정의한다. 예를 들어 h(S) = (S~G 사이의 거리) x (1 시간) = 시간이다. 이러한 휴리스틱 함수는 admissible 한가? 설명하시오.

 

답: 각 state에서부터 Goal까지의 실제 걸리는 시간을 h*(s)이라고 했을 때, 고속도로가 가장

빠른 길이고, 직선거리보다 더 짧은 이동거리는 없으므로, h(s) ≤ h*(s)를 만족하며,

이 heuristic 함수는 admissible하다.

즉, 직선고속도로로 이동하는 것을 가정한 소요시간 ≤ 실제 소요시간 이 된다.

STATE

목적지까지 최단소요시간

h(n)

S

8

()

A

7

()

B

3

()

C

5

()

D

1

()

 

 

c. 위의 휴리스틱으로 A*를 진행하면서 단계별로 OPEN list가 어떻게 변하는지 쓰고, 찾아지는 solution path를 쓰시오. OPEN의 각 state는 state(parent, g, h)로 표시하시오.

 

stateOPENCLOSED

S(∅, 0, 2.2)

S(∅) ... S(∅)

 

 

Current

Open List

Close List

S

A(S, 1+2), B(S, 5+)

S

A

C(A, 3+1), B(S, 5+)

S, A

C

B(C, 4+), GOAL(C, 8+0)

S, A, C

B

D(B, 6+1), GOAL(C, 8+0)

S, A, C, B

D

GOAL(D, 7+0)

S, A, C, B, D

Goal

END

END

∴ Solution path = G ← D ← B ← C ← A ← S

 

4. (Programming) 8-puzzle 문제를 DFS, BFS, A* 알고리즘으로 탐색하여 solution을 구하는 프로그램을 작성하고, 아래의 시작상태와 목표상태가 주어졌을 때 각 알고리즘을 사용하는 경우의 방문 state 수와 solution path를 비교하시오. 프로그램은 시작 상태와 목표 상태를 입력 받아 탐색을 수행하고 solution path를 출력한다. 주어진 sample C code를 사용하거나, 새로운 프로그램을 작성할 수 있다.

extra credit) A* 알고리즘에서 두 가지 이상의 heuristic을 사용하여 그 결과를 비교하시오.

 

Start: 1 2 3 Goal: 7 8 1

8 x 46 x 2

7 6 55 4 3

 

 

h1: 제자리에 있지 않은 숫자들의 개수

h2: 제자리에 있지 않은 숫자들의 제자리로부터 거리의 합 이라 할 떄,

 

Solution path 길이: A* with h2 = A* with h1 = BFS =< DFS

방문 state 수: A* with h2 < A* with h1 =< BFS/DFS (경우에 따라 다를 수 있음)

'Univ Study > 인공지능' 카테고리의 다른 글

인공지능 과제4  (0) 2010.02.15
인공지능 과제3  (0) 2010.02.15
인공지능 과제2  (2) 2010.02.15
인공지능 과제1  (0) 2010.02.15
인공지능 프로로그(Prolog) 설치파일  (0) 2010.02.15