인공지능(#2) 과제(소개글과 목차 참조)

소개글

인공지능(#2) 과제(소개글과 목차 참조).

목차

없음

본문내용

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를 쓰시오.

1. X = , open { A(a)}, closed = { }
2. X = A , open { AD(9), AB(12), AC(15)}, closed { A }
3. X = AD , open { ADB(10), AB(12), AC(15)}, closed { A, AD }
4. X = ADB , open { ADCB(12), AB(12), AC(15)}, closed { A, AD, ADB }
5. X = ADCB , open { ADCBE(12), AB(12), AC(15)}, closed { A, AD, ADB, ADCB }
6. X = ADCBE !

참고 자료

없음