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

소개글

(방송통신대 인공지능 중간과제물)A* 알고리즘의 주요 개념, 평가함수, 최소비용 탐색을 할 수 있기 위한 조건에 대하여 설명하고 균일비용 탐색이나 언덕오르기 탐색과 어떠한 점에서 차이가 있는지 설명하라 등에 대한 보고서 자료입니다.

목차

a~h로 표시된 8개의 도시를 연결하는 도로망이 있다. [그림1]은 각 도시를 연결하는 도로망과 거리이다. a에서 출발하여 h에 도착하기 위한 경로를 탐색하는 문제를 풀이하려고 한다. [그림2]는 각 도시와 목적지 도시인 h 사이의 직선거리이다.

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

(나) A* 알고리즘을 이용하여 최단길이 경로를 구하는 과정을 보여주는 탐색트리를 구하라. 평가함수는 [그림2]를 예측비용으로 하여 정의하고, 탐색 트리의 각 노드에는 확장되는 순번과 평가함수 값을 표시하라.

참고문헌

본문내용

n)보다 큰 값으로 예측하지 않는다면 A* 알고리즘은 최소 비용 경로를 반환하는 것을 보장한다. 또한 함수 을 사용함으로써 균일비용 탐색을 한 경우보다 탐색과정이 효율적이다.
(나) A* 알고리즘을 이용하여 최단길이 경로를 구하는 과정을 보여주는 탐색트리를 구하라. 평가함수는 [그림2]를 예측비용으로 하여 정의하고, 탐색 트리의 각 노드에는 확장되는 순번과 평가함수 값을 표시하라.
초기상태
OPEN = {a(21, NULL)}
CLOSED = {}
1단계
OPEN = {b(22, a), c(21, a), e(23.5, a), f(20, a)}
CLOSED = {a(21, NULL)}
2단계
OPEN = {b(22, a), c(21, a), e(23.5, a), g(21.5, f)}
CLOSED = {a(21, NULL), f(20, a)}
3단계
OPEN = {b(22, a), e(23.5, a), g(21.5, f), d(22.5, c), f(22, c)}
CLOSED = {a(21, NULL), f(20, a), c(21, a)}
4단계
OPEN = {b(22, a), e(23.5, a), d(22.5, c), f(22, c), h(23, g)}
CLOSED = {a(21, NULL), f(20, a), c(21, a), g(21.5, f)}
탐색트리
* 참고문헌
이광형, 이병래(2018), 인공지능, 한국방송통신대학교출판문화원.
천인국(2020), 인공지능 : 파이썬으로 배우는 머신러닝과 딥러닝, 인피니티북스.
스튜어트 러셀 , 피터 노빅(2016), 인공지능. 1: 현대적 접근방식 3판, 제이펍.

키워드

방송통신대인공지능,   방송대인공지능,   방통대인공지능,   A*알고리즘