Dijkstra 알고리즘을 이용하여 출발점에서 종료점까지 가는 최소 비용의 경로를 찾을 수 있습니다. 하지만 시간 복잡도는 $$O(n^2)$$로 좋지 않습니다.
Dijkstra 알고리즘은 종료점까지 도착한 경로들을 구한 뒤 가장 적은 비용의 경로를 선택합니다. 만일 각 노드마다 비용을 확인하여 도중에 탐색을 멈추게할 수 있다면 알고리즘을 개선할 수 있습니다.
예를 들어 출발점과 종료점 사이의 임의의 지점(X)에 A, B가 도착했다고 생각해 봅시다.
둘이 서로 이야기하다 X에 오기까지의 비용을 이야기하게 되었습니다.(여기서 비용은 금액만을 이야기하지 않습니다. 오기까지 지불해야 하는 대가라고 보시면 됩니다.)
A: "X까지 오기까지 3시간 10분 걸렸습니다"
B: "전 3시간 30분 걸렸습니다."
인간 세계에서는 B가 A를 이기기위해서는 더 빨리 이동하거나 부지런히 움직이면 이길 가능성이 있습니다.
하지만 알고리즘에서는 B가 A를 이길 수 없습니다.
알고리즘에서 A,B를 포함한 모든 선수들은 능력이 똑같기 때문입니다.
즉 X에서 종료점까지 가는 시간은 A, B 둘 다 똑 같습니다. 따라서 B는 경기에서 A를 이길 수 없기 때문에 경기를 그만두는게 올바른 선택입니다.
위 내용을 알고리즘에 포함시켜 보도록하겠습니다.
각 노드마다 비용을 기록하는 기록지를 두어 도달까지의 비용을 기록하게합니다.
어떤 경로가 노드에 도착했을때 기록지의 적힌 비용과 자신의 비용을 비교하여 자신의 비용이 더 많다면 더이상 탐색을 진행하지 않고 멈춥니다.
여기서 더 나아가 기록지에 경로와 비용 둘다 적게 한다면,
노드에 도착한 경로의 비용이 기록지의 비용보다 적을때 기록지의 경로의 탐색을 멈추게 할 수도 있을 것 같습니다.
댓글
댓글 쓰기