A* 알고리즘

A* 알고리즘 이란?

• A* 알고리즘은 주어진 출발 꼭짓점에서부터 목표 꼭짓점까지 가는 최단 경로를 찾아내는(다시 말해 주어진 목표 꼭짓점까지 가는 최단 경로임을 판단할 수 있는 테스트를 통과하는) 그래프 탐색 알고리즘 중 하나이다.

• 다익스트라 알고리즘과 유사하나 차이점은 각 꼭짓점 x에 대해 그 꼭짓점을 통과하는 최상의 경로를 추정하는 순위값인 "휴리스틱 추정값" h(x) 을 매기는 방법을 이용한다는 것이다. 이 알고리즘은 이 휴리스틱 추정값의 순서로 꼭짓점을 방문한다. 그러므로 A* 알고리즘을 너비 우선 탐색의 한 예로 분류 할 수 있다.

• A* 알고리즘은 출발 꼭짓점으로부터 목표 꼭짓점까지의 최적 경로를 탐색하기 위한 것이다. 이를 위해서는 각각의 꼭짓점에 대한 평가 함수를 정의해야 한다. 이를 위한 평가 함수 f(n)은 다음과 같다.

  

  • g(n) : 출발 꼭짓점으로부터 꼭짓점 n까지의 경로 가중치

  • h(n) : 꼭짓점 n으로부터 목표 꼭짓점까지의 추정 경로 가중치 -> 휴리스틱 함수

장점과 단점

• 장점

  • 올바른 휴리스틱 함수를 사용하면 보다 빠른 최단거리 길찾기가 가능하다.

  • 주변환경 또는 추정값이 반영된 실질적 최단거리를 찾기 용이하다.

• 단점

  • 휴리스틱 함수 의존도가 강하다.

  • 최단경로를 결정 이후, 환경에 변동이 있을 시 유연하게 반응하기 힘들다.

  • 탐색할 지형정보의 크기가 방대해질수록 관리를 요하는 리스트 목록이 늘어나 시스템 메모리 고갈 및 CPU 처리시간 과다 요인이 될 수 있다는 것

  
  

A* 알고리즘 구현

• 구현방법

  • 우선순위 큐 사용 ( 우선순위 정렬요소는 f / 오름차순)

  1. 시작노드를 우선순위 큐에 넣는다.

  2. 우선순위 큐에서 다음 노드를 꺼내 현재 노드로 설정한다. 현재 노드는 지나간 노드 (close list)로 설정한다.

  3. 현재 노드의 주변 노드를 탐색한다.

     • close list에 포함된 노드라면 무시.

     • 만약 우선순위 큐(open list)에 포함되지 않은 노드라면 f(x)값을 구하고, 현재 노드를 주변 노드의 부모로 설정하고, 우선순위 큐에 등록한다.

     • 만약 주변 노드가 이미 open list에 등록되어 있다면, 자신보다 G값이 적은 노드가 있는지 확인하여 해당 노드를 현재노드의 부모노드로 바꾸고 f(x)를 재계산한다. (G값이 크다면 무시)

  4. 목표에 도달할 때까지 2~3을 반복한다.

  5. 목표를 찾으면 거꾸로 부모노드를 쫒아 역정렬하면 최단거리 경로가 된다.

• pseudo code

pq.enqueue(start_node, g(start_node) + h(start_node))       
// 우선순위 큐에 시작 노드를 삽입한다.

while pq is not empty       // 우선순위 큐가 비어있지 않은 동안
    node = pq.dequeue       // 우선순위 큐에서 pop한다.

    if node == goal_node    
    // 만약 해당 노드가 목표 노드이면 반복문을 빠져나온다.
        break

    for next_node in (next_node_begin...next_node_end)       
    // 해당 노드에서 이동할 수 있는 다음 노드들을 보는 동안
        pq.enqueue(next_node, g(node) + cost + h(next_node)) 
        // 우선순위 큐에 다음 노드를 삽입한다.

return goal_node_dist       
// 시작 노드에서 목표 노드까지의 거리를 출력한다.

출처 : https://ko.wikipedia.org/wiki/A*_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

https://zprooo915.tistory.com/78

https://www.koreascience.or.kr/article/JAKO201115537947327.pdf

연도별 경로 탐색 알고리즘

D star 알고리즘 VS A star 알고리즘

• 객체의 이동 시작점과 목표점이 선정되면 D* 알고리즘의 내부 함수를 통해 셀 별 백 포인터를 형성한 후 초기경로를 생성하여 객체가 백 포인터를 따라 이동한다. 실시간 감지된 장애물은 해당 셀 주변의 백 포인터만을 변경하여 최종 목적지에 도달하게 된다.

• A* 알고리즘과의 특징적 차이는 최초 지형 정보와 경로탐색 과정에서 주어지는 추후 지형정보가 동일한지를 평가하는 기능

• A star 알고리즘이 정적으로 초기의 완전한 지형정보를 바탕으로 전방향 탐색(forward search)으로 최적의 경로를 산출하는 반면, D star 알고리즘은 불완전한 사전정보를 통해 후방향 탐색(backward search)으로 목적지가 변하거나 지형정보가 변화할 때 비교적 신속하게 적용이 가능하다는 점