A 지점에서 출발하여 H 지점으로 가는 경로를 찾는 문제를 해결하려고 한다. 각 지점 사이의 거리(단위는 km)와 그 구간의 주행속도(단위는 km/h, 양 방향이 동일하다고 가정함)는 [그림1]과 같고, 각 지점으로부터 H까지의 직선거리는 [그림2]와 같다.

소개

인공지능 만점 받은 과제물 입니다.
계산식과 이미지 등이 들어 있어, 과제하고 이해하기 편하실 껍니다.
참고하시어 좋은 성적 받으세요.

목차

Ⅰ. 상태공간 탐색으로 이 문제를 풀이하는 방법의 개념
1. 상태공간탐색 개념
2. 최적경로 탐색하기 위한 A* 알고리즘의 문제풀이 개념

Ⅱ. A* 알고리즘을 이용하여 최단길이 경로를 구하려고 한다. [그림2]를 예측비용을 구하는데 활용하여 평가함수를 정의하고, 이에 따른 탐색 트리를 보여라. 각 탐색 트리의 각각의 노드에는 확장 순번과 평가함수 값을 표시하라.

Ⅲ. A* 알고리즘을 이용하여 최소시간 경로를 구하려고 한다. 예측 비용은 평균시속 17km/h를 가정하여 [그림2]를 바탕으로 정하고, 이에 따라 평가함수를 정의하라. 이에 따른 탐색 트리를 (나)와 동일한 방법으로 보여라.

Ⅳ. 참고문헌

본문내용

1. 상태공간탐색 개념
상태공간을 탐색하여 문제가 주어진 시점인 초기상태에서 시작을 하여 문제에서 원하는 결과 값인 목표상태에 도달할 수 있게 일련의 연산자를 찾는 것으로 문제를 풀이할 수 있는 방식이다.
상태공간 탐색의 방식에서 최적의 경로를 탐색하는 방법에는 맹목적 탐색의 균일비용 탐색과 경험적 탐색의 A*알고리즘이 있다.
맹목적 탐색은 목표노드의 위치와 문제에 대한 정보를 생각하지 않고 탐색의 순서가 미리 정해있는 것에 따라 탐색하는 방법이며, 경험적 탐색은 완벽하게 맞아 떨어지는 것은 아니지만 수많은 시행착오를 통해서 목표노드에 대한 가장 긍정적인 결과를 얻기 위해 탐색하는 방법이다.

경로를 탐색하는 알고리즘에는 다익스트라 알고리즘과 A* 알고리즘이 주로 거론이 되는데 두 지저간의 최적경로를 찾아주는 공통점이 있으며 차이점은 다익스트라 알고리즘은 현재까지의 최적 경로 정보를 이용하여 최종적인 최적 경로를 찾는 알고리즘인 것에 반해 A* 알고리즘은 관측되지 않은 미래의 정보에 대하여 경험 등을 통해서 최적의 경로를 찾는 알고리즘이다. 가장 유망할 듯한 노드(best-first search)라는 표현을 사용한다.

2. 최적경로 탐색하기 위한 A* 알고리즘의 문제풀이 개념
A* 알고리즘은 출발노드로부터 목표 노드까지의 최적 경로를 탐색하는 알고리즘으로 각각의 노드에 대한 평가함수를 정의해야 한다.

참고자료

· 이병래·이광형 공저,『인공지능』, 한국방송통신대학교출판문화원, 2018
· 박종진, 최규석 공저,『인공지능시스템』, 21세기사, 2008
· 정기철 저,『실용적인 예제를 통해 배우는 인공지능 입문서 체험 인공지능』, 홍룡과학출판사, 2016