문서 보기역링크PDF로 내보내기맨 위로 이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요. # A* 알고리즘 # Ⅰ.대표적인 탐색 알고리즘, A* 알고리즘의 개요 ## 가. A* 알고리즘의 개요 * A* 알고리즘은 그래프의 시작점에서 도착점에 이르는 최단경로를 찾는 알고리즘으로 현재 위치한 정점에서 목적점에 이르는 잔여거리를 추정하여 다음 노드를 선택하는 휴리스틱 알고리즘 * 시작 노드에서 목적노드에 이르는 최단 경로를 찾아야 하는 경우 사용하는 알고리즘으로 최적우선탐색에 목적점에 이르는 추정치를 같이 사용하여 다음 정점을 선택하는 탐색 방법 ## 나. A* 알고리즘의 특성 * A\*는 시작으로부터 목표에 이르는 하나의 경로를 찾음 * A\*는 최적의 경로를 찾음 * A\*는 휴리스틱을 가장 효율적으로 사용 # Ⅱ. A* 알고리즘의 평가함수 및 의사코드 ## 가. A* 알고리즘의 평가함수 * 현재 노드에서 목적노드까지 가는 거리가 비슷하다면 시작노드에서 현재노드까지 온거리가 짧은 쪽이 전체적인 이동거리가 더 짧음 * A* 알고리즘이 관리하는 상태 리스트는 아직 조사하지 않은 상태들이 담긴 Open List이고 다른 하나는 이미 조사한 상태를 담은 Closed List로 구성됨 * 최단 거리 탐색 경로를 찾기 위해서는 평가 함수의 아래와 같은 2가지 사항을 고려해야 함 1. 시작노드에서 현재노드(N)까지 온 실제의 최단거리(g(n)으로 표시) 2. 현재노드(N)에서 목적노드까지의 실제의 최단거리(h(n)으로 표시) * 이를 고려하여 만든 평가 함수 f는 f(n)=g(n)+h(n)임 * 하지만 h(n)는 정확하게 알지 못하는 거리 이므로 * h\*(n):현재 노드(n)에서 목적노드 가지의 추정치를 사용하면 * 다음 정점을 선택하기 위한 A*알고리즘의 평가 함수는 f\*(n)=g(n)+h\*(n) open/a-알고리즘.txt 마지막으로 수정됨: 2020/06/02 09:25저자 127.0.0.1