-
질문 & 답변
카테고리
-
세부 분야
게임 프로그래밍
-
해결 여부
미해결
다익스트라 알고리즘 질문이 있습니다.
21.10.15 15:46 작성 조회수 209
0
알고리즘이 시작되는 while문 안에서 처음 하는 동작중에
가장 가까운 distance의 정점를 찾아서 선택하는 과정이 있는데요.
for (int i = 0; i < 6; ++i)
{
// 이미 방문한 정점은 스킵
if (visited[i])
continue;
// 아직 예약된 적이 없거나, 기존 후보보다 멀리 있으면 스킵
if (distance[i] == Int32.MaxValue || distance[i] >= closest)
continue;
// 이때까지 발견한 가장 가까운 후보이기 때문에 정보 갱신.
closest = distance[i];
now = i;
}
굳이 가장 가까운 후보를 찾아야 하는 이유를 잘 모르겠습니다.
어느 쪽을 선택하든 최종적으로는 distance가 가장 짧은 쪽으로 갱신 되는 결과가 나올 것 같은데..
(1번이 아닌 3번을 먼저 선택해도 3번이 선택됐을 때 1번 + 10이 더 가깝기 때문에 3번의 distance가 1번을 통하는 쪽으로 distance가 갱신될것 같은데 굳이 더 짧다는 이유로 1번을 먼저 선택.)
혹시 필수 작업은 아니지만 가장 가까운 후보를 선택하는 것이 최종적으로 가장 짧은 distance를 가질 확률이 높아지기 때문에 해주는 작업일까요?
아니면 반드시 필요한 작업인데 제가 제대로 파악을 못한 걸까요
도움 주시면 감사하겠습니다!
답변을 작성해보세요.
1
Rookiss
지식공유자2021.10.21
-> 실제로 코드를 보면 이미 최선인 1번을 선택(발견된 노드 중 가장 짧은 거리의 노드) 하고도 1번과 연결된 모든 루트에 대해서 비교 하여 distance를 갱신하는 과정이 진행됩니다. 1번을 선택했다고 하여 3번에 대한 검증을 안하지 않는다는 것이죠.
1번을 선택하고 3번에 대해 추가 검증을 하는 이유는,
3번은 아직 '방문'까지는 하지 않은 상태이기 때문입니다.
즉, 이미 '방문'한 노드는 추가적인 검증을 하지 않고 할 필요도 없습니다.
현재 '발견'한 후보군 중에서 cost가 제일 작은 애를 '방문'하는 순간
거기서 100% 끝나는거고, 방문하는 시점에서
그 경로보다 짧은 경로를 뒤늦게 찾을 수 없음을 수학적 귀납법으로 증명할 수 있습니다.
수학 정당성 증명에 익숙하지 않다면 조금 어려운 내용일 수 있지만,
구글에 [다익스트라 정당성 증명]을 검색하면 많은 내용들이 나오니
정말 정말 연구해보고 싶으시다면 참고해보시기 바랍니다.
0
랄프로
질문자2021.10.17
안녕하세요. 빠른 답변 감사드립니다!
적어주신 답변에 대해서는 한참을 보고, 좀 더 찾아보고 다시 글을 적습니다.
그런데도 제가 포인트를 제대로 잡지 못하고 있는것인지.. 완전히 이해가 가지는 않았습니다ㅠ
혹은 제 질문이 조금 잘못 됐을 수도 있을것 같은데요.
일단 정확한 질문은 "이때까지 발견된 노드 중에 거리가 가장 짧은 노드를 방문한다"에 대한 의문이 었습니다.
이때까지 발견한 노드 중에 선택을 하는 것은 맞지만 왜 가장 짧은 거리의 노드일까? 라는 것인데요.
사실상 새로운 정점을 방문하면, 혹시 뒤늦게 더 좋은 경로를 발견한게 아닐까? 라는 마음에
나머지 N개의 정점 경로를 다시 다 방문을 해보면서
cost 계산을 다시 해봐야 한다는 말이 되죠.
-> 실제로 코드를 보면 이미 최선인 1번을 선택(발견된 노드 중 가장 짧은 거리의 노드) 하고도 1번과 연결된 모든 루트에 대해서 비교 하여 distance를 갱신하는 과정이 진행됩니다. 1번을 선택했다고 하여 3번에 대한 검증을 안하지 않는다는 것이죠. 3번을 선택했다 해도 같은 루틴을 반복할 것이고, 간선이 더 있다고 해도 상황이 달라지지 않을것 같다는 생각이 듭니다. 그래서인지 말씀하신 내용이 잘 와닿지가 않고 있습니다 ㅠ
그래서 제가 생각하는 것은 "이때까지 발견된 노드 중에 가장 짧은 노드를 선택하는 것은 나중에 다시 갱신될 여지가 있지만 가장 짧은 거리의 노드를 선택하는 것이 더 가까운 루트일 확률이 높기 때문" 정도로만 혼자 정리를 한 상태인데..
제가 잘못 이해하고 있는 포인트가 있다면 조금만 더 자세하게 알려주시면 감사하겠습니다!
가장 짧은 걸 선택하지 않았을 때 느려지는 예를 조금만 더 디테일하게 부탁드리겠습니다..
강의 제작으로 바쁘실텐데 번거롭게 해드려 죄송합니다.
0
Rookiss
지식공유자2021.10.15
다익스트라를 돌릴 때는 '발견'한 지점과 '방문'한 지점이 의미가 완전 다른데요.
'발견'은 말 그대로 다음으로 방문할 수 있는 '후보'에 불과하나
'방문'한 지점은 이미 더 짧은 경로가 없다고 확정이 나서 처리 완료된 지점입니다.
다음 '방문 후보'를 고를 때는 현재 '발견'한 지점들 중에
가장 cost가 낮은 애를 선택하는 것이 다익스트라의 특징인데요.
이미 선택이 완료된 점이라면, 다른 경로로는 그보다 더 좋은 후보가 없다는게
수학적 귀납법을 증명될 수 있기에 굳이 찾을 필요가 없습니다.
어느 쪽을 선택하든 최종적으로는 distance가 가장 짧은 쪽으로 갱신 되는 결과가 나올 것 같은데..(1번이 아닌 3번을 먼저 선택해도 3번이 선택됐을 때 1번 + 10이 더 가깝기 때문에 3번의 distance가 1번을 통하는 쪽으로 distance가 갱신될것 같은데 굳이 더 짧다는 이유로 1번을 먼저 선택.)
말씀하신대로 제일 cost가 낮은애를 선택하는게 아니라 아무나 고르고,
나중에 뒤늦게 더 좋은 경로로 갱신하는 방법을 택하는 방식이었다면
알고리즘이 말도 안되게 느리게 동작할겁니다.
사실상 새로운 정점을 방문하면, 혹시 뒤늦게 더 좋은 경로를 발견한게 아닐까? 라는 마음에
나머지 N개의 정점 경로를 다시 다 방문을 해보면서
cost 계산을 다시 해봐야 한다는 말이 되죠.
위 그림에서 ---- 하나가 길 1개가 아니라 100만개이고
다 cost가 다르다고 가정해보세요.
100만개를 일일히 방문하면서, 또 그것이 최단거리인지 보기 위해
나머지 정점들에 대해서도 각기 100만개짜리 길을 일일히 연산해야겠죠.
답변 3