MIT - Introduction to Algorithms
- Lecture 18. Speeding up Dijkstra
다익스트라 속도 높이기 Review
Copyright to MIT & Srini Devadas & Erik Demaine
https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-notes/
code, data, note pdf : https://courses.csail.mit.edu/6.006/fall11/notes.shtml
한글 번역과 슬라이드를 보고싶은 분은 Edwith - 파이썬을 이용한 알고리즘의 이해 항목 강의를 참조하세요.
URL : https://www.edwith.org/introalgorithm/
현실에 적용했을 때 실질적인 성능을 향상시킨다. - 증명은 불가하지만 평균적인 성능 향상
시작점 source S가 있고 특정 도착점 t에 대한 최단 경로의 최적화
실행 시간은 줄일 수 있다. - 직관적 변형 : Bi-Directional Search : 코드 최적화
최악의 시간 복잡도는 변하지 않음
all pairs shortest paths : 6.046 강의에서 다룸
시작점과 도착점을 모를 때 임의의 정점 쌍 (s,t)에 대한 최단 경로를 찾는 문제
Dijkstra : Single Source, Single Target에서는 도착점을 알 때 바로 멈추는 조건문이 존재
pdf에서는 1p 빨간 글씨로 stop if $u = t$라고 적혀있다.
당연히 더 빠름
forward search와 backward search를 동시에 진행 : Bi 양쪽에서 진행
분명히 source와 target을 분명히 알 때 사용 가능
worst-case는 변하지 않으나 방문 정점이 줄게되므로 속도가 향상됨
$d_f[s]=0,d_b[t]=0$나머지 정점들은 무한대를 시작으로 설정하여 서로 다른 우선 순위를 가르킴 - 상호 보완적 complementary
우선 순위가 2배로 필요 (자료 구조를 2배 늘림 - 서로 다른 우선 순위 큐)
$Q_f, Q_b$
backward search를 고려하기 위한 반대 방향 간선들에 대한 이해가 선행돼야함
Q. What is the termination condition? 종료 조건은?
직관 상 탐색은 두 경계가 만났을 때 종료되야함 BFS와 같음
= 더 정확히는 extract min에 의해 어떤 정점 u가 전방향 탐색 forward search와 역방향 탐색 backward search에 모두 추출되었을 때 경계가 만난다고 표현
이는 $Q_f, Q_b$에서 삭제, 추출되었다.
자료 구조 $\Pi_f, \Pi_b$도 있어야함
다만 $\Pi_b$의 경우 간선의 방향과 반대로 가르키는 것을 잊지말아야함
고로 영상에서 설명하는 도착점 t에 대해 가르키는 v2라는 정점이 있을 때 backward search의 경우
$\Pi_b[v2]=t$이다
Q2. How do we find the shortest path from s to t?
= 두 경계가 만나서 탐색을 종료한 후 s에서 t까지 최단 경로를 어떻게 찾을 수 있을까?
Q2-1) 어디에서 $\Pi_f$에서 $\Pi_b$로 전환해야할까?
경계가 만나는 정점
But
Claim : 알고리즘의 종료 조건 정점 w에 대한 해석
apply $\Pi_f$ to w : $\Pi_f \Pi_f \Pi_f \cdots \Pi_f[w]=s$
apply $\Pi_b$ to w : $\Pi_b \Pi_b \Pi_b \cdots \Pi_b[w]=t$
그러나 이 방법은 정확하지 않음
w may not be on the S.P
이유: 정점 w가 최단 거리가 아닐 수 있기 때문이다.
그렇다면 어떻게 고쳐야할까
($\Pi_f, \Pi_b$를 사용해야하는 것은 맞다.)
Init : $d_f[s]=0, d_b[t]=0$
Forward : $d_f[w]=5, d_f[u]=3$
Backward : $d_b[w]=5, d_b[u^\prime]=3$
우선 순위의 입장에서 u가 w보다 더 우선 순위이다.($\because (d_f[u]=3) < (d_f[w]=5)$)
extractMin 함수는 u를 선택하나 결과적으로 진행하다 보면
$d_f[u^\prime]=6 > d_f[w]$이므로 우선 순위가 w로 이동 결과적으로 $d_f[w], d_b[w]$ 양쪽에서 w 정점이 뽑히므로 알고리즘이 종료하게 된다.
5p Figure 3 그림 참조
우리는 최단 경로가 9인 것을 알지만 10이 최단 경로의 길이로 마치게 되는 것
경계가 충돌했을 때 알고리즘의 교묘함을 볼 수 있다.
경계가 edge 가중치와 관계없는 정점에서 만남, 간선의 개수가 가장 적은 경로가 경계와 만나게 됨
그럼 다시 Q2 질문으로 돌아와서 단순히 forward search와 backward search로는 불가능하다는 것을 알았다.
그렇다면 어떻게 해야 최단 거리를 찾을까
terminate condition에 해당하는 정점 w를 찾고 알고리즘을 통해 찾은 모든 정점들에 대한 $d_f[x]+d_b[x]$의 최솟값을 x로 설정(물론 w 포함한 정점들)
x를 통과하는 vertex와 edges들이 최단 경로임을 알 수 있다.
Goal Directed Search $A^*$
Edge weight들을 수정해서 최단 경로를 찾아가는 것
potential function $\lambda$ 사용
다익스트라의 우선 순위에 따라 Edge weights들을 선별하는 것을 적절한 potential function $\lambda$를 사용해 좀 더 빠르게 최단 경로를 찾도록 하는 방법
