다익스트라, 에이스타

주의 : 해당 게시물에서 작성될 내용은 과제를 해결하기 위해 출처의 내용을 그대로 작성한 부분이 많으며 일절 광고나 수익 창출 목적으로 쓰인 것이 아님을 밝힙니다.

다익스트라

다이내믹 프로그래밍을 활용하여 음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘입니다. 흔히 인공위성이나 GPS 소프트웨어에서 흔하게 많이 사용됩니다. 최단 경로를 알려줄 때 음의 간선을 포함할 수 없기 때문에 현실세계에서 사용하기 매우 적합한 알고리즘입니다. 이 과정에서는 도착까지의 정점뿐만이 아니라 모든 다른 정점까지 최단 경로로 방문하여 각 정점까지의 최단 경로를 찾게 됩니다. 그래프 방향의 유무는 상관없지만, 만약 간선들 중 단 하나라도 가중치가 음수이면 이 알고리즘은 사용할 수 없고 가중치의 합이 음인 사이클이 존재하지 않는 경우에는 '벨먼-포드 알고리즘'을 사용할 수 있습니다. 만약 음의 사이클이 존재한다면 사이클을 도는 경우 경로의 합이 음수로 무한대로 늘기 때문에 그래프의 최단 경로는 구성할 수 없게 됩니다.

 

↓벨먼-포드 알고리즘

벨먼-포드 알고리즘은

가중 유향 그래프에서 노드 사이의 최단 경로를 찾는 알고리즘입니다.

그래프가 가중치를 가지는 방향 있는 변으로 이루어져 있을 때 한 점에서 나머지 다른 점까지의 최단 경로를 찾는 알고리즘입니다. 이러한 목표는 위처럼 다익스트라 알고리즘과 같지만 시간 복잡도는 다익스트라 알고리즘보다 느립니다. 그럼에도 사용하는 이유는 조금 더 유연한 알고리즘으로 변의 가중치가 음수라도 사용할 수 있기 때문입니다.

 

동작 단계로는

먼저 출발 노드와 도착 노드를 설정합니다.

다음으로 '최단 거리 테이블'을 초기화합니다.

현재 위치한 노드의 인접 노드 중 방문하지 않은 노드를 구별하고, 방문하지 않은 노드 중 가장 거리가 짧은 노드를 선택해서 그 노드를 방문 처리 합니다.

그다음 해당 노드를 거쳐 다른 노드로 넘어가는 간선 비용(가중치)을 계산해 '최단 거리 테이블'을 업데이트합니다.

이후부터 구별하고 방문하는 과정을 반복합니다.

 

이러한 알고리즘은 적은 비용으로 가장 빠르게 해답에 도달하는 경로를 찾아내는 대부분의 문제에 응용됩니다. 예를 들어 루빅스 큐브를 푸는 프로그램을 다익스트라 알고리즘으로 만들 수 있고, 내비게이션에서 지도상의 각 도시들을 노드로, 도로들을 간선으로 갖는 그래프로 간주한다면, 두 도시를 잇는 가장 빠른 길을 찾는 문제를 이 알고리즘으로 해결할 수 있습니다.

 

다익스트라 알고리즘에 대한 영상 링크입니다. https://www.youtube.com/embed/tZu4x5825LI

---

에이스타

위의 다익스트라 알고리즘을 확장하여 만들어진 경로 탐색 알고리즘입니다. 드론이나 로봇 차량의 인공지능 주행을 구현하기 위해 개발되었습니다. 지금까지 가장 최소의 비용으로 도달한 지점부터 탐색하는 다익스트라 알고리즘의 원리를 차용한 것으로 A* 알고리즘은 현재 상태의 비용을 g(x), 현재 상태에서 다음 상태로 이동할 때의 휴리스틱 함수를 h(x)라고 할 때 둘을 더한 값이 최소가 되는 지점을 우선적으로 탐색하는 방법입니다.

 

↓휴리스틱

휴리스틱 알고리즘은 불충분한 시간이나 정보로 인하여 합리적인 판단을 할 수 없거나, 체계적이면서 합리적인 판단이 굳이 필요하지 않은 상황에서 빠른 의사결정을 할 수 있도록 고안된 컴퓨터 알고리즘입니다.

 

이 알고리즘을 사용하는 이유는 다익스트라가 가장 현실적인 알고리즘이라고 했지만 현실 문제에는 적용하기가 매우 부담이 되기 때문입니다. 네트워크 같은 디지털 공간이 아닌 현실의 공간을 생각해 봐도 알 수 있습니다. 사람이 다닐 수 있는 '거리'는 아날로그입니다. 이것을 전부 노드화 시키기에는 그 수가 너무나도 많고 탐색해야 하는 공간도 커지게 되고, 시간 복잡도 역시 너무나도 커지게 됩니다.

 

동작 단계로는

기본적인 식은 f(x) = g(x) + h(x)입니다.

먼저 f(x)를 오름차순 우선순위 큐에 노드로 삽입합니다.

다음 우선순위 큐에서 최우선 노드를 pop 합니다.

다음 해당 노드에서 이동할 수 있는 노드를 찾고 그 노드들의 f(x)를 구합니다.

그 노드들을 우선순위 큐에 삽입하고 목표 노드에 도착할 때까지 반복합니다.

슬라이드 퍼즐이 가장 좋은 예시