인공지능 ) a-h로 표시된 8개의 도시를 연결하는 도로망이 있다. 각 도시를 연결하는 도로망과 거리이다. a에서 출발하여 h에 도착하기 위한 경로를 탐색하는 문제를 풀이하려고 한다.

과제정보

학과	컴퓨터과학과	학년	4학년
과목명	인공지능	자료	2건
공통	a~h로 표시된 8개의 도시를 연결하는 도로망이 있다. [그림1]은 각 도시를 연결하는 도로망과 거리이다. a에서 출발하여 h에 도착하기 위한 경로를 탐색하는 문제를 풀이하려고 한다. [그림2]는 각 도시와 목적지 도시인 h 사이의 직... 더보기 a~h로 표시된 8개의 도시를 연결하는 도로망이 있다. [그림1]은 각 도시를 연결하는 도로망과 거리이다. a에서 출발하여 h에 도착하기 위한 경로를 탐색하는 문제를 풀이하려고 한다. [그림2]는 각 도시와 목적지 도시인 h 사이의 직선거리이다. (가) A* 알고리즘의 주요 개념, 평가함수, 최소비용 탐색을 할 수 있기 위한 조건에 대하여 설명하고, 균일비용 탐색이나 언덕오르기 탐색과 어떠한 점에서 차이가 있는지 설명하라. (A4용지 2매 내외) (나) A* 알고리즘을 이용하여 최단길이 경로를 구하는 과정을 보여주는 탐색트리를 구하라. 평가함수는 [그림2]를 예측비용으로 하여 정의하고, 탐색 트리의 각 노드에는 확장되는 순번과 평가함수 값을 표시하라(강의자료 32쪽 참고). 접기

목차

1. 서론

2. 본론
(가) A* 알고리즘의 주요 개념, 평가함수, 최소비용 탐색을 할 수 있기 위한 조건에 대하여 설명하고, 균일비용 탐색이나 언덕오르기 탐색과 어떠한 점에서 차이가 있는지 설명하라.
(1) A* 알고리즘
(2) 균일비용 탐색과의 비교
(3) 언덕오르기 탐색
(나) A* 알고리즘을 이용하여 최단길이 경로를 구하는 과정을 보여주는 탐색트리를 구하라.

3. 결론

4. 참고문헌

본문내용

경로 검색 알고리즘을 구현하기 위한 고려사항으로는 검색 속도, 하드웨어에서 제조될 때의 영역, 하드웨어의 설계 용이성 및 하드웨어의 응용이 포함된다. 이전에 항법 목적으로 연구한 경로 검색 알고리즘에는 다익스트라 알고리즘과 다익스트라 변경 알고리즘, A* 알고리즘이 포함된다. 벨만 포드 알고리즘의 경우 링크 가중치가 음수인 그래프도 적용할 수 있다. 그러나 실제 지도에는 음의 거리가 없다. 따라서 알고리즘은 항법 경로 검색 하드웨어에 적용할 수 없으며 변형을 적용하여 적용할 수 있다. 또한 지도 정보에 음의 거리가 없는 경우 다중 추가 알고리즘이 빠르게 실행되기 때문에 다익스트라 알고리즘이 선호된다.
A* 알고리즘은 다익스트라 알고리즘을 기반으로 한다. 두 알고리즘은 비슷하지만 가장 큰 차이점은 결과 값이다. 다익스트라 알고리즘은 단일 시작점에서 모든 노드의 최단 경로를 찾는다. 그러나 A* 알고리즘의 경우, 시작 노드와 대상 노드를 정의하여 노드 쌍에 대한 최단 경로를 찾아야 한다. 다익스트라 알고리즘은 집합 Q에 모든 노드를 포함하며 매트릭스 연산을 수행하여 모든 노드 간의 거리를 계산한다. 매트릭스 작업의 경우 더 많은 메모리 리소스가 필요하다.

참고 자료

김종석,이형옥,Kim Jong-Seok,and Lee Hyeong-Ok. "An Algorithm for One-to-One Mapping Matrix-star Graph into Transposition Graph." 한국정보통신학회논문지 18.5 (2014): 1110-1115. (http://www.riss.kr/link?id=A101324902)
Kang Nam Kyu,Son Ho Joon,and Lee Soo-Hong. "Modified A-star algorithm for modular plant land transportation." JOURNAL OF MECHANICAL SCIENCE AND TECHNOLOGY 32.12 (2018): 5563-5571. (http://www.riss.kr/link?id=A107435083)
Zhanying Zhang,and Ziping Zhao. "A Multiple Mobile Robots Path planning Algorithm Based on A-star and Dijkstra Algorithm." International Journal of Smart Home 8.3 (2014): 75-86. (http://www.riss.kr/link?id=A100127950)
Skiena, Steven S. Programming challenges. 서울: 한빛미디어, 2004. (http://www.riss.kr/link?id=M9416441)
서우진. "A* 알고리즘의 하드웨어 구조 설계." 국내석사학위논문 경북대학교 대학원, 2010. 대구 (http://www.riss.kr/link?id=T11972112)