A* 알고리즘을 통한 최단경로탐색 프로그램

소개글

A* 알고리즘을 통해서 최단경로를 탐색하는 프로그램이며 열린목록(Opened list)와 닫힌목록(Closed list)를 구현하기 위해 큐와 스택을 사용하였습니다. 최적우선트리를 구현하기 위해 큐를 우선순위큐로 구현했습니다.

목차

1. 서 론

2. 관 련 연 구

3. 연 구 내 용

4. 구 현

5. 결론 및 향후과제

6. 참 고 문 헌

본문내용

A*의 알고리즘은 다음과 같이 동작한다.
1. 검색된 인접노드들을 열린목록에 넣는다.
2. 다음 과정을 반복한다.
A. 열린목록에서 가장 낮은 f(최고값) 비용을 찾아 선택한다.
B. 이를 꺼내 닫힌목록에 넣는다.
C. 현재 노드에 인접한 노드들에 대해..
 만약 인접한 노드에 갈 수 없거나 닫힌 목록상에 있다면 제외, 그렇지 않다면 다음을 계속한다.
 만약 열린목록에 있지 않다면, 열린목록에 추가한다.
 만약 열린목록에 있다면, 이 노드가 열린목록에 추가되면 자동으로 f의 값에 의해 나열될 것이다.
D. 그만해야 할 때
 길을 찾는 중 목표노드를 열린목록에 추가하였을 때,
 열린목록이 비어있게 될 경우 (이때는 목표노드 탐색실패)
3. 길 저장하기
목표 노드부터 시작으로 각 노드에 저장된 부모노드값을 되추적한다.

참고 자료

[1] 문병로 저 “쉽게 배우는 알고리즘:관계 중심의 사고법”
[2] 스티브 레이븐 저 “AI Game Programming Wisdom (인공지능 게임 프로그래밍)”
[3] Rich Neapolitan 저, 도경구 역 “Foundations of Algorithms: using C++ pseudocode”
[4] Dale, Nell B 저 “C++ Plus Data Structures”