[2024-1] 방송통신대학교(방통대) 인공지능 중간과제물 평가 30점 만점 받은 리포트

소개

2024-1학기 인공지능 중간과제물 평가에서 30점 만점 받은 리포트입니다.

A* 알고리즘이 최소비용 경로를 찾는 것이 보장되는 조건과 해당 조건을 만족했을 때 최소비용 경로를 찾는 것이 보장되는 이유 등, A* 알고리즘에 대한 자세한 설명을 포함하고 있습니다.

문제는 아래와 같았습니다.

[그림1]은 a~h 지점을 연결하는 도로망에서 각 지점간 도로의 거리를 나타내는 그림이고, [그림2]는 각 지점에서 목적지인 h까지의 직선거리로, (중략) a 지점에서 출발하여 h 지점에 도착하는 경로를 탐새갛려고 할 때, 다음 질문에 답하라.

(각 그림은 리포트에 포함 시켜놓았습니다.)

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

목차

없음

본문내용

(가)
상태공간 탐색으로 이 문제를 풀이하려면 먼저 문제의 상태를 컴퓨터가 이해할 수 있는 형태로 표현하고 적절한 탐색 알고리즘을 적용해야한다. 이를 위해서는 문제의 상태를 표현할 수 있는 적합한 자료구조를 선정하고, 탐색 알고리즘을 결정하여 구현해야한다.
이러한 유형의 문제의 간선 상태 표현에 주로 쓰이는 자료구조는 인접리스트와 인접 행렬 등이 있다. 인접 리스트는 각 지점 별로 이동 가능한 다른 지점들의 정보를 리스트 형태로 저장하는 자료구조다. 인접 행렬은 2차원 배열 형태로 각 지점 간의 거리(또는 연결 상태)를 저장하는 자료구조다. 간선 정보 저장을 위한 인접행렬 또는 인접리스트와 현재 방문한 지점 정보, 현재 소모한 비용과 같은 추가적인 상태 정보를 포함하는 구조체 등을 이용하면 이 문제를 적절하게 표현하는 자료구조를 만들 수 있다.

참고자료

· 없음