Dijkstra algorithm and A* algorithm

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

1. 다익스트라 알고리즘이란?
   • 다익스트라 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단 경로(Shortest Path) 탐색 알고리즘이다.
     • 이 알고리즘은 하나의 출발점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘이다.
     • 다이나믹 프로그래밍(Dynamic Progrmming)이란?
       • 복잡한 문제를 간단한 하위 문제로 나누어 풀기 위한 알고리즘 디자인 기법이다.
       • 이 기법은 큰 문제를 작은 하위 문제로 나누어 해결하고, 중복되는 하위 문제들을 한 번만 계산하여 중복 계산을 피하는 방식으로 동작한다.
2. 주 사용처 :
   • 흔히 인공위성 GPS 소프트웨어 등에서 가장 많이 사용된다.
3. 작동 원리 :
   • 이 알고리즘은 네트워크 형태로 표현된 그래프에서 가중치가 있는 간선들을 통해 최단 경로를 계산한다.
   • 과정 :
     1. 출발 노드를 설정
     2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장
     3. 탐색되지 않은 노드 중에서 가장 비용이 적은 노드를 선택
     4. 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신
     5. 해당 과정들을 모든 정점들이 탐색될 때까지 반복하면, 출발 노드부터 모든 정점까지의 최단 경로를 구할 수 있다.

다익스트라 알고리즘 사용 예시

• 입력 값을 0으로 설정했을 때의 결과
• 출력 값으로는 0 4 12 19 21 11 9 8 14가 나온다.
• 설명
  • 각 노드 간의 거리 값은 중간에 나와있는 값이며, 0부터 시작하여 각 노드의 최단 거리를 구하는 방식이다.
  • 예를 들어, 0부터 1까지의 최단 거리는 4이고 그 루트는 0 -> 1과 같다.
• 최소 거리 결과 값
  • 0 to 1 = 4
    • 0 -> 1
  • 0 to 2 = 12
    • 0 -> 1 -> 2
  • 0 to 3 = 19
    • 0 -> 1 -> 2 -> 3
  • 0 to 4 = 21
    • 0 -> 7 -> 6 -> 5 -> 4
  • 0 to 5 = 11
    • 0 -> 7 -> 6 -> 5
  • 0 to 6 = 9
    • 0 -> 7 -> 6
  • 0 to 7 = 8
    • 0 -> 7
  • 0 to 8 = 14
    • 0 -> 1 -> 2 -> 8

A* 알고리즘(A Star, 에이 스타)

• A* 알고리즘은 다익스트라 알고리즘의 변형으로, 그래프에서 최단 경로를 찾는데 사용된다.
  • 다익스트라 알고리즘에서는 시작 노드만을 정하고 모든 정점을 구하였다면 A* 알고리즘은 휴리스틱 함수를 사용하며, 시작 노드와 목적지 노드를 분명하게 지정해 이 두 노드 간의 최단 경로를 파악할 수 있다.
    • 휴리스틱(heuristic) 함수는 현재 위치에서 목적지까지의 예상 최단 거리를 추정하는 함수로 사용된다.
  • A* 알고리즘은 이 휴리스틱 함수의 값을 활용하여 다음으로 탐색할 정점을 선택한다.
  • 각 정점의 가중치와 휴리스틱 함수의 값의 조합을 이용하여 우선순위 큐를 유지하면서 탐색을 진행하고, 목적지에 도달하면 최단 경로를 찾을 수 있다.
• A* 알고리즘의 응용 분야
  1. 게임 개발 :
     • 게임에서 NPC의 이동 경로를 계획하는데 사용
     • 플레이어와 상호작용하거나 게임 세계 내에서 다양한 장애물을 피해 목표 지점 도달해야 할 때
  2. 로봇 공학 :
     • 로봇의 자율 이동과 경로 계획에 널리 사용된다.
     • 주어진 환경에서 최적 경로를 찾는데 알고리즘을 활용하여 장애물을 피하고 효율적으로 이동
  3. 지도 탐색 :
     • 지도 어플리케이션에서 출발지와 목적지 사이의 최단 경로를 계산하는데 사용
  4. 인공지능 :
     • 상태 공간 탐색이나 문제 해결에 이 알고리즘이 사용되기도 한다.
  5. 자동화 시스템 :
     • 자동화 시스템에서 경로 계획 문제를 해결하는데 사용
       • 자동차 경로 계획, 로봇 공장 내 이동 경로, 자동차 조립 라인의 부품 이동 등에 적용될 수 있다. - 이 외에도 많은 분야에서 사용된다. 기본적으로 A*알고리즘은 경로 탐색과 최적화 문제를 해결하는데에 사용되며, 휴리스틱 함수를 조정하거나 문제에 맞게 확장함으로써 다양한 도메인에 적용될 수 있다.

다익스트라 알고리즘과 A* 알고리즘 비교 사용

• 아래 그림은 다익스트라와 Greedy Best-First(그리디 알고리즘) 그리고 A*알고리즘을 사용한 형태이다.
  • Greedy Best-First 알고리즘은 똑같이 경로 탐색 문제에서 사용되는 탐색 알고리즘 중 하나이며, 장점은 계산 비용이 낮고 빠른 실행 속도를 가졌다는 점이다.
  • 하지만 지역 최적해(local optimum)에 빠질 수 있으며, 최단 경로를 보장하지 않을 수도 있다.
    • 따라서 탐색 과정에서 다른 경로를 무시하는 경향이 있기 때문에, 탐색 공간이 복잡하거나 잘못된 휴리스틱 함수를 사용할 경우 최적해를 보장하지 못한다.
• 먼저 빨간색 별의 형태가 시작지점이고 X 표시의 보라색이 도착 지점이며, 어두운 색의 블럭은 장애물로 생각하면 된다.
• 각 그림을 통해 특징을 비교했을 때 다익스타라 알고리즘은 시작점으로부터의 거리를 모두 계산하고, Greedy Best-First Search는 목표 지점까지의 거리를 추정한다. 또한 A*는 이 두 거리의 합을 사용한다고 설명이 나와있다.
  • 해당 그림의 장애물을 직접 만들거나 없앨 수 있는데, 이 테스트 과정에서 Greedy Best-First Search가 루트를 찾으면 A*도 같은 영역을 탐색하면서 루트를 찾는다.
  • 여기서 Greedy Best-First Search가 최적의 루트가 아닌 루트를 찾아도 A*는 다익스트라 알고리즘처럼 최적의 루트를 찾지만 다익스트라 알고리즘보다 덜 탐색한다.
  • 아래 참고 사이트에서 직접 테스트가 가능하다
• A* 알고리즘은 다익라스트 알고리즘과 같이 최적의 루트를 찾지만 다익라스트 알고리즘보다 더 빠르게 경로를 찾는다.

References

• https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-greedy-algo-7/(다익스트라 알고리즘 관련 자료 및 예시)
• https://www.geeksforgeeks.org/a-search-algorithm/(A* 알고리즘 관련 자료 및 예시)
• https://www.redblobgames.com/pathfinding/a-star/introduction.html(다익라스트 알고리즘, A* 알고리즘, Greedy Best-First Search 알고리즘 비교 테스트 가능 사이트)