[2018 : 방통대 인공지능] 인공지능 과제물

과제정보

학과	컴퓨터과학과	학년	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.

참고 자료

없음