컴퓨터공학과 인공지능 과제 2강
본 자료는 3페이지 의 미리보기를 제공합니다. 이미지를 클릭하여 주세요.
닫기
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
해당 자료는 3페이지 까지만 미리보기를 제공합니다.
3페이지 이후부터 다운로드 후 확인할 수 있습니다.

소개글

컴퓨터공학과 인공지능 과제 2강에 대한 보고서 자료입니다.

본문내용

때문이다, 그리고 다음 state로의 실제 이동경로를 1이라 하면 각 state의 h(n)과 g(n)은 다음과 같다.
state
h(n)
f(n)=h(n)+g(n)
S
4
4
A
3
4
B
2
3
C
1
3
D
3
5
E
2
4
F
1
4
H
1
4
I
1
4
J
1
5
K
1
5
L
1
6
G
0
2. 다음 상태공간에서 시작상태는 A이고 목표상태(두개의 겹치는 원)는 F와 J이다(둘 중 어느쪽에 도달해도 목표가 달성되는 것이다). 각각의 노드에는 목표상태까지의 추정값인 heuristic 값 h가 있다. 목표상태에 도달할 수 없는 노드는 h=∞ 값을 가진다. 각각의 노드에서 다음 노드까지의 실제 값은 간선에 표시되어 있다. 아래의 각 탐색 알고리즘에 대하여 노드가 확장되는(선택되는) 순서와 탐색 결과를 구하시오. 동일한 조건의 노드들 중 하나를 선택할 때는 알파벳 순서로 선택한다고 가정하시오. BFS와 DFS에서는 간선 값 및 h 값은 고려되지 않는다. 탐색은 목표상태가 생성되었을 때가 아니라 목표상태가 선택되었을 때 종료됨에 주의하시오.
(a) Breadth-first search
X
open
close
1
A
2
A
B C
A
3
B
D E F C
A B
4
D
E F C
A B D
5
E
H I F C
A B D E
6
H
I F C
A B D E H
7
I
F C
A B D E H I
8
F (goal)
경로 : A->B->F
(b) Depth-first search
X
open
close
1
A
2
A
B C
A
3
B
C D E F
A B
4
C
D E F G
A B C
5
D
E F G
A B C D
6
E
F G H I
A B C D E
7
F (goal)
경로 : A->B->F
(c) A*
X
open
close
1
A0+3
2
A
C2+2 B3+2
A
3
C
B3+2 G5+1
A C
4
B
G5+1 F7+0 E6+2 D5+∞
A C B
5
G
J6+0 F7+0 E6+2 D5+∞ K8+∞
A C B G
6
J (goal)
경로 : A->C->G->J
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 한가? 설명하시오.
-> h(x)는 heuristic cost
-> h*(x)는 actual cost(distance) from x to G(Goal)
state
h(X)
h*(X)
D
1
1
C
1
5
B
√2
4
A
2
7
S
√5
8
- A*알고리즘은 f(n)=g(n)+h(n)이고 이때 h(n)h*(x) 이어야 Admissible하다고 볼 수 있다.. 위에 표에서 보면 모든 state의 h(x)의 값은 h*(x) 보다 작은 것을 알 수 있다. 그러므로 이러한 휴리스틱 함수는 admissible 하다고 볼 수 있다.
c. 위의 휴리스틱으로 A*를 진행하면서 단계별로 OPEN list가 어떻게 변하는지 쓰고, 찾아지는 solution path를 쓰시오. OPEN의 각 state는 state(parent, g, h)로 표시하시오.
state
open
close
1
S()
2
S()
A(S,1,2) B(S,5,√2)
S()
3
A(S)
C(A,3,1) B(S,5,√2)
S() A(S)
4
C(A)
B(C,4,√2) G(C,9,0)
S() A(S) C(A)
5
B(C)
D(B,7,1) G(C,9,0)
S() A(S) C(A) B(C)
6
D(B)
G(D,8,0)
S() A(S) C(A) B(C) D(B)
7
G(D) (goal)
solution path : S->A->C->B->D->G
  • 가격1,900
  • 페이지수9페이지
  • 등록일2020.12.09
  • 저작시기2007.8
  • 파일형식한글(hwp)
  • 자료번호#1141805
본 자료는 최근 2주간 다운받은 회원이 없습니다.
다운로드 장바구니