2024년 1학기 방송통신대 중간과제물 인공지능)상태공간 탐색으로 이 문제를 풀이하는 방법에 대하여 설명하라 A스타 알고리즘으로 최단경로를 탐색하기 위한 평가함수를 정의 이에 따른 탐색트리 각각의 노드에 평가함수의 계산식 및 노드 확장 순서 등

소개글

2024년 1학기 방송통신대 중간과제물 인공지능)상태공간 탐색으로 이 문제를 풀이하는 방법에 대하여 설명하라 A스타 알고리즘으로 최단경로를 탐색하기 위한 평가함수를 정의 이에 따른 탐색트리 각각의 노드에 평가함수의 계산식 및 노드 확장 순서 등에 대한 보고서 자료입니다.

목차

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

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

* 참고문헌

본문내용

각 지점에서 목적지인 h까지의 직선거리에 해당한다.
이때 의 예측이 정확할수록 은 에 근접할 것이다. 그리고 언제나 을 보다 큰 값으로 예측하지 않는다면 A* 알고리즘은 최소 비용 경로를 반환하는 것을 보장한다. 또한 함수 을 사용함으로써 균일비용 탐색을 한 경우보다 탐색과정이 효율적이다.
이상의 내용을 바탕으로 A* 알고리즘으로 최단경로를 탐색해 보면 다음과 같다.
①ⓐ
=0+22=22
ⓑ
②ⓒ
ⓕ
=10+14=24
=7+14=21
=11+11.5=22.5
③ⓓ
ⓕ
=13+9=22
=12+11.5=23.5
④ⓖ
=18+3.5=21.5
ⓕ
⑤ⓗ
=26+11.5=37.5
=23+0=23
(다) A* 알고리즘으로 최소시간 경로를 구하려고 한다. [그림3]은 각 도로의 평균시속이다. 각 지점에서 목표까지 도달하는 시간을 [그림2]의 직선거리를 평균시속 16km/h로 이동하는 것으로 예측하는 것으로 할 때, 최소시간 경로를 탐색하기 위한 평가함수를 정의하고, 이에 따른 탐색트리를 구하라.
평가함수는 다음과 같이 정의할 수 있다.
이때 평가함수 은 출발노드에서 시작하여 노드 을 거쳐 목표노드(목적지 h)까지 도달하는 데 소요되는 예측시간이다. 은 출발노드에서 현재노드 까지 도달하는데 실제 소요된 시간이다. 은 각 도시에서 목적지까지 도달하는데 소요되는 예측시간이다. 시간은 거리를 속도로 나누어 계산하면 된다.
①ⓐ
=0+22/16=1.38
②ⓑ
ⓒ
ⓕ
=10/20+14/16=1.38
=7/10+14/16=1.58
=11/15+11.5/16=1.45
③ⓔ
=10/20+8/18+6/16=1.32
ⓕ
④ⓗ
=10/20+8/18+9/20+
11.5/16=2.11
=10/20+8/18+7/17+0=1.36
(라) (나)의 방식이 최단경로를 탐색할 수 있는지에 대해 설명하라.
A* 알고리즘은 목표노드까지의 예측비용을 실제 경로비용보다 크게 산정하지 않는다면 최소비용 경로를 탐색하는 것을 보장한다. (나)의 경우 은 각 도시에서 목적지까지 도달하는 거리의 예측치로서 각 지점에서 목적지인 h까지의 직선거리에 해당한다. 직선은 두 점 사이의 최단거리이므로, 은 각 도시에서 목적지까지 도달하는 실제거리인 보다 항상 작거나 같다. 따라서 (나)의 방식이 최단경로를 탐색한다고 할 수 있는 것이다.
(마) (다)의 방식이 최소시간 경로를 탐색할 수 있는지에 대해 설명하라.
A* 알고리즘은 목표노드까지의 예측비용을 실제 경로비용보다 크게 산정하지 않는다면 최소비용 경로를 탐색하는 것을 보장한다. (다)의 경우 은 각 도시에서 목적지까지 도달하는 데 소요되는 예측시간이다. 이 예측시간은 각 도시에서 목적지까지의 직선거리를 평균속도 계산하므로, 은 각 도시에서 목적지까지 도달하는 데 실제 소요되는 시간인 보다 항상 작거나 같다. 따라서 (다)의 방식이 최소시간 경로를 탐색한다고 할 수 있는 것이다.
* 참고문헌
이광형, 이병래(2018), 인공지능, 한국방송통신대학교출판문화원.
스튜어트 러셀 , 피터 노빅(2016), 인공지능. 1: 현대적 접근방식 3판, 제이펍.

키워드

방송통신대인공지능,   방송대인공지능,   방통대인공지능