[방통대] 인공지능 중간시험(온라인평가) 과제물 (2021/2학기) 참고자료

소개

"[방통대] 인공지능 중간시험(온라인평가) 과제물 (2021/2학기) 참고자료"에 대한 내용입니다.

목차

(1) A* 알고리즘의 주요 개념, 평가함수, 최소비용 탐색을 할 수 있기 위한 조건에 대하여 설명하고, 균일비용 탐색이나 언덕오르기 탐색과 어떠한 점에서 차이가 있는지 설명하라. (A4용지 2매 내외)
(2) A* 알고리즘을 이용하여 최단길이 경로를 구하는 과정을 보여주는 탐색트리를 구하라. 평가함수는 [그림2]를 예측비용으로 하여 정의하고, 탐색 트리의 각 노드에는 확장되는 순번과 평가함수 값을 표시하라(강의자료 32쪽 참고).

본문내용

(가) A* 알고리즘의 주요 개념, 평가함수, 최소비용 탐색을 할 수 있기 위한 조건에 대하여 설명하고, 균일비용 탐색이나 언덕 오르기 탐색과 어떠한 점에서 차이가 있는지 설명하라.

A* 알고리즘은 그래프의 시작점부터 도착점까지의 최소비용 경로를 구하는 알고리즘이다. 이것은 Dijkstra 알고리즘의 성능을 개선한 것으로, Dijkstra 알고리즘은 잘 알다시피 그래프 상의 최단경로를 찾는 알고리즘으로 유명하다. 그러나 A*와 Dijkstra 두 알고리즘은 모두 찾게 되는 경로가 똑같으며, 간단하게는 현재 탐색 중인 노드에서 목적지까지의 직선거리에 사용한다. A* 알고리즘이 주로 동작하는 방식은 다음과 같다. 먼저 출발지에 인접한 노드들을 OpenList에 넣고 평가함수 (Evolution Function)의 f를 구한다. 이때 g와 h의 합인데 g는 출발지에서 현재 노드 간 실제 가중치로, h는 현재 노드에서 목적지 간 추정 가중치를 의미한다. A* 알고리즘은 가중최단거리 = f(장소)가 핵심인 것이다. OpenList에 들어있는 노드 중 f가 가장 작은, 추정 경로로 추정되는 노드를 OpenList에서 제거하고 CloseList에 추가한다. 그런 다음 그 노드를 탐색 기준으로 삼아 목적지에 도달할 때까지 이 과정을 반복하면 된다. 목적지에 도달하게 된 경우 부모 노드 정보를 이용하여 최단경로를 도출할 수 있다.

참고자료

· 없음