[인공 지능] A* 알고리즘

소개

인공지능 레포트로 작성한 것입니다.
A* 알고리즘의 효율성에 대해 찾아놓은 것입니다.
많은 도움이 되었으면 합니다.

목차

(1) A* 알고리즘
(2) A* 알고리즘의 허용성
(3) 휴리스틱 함수와 탐색의 효율성

본문내용

(1) A* 알고리즘
A* 는 최단 거리 찾기 에서 가장 훌륭한 선택이 될 것이다. 왜냐하면 Dijkstra's algorithm 이나 Best-First Search (BFS) 보다 훨씬 빠르기 때문이다. A* 는 휴리스틱 방법 (의사결정을 할 때 해당 문제에 대한 정보를 이용하는 것) 과 형식적 방법 (formal method : 문제와 관련된 정보를 사용하지 않지만 formally analyzed 될 수 있는 것)을 결합하기 위해 1968 년에 개발되었다. A* 의 대략의 구조는 그래프 탐색 알고리즘이다. 그러나 다른 그래프 탐색 알고리즘과 다른 점은 목표에 얼마나 근접한 것인지를 평가하는데 휴리스틱 함수를 사용한다는 것이다. 휴리스틱에 의해 먼저 가장 바람직한 방향을 탐색하게 된다. 그 방향이 실패하면 다른 경로를 찾게 된다.즉, A* 는 공간안의 어떤 특정 state 에서 인접한 state를 조사해 나가면서 시작 state에서 목표 state 까지 가장 싼 비용의 경로를 찾는 algorithm 이다. 여기서는 A* 알고리즘에 대한 증명과 그에 대한 예시를 보여주면서 설명하겠다.

참고자료

· * 인공지능- 지능형 에이전트를 중심으로 : Nils,nilsson 저서, 최충민,김준태,심광섭,장병탁 공역, 사이버 택 미디어, 2000
· * http://theory.stanford.edu/~amitp/GameProgramming/ : Amit's Thoughts on path-finding