A* 알고리즘

• 목적지까지 최단 경로를 찾기 위한 알고리즘이다.
• 가중치가 있는 유향 그래프까지 가능

• Heuristic 함수를 이용하는 것이 특징이다.
  -> 출발 지점에서 인접한 부분까지의 거리와 인접한 부분으로부터 목적지까지 거리(추정치)를 구한다.
  -> 정확하지 않더라도 대충의 추정치를 구해내는 것이다.
  -> 과대평가되지 않은 Heuristic 추정 값을 사용시, 시작 노드에서 목표 노드까지의 최단경로를 구할 수 있다.
  ( 과대평가되지 않은 Heuristic 추정 값 예시 : 유클리드 거리)
• 다익스트라보다 효율적인 알고리즘

• 인접 부분까지의 거리와 목적지까지의 거리 추정치의 합이 최소값인 지점에 대하여 앞에 과정을 반복한다
• 검은색 셀은 이동하지 못한다고 가정

• 위의 과정을 반복하다가 인접 부분과 목표지점이 같으면 종료

• 목표 지점에서 출발하여 값이 작아지는 방향으로 출발 지점까지 연결
• 값이 작아지는 방향이 여러개라면 여러 방향 모두 최단 경로가 된다.

• 이를 거꾸로 가는 방향으로 이동하면 최단 경로 생성

<A* 알고리즘 구현>

• 구현은 Heuristic 함수를 제외하고는 다익스트라와 매우 유사하다.

• Heuristic 추정값은 하한 추정치를 사용한다. 만약 상한 추정치를 사용하면 과대평가 되어 정확한 값을 도출해내지 못한다.
  -> 정확하게 추정하지 못한다면 약하게 추정하자!!
• 그렇다고 너무 낮게 추정해버리면 H[u]=0인 경우와 같이 다익스트라와 거의 같아진다.
  -> 이 경우는 A* 알고리즘의 효율성을 살리지 못한다
• 도착지점에 도달하지 못하는 경우도 있음으로 while문의 종료조건에 나타내준다.
• 현재노드에 대해서 더 짧은 거리가 있다면 해당 거리로 갱신하고 Path를 기록하는 집합에 저장한다.

• 실제 노드에 위의 코드를 적용시켜보면 다음과 같은 주황색 경로가 구해진다.
• 시작 지점에서 목표 지점까지의 최적 거리만 찾는다.

📒 사실 다익스트라와 매우 유사하며, 다익스트라의 성능을 개량하기 위한 알고리즘이다. Heuristic 추정치를 제데로 설정해야 다익스트라보다 효율적인 알고리즘이 된다.