키워드

• A* 알고리즘

진행하는 프로젝트에 필요한 파트라서 오늘 시간을 내서 정리했다.

A* 알고리즘

• 가중치 그래프에서 최단 경로를 탐색하는 알고리즘이다.
• 시작 노드와 목적지 노드를 지정해서 이 두 노드 간 최단 경로를 파악할 수 있다.

vs 다익스트라

• 다익스트라는 목적지가 없다.
• 그러므로 시작 지점에서 모든 정점 대한 최단거리를 계산한다.
  • 모든 정점을 다 검사하다가 원하는 정점을 찾으면 그때 계산을 종료한다.
  • 문제는 이러한 부분 때문에 비효율성이 발생한다.
• 최적 경로가 아닐 수 있다.
  • 어떤 시작점에서 모든 정점을 탐색하기 때문에 최적 경로를 보장하지 않는다.

휴리스틱

• A* 알고리즘에서 휴리스틱 추정값을 이용하여 얼마나 빠르게 최단 경로를 파악할지 결정할 수 있다.
• A* 알고리즘이 다음 탐색 노드를 정하는 방법
  • g(n) : 시작 노드부터 현재 노드까지의 비용
  • h(n) : 현재 노드에서 목표 노드까지의 예상 비용
  • f(n) = g(n) + h(n) : 위의 두 비용의 합이 가장 최소가 되는 다음 노드를 선정한다.
    • f(n)을 찾기 위해 우선순위 큐를 사용.

휴리스틱 함수 h(n)

• 현재 노드 -> 목표 노드까지의 예상 비용을 구하는 함수.
• 휴리스틱 함수 설계에서 알고리즘의 성능이 결정된다.

#내일배움캠프 #스파르타내일배움캠프 #스파르타내일배움캠프TIL