인공지능 ) a-h 지점을 연결하는 도로망에서 각 지점간 도로의 거리를 나타내는 그림, 각 지점에서 목적지인 h까지의 직선거리로, 각 도시

소개

인공지능
[그림1]은 a~h 지점을 연결하는 도로망에서 각 지점간 도로의 거리를 나타내는 그림이고, [그림2]는 각 지점에서 목적지인 h까지의 직선거리로, 각 도시에서 목적지까지 도달하는 거리의 예측치로 사용할 수 있다. a 지점에서 출발하여 h 지점에 도착하는 경로를 탐색하려고 할 때, 다음 질문에 답하라.

목차

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

참고문헌

본문내용

상태공간 탐색의 경우 탐색의 구성요소를 명확하게 하는 것으로부터 시작한다. 우선 초기 상태를 정의해야 한다. [그림1] 상태의 경우 a에서 출발하는 것을 전제하고 있기 때문에, 초기 상태는 노드 a에서 출발하는 것으로 정의할 수 있다. 그다음으로 목표 상태를 정의한다. [그림1] 상태의 경우 h에 도착하는 것을 목표로 하고 있기 때문에, 목표 상태는 노드 h에 도착하는 것으로 정의할 수 있다. 정의가 완료되었으므로, 초기 상태 노드부터 노드를 확장해 나가면서 목표 노드까지 도달하는 경로를 연산자를 활용하여 탐색하면 된다. [그림1]의 경우 경로를 찾는 것이 목표이므로 연산자는 기준 노드로부터 연결된 이동 경로, 그리고 도착한 위치의 노드가 해당한다. 예를 들어 초기 노드 a의 경우 각각 b, c, f에 경로가 이어져 있으므로, 후속 노드로 b, c, f 노드를 지정하여 확장할 수 있다. 상태공간 탐색은 구성요소의 정의, 그리고 정해진 구성요소에 따른 시행착오를 거쳐 최종적으로 목표 노드인 h에 도달하는 방식이다.

참고자료

· 인공지능. 이광형, 이병래 지음. 출판사 : 출판문화원. 발행일 : 2018년 07월 25일