[알고리즘] 다익스트라(Dijstra) 그리고 에이스타(A*)

🧪휴리스틱(heuristic)

• 불충분한 시간이나 정보 또는 합리적 판단이 필요하지 않은 상황에서 신속하게 사용하는 어림직작의 기술
• 현재 위치에서 목표까지 남은 거리(또는 비용)을 빠르게 추정해주는 함수
• 아직 실제로 가보진 않았지만, 아마 이정도 거리(비용)이 남았을거야. 라고 직관적으로 추측.
• 조건
  • 낙관적 추정 : 실제 비용보다 크지 않아야 함. 실제보다 작거나 같도록.
    (목적지까지 남은 거리를 과대평가 하지 않음. 최단경로를 찾아야하니까)
  • 노드간 이동할 때, 일관적으로 삼각 부등식 만족

1. 다익스트라(Dijkstra) 알고리즘

• 시작점에서 모든 노드까지의 최단 거리를 찾는 알고리즘
• 탐색 기준 : 지금까지의 실제 비용(`g(n)`)만 사용 (휴리스틱 없음)
• `f(n) = g(n)`
• 목표가 어디에 있는지 전혀 모르고, 그냥 전체를 넓게 탐색해나감 (지도 전체를 뒤지면서, 가장 짧은 길을 찾아보자!)
•  예시)
  • 미로찾기 : 미로 전체를 샅샅이 탐색

2. 에이스타(A*) 알고리즘

• 다익스트라(Dijstra) 알고리즘을 확장하여 만들어진 경로 탐색 알고리즘
  • 다익스트라와의 차이점은, 휴리스틱을 사용한다는 점
• 시작점에서 특정 목표까지의 최단 경로를 빠르게 찾는 탐색 알고리즘
• 탐색 기준 : 실제 비용(`g(n)`) + 추정비용(`h(n)`)을 함께 사용
• `f(n) = g(n) + h(n)`
  • `g(n)` : 시작점에서 현재 노드 n까지의 실제 비용
  • `h(n)` : 현재 노드에서 목표까지의 추정치 (휴리스틱)
  • `f(n)` : 총 예상 비용 (우선순위 큐에서 이 값을 기준으로 탐색 순서를 정함)

2-1. 단방향 A*

• 시작점에서 목표까지 한 방향으로 탐색
• 목표 쪽으로 더 똑똑하게 탐색 → 불필요한 경로 탐색 줄어듦
  • 목표가 저쪽이니까, 그 방향을 우선 살펴보자!
• 예시)
  • 네비게이션 : 실제 도로를 다 계산하지 않고도, 휴리스틱으로 서울-부산간의 직선 거리를 사용하여, 탐색할 방향을 부산 쪽으로 좁혀줌 (이 때, 직선거리는 실제 도로 거리보다 짧을 수 있지만, 추정치로 괜찮음)
  • 미로찾기 : 출구가 저기 오른쪽 아래니까, 그쪽으로 가까워지는 칸을 우선 봐야겠다.

2-2. 양방향 A*

• 시작점과 목표점에서 동시에 탐색
• 두 탐색이 중간에서 만나는 지점에서 경로 연결
• 단방향보다 탐색 범위가 줄어들어서 더 효율적
• 예시)
  • 큰 지도에서 시작점과 목표점 양쪽에서 동시에 길 탐색 >> 중간에서 만나 최단 경로 확정