[알고리즘][길찾기] A* 알고리즘

휴리스틱 길찾기 알고리즘의 대표 / 너비탐색과 다익스트라 알고리즘의 확장판 A* 알고리즘입니다.

 

포스팅 순서는 아래와 같습니다.

• A* 알고리즘
  • 개요
  • 장단점
  • 구현방법
  • 사용예시

 

 

A* 알고리즘

• 개요
  • 노드간의 가중치 뿐 아니라 휴리스틱 함수라는 추정값을 기반으로 최단거리를 탐색하는 알고리즘
  • 공식으로는 f (x) = g(x) + h(x)
    
    • g(x) - 시작노드 부터 현재 노드까지의 가중치 합
    • h(x) - 현재 노드부터 도착 노드까지의 예상 가중치
      • 일반적으로 가중치를 노드 간 거리라 했을 때 도착 노드까지의 대략적인 거리를 의미.
      • 이때 대략적인 거리를 구하는 방식에 따라 또 결과가 달라집니다.
    • 휴리스틱이란? 쉽게 말해 그냥 추정값이라고 보면 됩니다. (대략 이정도 하겠다~ 정도)
      • 그래서 휴리스틱 함수라 하면 추정값을 구하는 방법을 의미합니다. 추정이기 때문에 여러 방법이 있겠죠.
      • 예를 들면, 현재노드에서 목적지까지의 대략적인 거리를 구하는 방법으로 줄자로 제어진 거리, 수학 공식으로 대략적으로 구한 거리, 좌표상으로 구한 거리 등
  • 쉽게 말해 등산하면서 산 위의 정상을 보고 어림짐작으로 가깝겠다 싶은 갈림길을 선택해 가는 겁니다.
  • 결국 A*는 이 휴리스틱 함수에 좌지우지됩니다.
    • 상황에 맞는 적절한 휴리스틱 함수를 결정해야만 좋은 효과를 볼 수 있습니다.

 

• 장단점
  • 장점
    
    • 올바른 휴리스틱 함수를 사용하면 보다 빠른 최단거리 길찾기가 가능하다.
    • 주변환경 또는 추정값이 반영된 실질적 최단거리를 찾기 용이하다.
  • 단점
    
    • 휴리스틱 함수 의존도가 강하다.
    • 최단경로를 결정 이후, 환경에 변동이 있을 시 유연하게 반응하기 힘들다.
• 구현방법
  • 우선순위 큐 사용 ( 우선순위 정렬요소는 f / 오름차순)
    
    1. 1. 시작노드를 우선순위 큐에 넣는다.
    2. 2. 우선순위 큐에서 다음 노드를 꺼내 현재 노드로 설정한다. 현재 노드는 지나간 노드 (close list)로 설정한다.
    3. 3. 현재 노드의 주변 노드를 탐색한다.
       • close list에 포함된 노드라면 무시.
       • 만약 우선순위 큐(open list)에 포함되지 않은 노드라면 f(x)값을 구하고, 현재 노드를 주변 노드의 부모로 설정하고, 우선순위 큐에 등록한다.
       • 만약 주변 노드가 이미 open list에 등록되어 있다면, 자신보다 G값이 적은 노드가 있는지 확인하여 해당 노드를 현재노드의 부모노드로 바꾸고 f(x)를 재계산한다. (G값이 크다면 무시)
    4. 4. 목표에 도달할 때까지 2~3을 반복한다.
    5. 5. 목표를 찾으면 거꾸로 부모노드를 쫒아 역정렬하면 최단거리 경로가 된다.

 

• 사용예시
  • 게임 AI의 길찾기, 미로찾기 등 기본적인 길찾기로 많이 사용.

 

여담

 * A* 알고리즘은 예전에 공부하면서도 느꼈지만, 결국 휴리스틱 함수가 핵심인 듯합니다. 일반적인 예시로 휴리스틱 함수를 최종 도착지까지의 추정 가중치라고하는데, 네비게이션과 같은 변수가 많은 쪽을 예시로 들면, 최종 도착지까지의 실제적인 거리 예상치는 큰 의미가 없을 수 있을 거 같습니다. 그보다는 교통체중, 신호등 갯수, 속도 제한 등이 더 유용해지기도 할 거 같아요. 상황에 따라 노드간 가중치와 휴리스틱 함수를 적절하게 응용할 수 있어야 하지 않을까 싶습니다.

 * 다음은 A*에서 확장된 LPA* 알고리즘을 포스팅하겠습니다.

 

* 포스팅내에 잘못된 내용이나, 문의사항 있으시면 언제든 댓글로 지적해주시면 감사하겠습니다.