[2018 : 방통대 인공지능] 인공지능 과제물
- 최초 등록일
- 2019.07.02
- 최종 저작일
- 2018.10
- 4페이지/ MS 워드
- 가격 3,000원
과제정보
학과 |
컴퓨터과학과 |
학년 |
4학년 |
과목명 |
인공지능 |
자료 |
2건
|
공통 |
다음 미로의 입구(●, (0, 0) 위치)에서 출발하여 출구(▲, (4, 4) 위치)로 나오는 가장 짧은 경로를 탐색하려고 한다. 이동은 상, 하, 좌, 우의 방향으로 1칸씩 할 수 있다고 가정한다.
(가) 상태공간 탐색으로 이 문제를 풀이하기 ... 더보기
다음 미로의 입구(●, (0, 0) 위치)에서 출발하여 출구(▲, (4, 4) 위치)로 나오는 가장 짧은 경로를 탐색하려고 한다. 이동은 상, 하, 좌, 우의 방향으로 1칸씩 할 수 있다고 가정한다.
(가) 상태공간 탐색으로 이 문제를 풀이하기 위한 문제표현에 대해 설명 하라.
(나) 균일비용 탐색을 적용하여 문제의 해를 구하려고 한다. 비용을 정의하고, 이에 따른 탐색 트리를 구하라.
(다) A* 알고리즘을 적용하여 문제의 해를 구하려고 한다. 평가함수를 정의하고, 이에 따른 탐색 트리를 구하라. 접기
|
목차
1.상태공간 탐색
2.균일비용 탐색
3.A* 알고리즘
본문내용
(가) 상태공간 탐색으로 이 문제를 풀이하기 위한 문제표현에 대해 설명 하라.
- 미로 문제는 상태공간 탐색 중 그래프로 최적해를 구할 수 있다.
- 그래프 기법 중 DFS(Depth First Search, 깊이우선탐색)와 BFS(Breadth First Search, 너비우선탐색)을 이용하여 최단경로 탐색이 가능하다.
- Minimum Path를 Y ̂ Path를 P, Cost를 C라고 정의할 때, P(0,0)에서 P(4,4)까지의 최단 경로를 구하는 문제는 결국 C를 최소화하는 문제로 해석할 수 있다.
- 즉 문제를 수식으로 표현하자면 최단 경로는 다음과 같이 표현될 수 있다.
(다) A* 알고리즘을 적용하여 문제의 해를 구하려고 한다. 평가함수를 정의하고, 이에 따른 탐색 트리를 구하라.
- A*알고리즘의 정의는 f(n)=g(n)+h(n)과 같이 정의가 가능하다.
- g(n): 출발지점 -> 다음지점 n까지의 weight.
- h(n): 현재지점 -> 다음지점 n까지의 weight.
참고 자료
없음