[컴퓨터과학과]인공지능_중간과제물

소개글

"[컴퓨터과학과]인공지능_중간과제물"에 대한 내용입니다.

목차

(가) 상태공간 탐색으로 이 문제를 풀이하는 방법에 대하여 설명하라.
(나) A* 알고리즘으로 최단경로를 탐색하기 위한 평가함수를 정의하고, 이에 따른 탐색트리를 구하라. 각각의 노드에 평가함수의 계산식 및 노드 확장 순서를 표시하라(강의 3강 30번 슬라이드 참고).
(다) A* 알고리즘으로 최소시간 경로를 구하려고 한다. [그림3]은 각 도로의 평균시속이다. 각 지점에서 목표까지 도달하는 시간을 [그림2]의 직선거리를 평균시속 16km/h로 이동하는 것으로 예측하는 것으로 할 때, 최소시간 경로를 탐색하기 위한 평가함수를 정의하고, 이에 따른 탐색트리를 구하라.
(라) (나)의 방식이 최단경로를 탐색할 수 있는지에 대해 설명하라.
(마) (다)의 방식이 최소시간 경로를 탐색할 수 있는지에 대해 설명하라.

본문내용

(가) 상태공간 탐색으로 이 문제를 풀이하는 방법에 대하여 설명하라.
상태공간 탐색으로 푸는 방법은 다음과 같습니다.
상태공간 탐색은 문제를 해결하기 위해 가능한 모든 상태(노드)를 탐색하고, 목표 상태에 도달하는 경로를 찾는 탐색 알고리즘입니다. 문제를 풀이하는 과정은 초기 상태를 설정하고 목표 상태에 도달하게끔 연산자를 찾는 과정으로, 비용을 고려하여 트리 등의 그래프를 이용해 구할 수 있습니다. 연산자의 적용을 대응하는 아크 값을 C(x, y)라고 두면 노드x로부터 노드y까지의 비용의 합을 나타냅니다. 이렇게 비용을 배정한 다음 최소의 비용이 드는 경로를 찾아야 합니다. 그림1과 그림2의 최단경로를 구하는 문제에서 가능한 모든 방법으로 이동시키는 시행착오를 거친 탐색을 수행합니다. 각각의 노드에 연산자를 적용시켜 후계노드를 만들고 이어서 후계노드를 만드는 과정을 거쳐 문제를 해결하는 방식이 상태공간 탐색이라고 합니다.

참고 자료

없음