전자 회로 설계는 그것들을 함께 연결하여 종종 몇 가지 컴포넌트들의 pins들이 동일하게 만들 필요가 있다. n개의 핀들의 한 집합을 상호 연결하기 위해서, 우리는 n - 1개의 wires의 한 배치를 사용할 수 있다. 그리고 각각이 두 개의 핀들을연결한다. 모든 그러한 배치들 중에서, 최소한 양의 wire를 사용하는 것이 보통 가장 바람직하다.
우리는 이러한 wiring problem을 연결되고, 방향이 없는 그래프 G = (V, E)로 모델링할 수 있다.여기에서 V는 pins들의 집합이고, E는 pins들의 쌍사이에 있는 가능한 상호연결의 집합이다. 그리고 각 edge (u,v) in E에 대해서, 우리는 w(u, v)의 한 가중치를 갖는다. 이것은 u와 v를 연결하는 (필요한 wire양) 비용을 명시한다. 우리는 그러고나서 모든 정점들을 연결하고, 총 가중치 w(T) = sum_in (u,v) of W -> w(u, v)가 최소가되도록하는 비순환 subset T in E를 찾기를 바란다. T는 비순환적이고, 모든 정점들을 연결하기 때문에, 그것은 한 트리를 형성 해야만한다. 그래서 우리는 그것을 spanning tree라고 부른다. 왜냐하면 그것이 그래프 G를 "span(가로지르다)"하기 때문이다. 우리는 트리 T를 결정하는 문제를 minimum-spanning-tree problem(actually, minimum-weight spanning tree)이라고 부른다. Figure 23.1은 연결된 그래프와 최소신장트리의 한 예시를보여준다.
이 챕터에서, 우리는 최소 신장 트리 문제를 풀기위해 두 가지 알고리즘들을 볼 것이다: Kruskal의 알고리즘과 Prim의 알고리즘. 우리는 쉽게 일반적인 binary heaps를 사용하여 O(ElgV) 시간안에 그것들의 각각을 쉽게 작동시킬 수 있다. Fibonacci heaps를 사용하여, Prim의 알고리즘은 O(E + VlgV) 시간안에 작동한다. 그리고 이것은 binary-heap 구현 에 비해 만약 |V|가 |E|가 더 작다면 개선된다.
Chapter 16에서 묘사되었듯이, 두 개의 알고리즘은 greedy algorithms이다. 한 그리디 알고리즘의 매 단계는 몇 가지 가능한 선택들 중의 한 가지를 만들어야 한다. 그 그리디 전략은 그 순간에 최선인 선택을 하는 것을 고려한다. 그러한 전략은 일반적으로 그것이 항상 globally하게 문제에 대한 최적의 해결책을 찾도록 보장하지 않는다. 그러나, 최소 신장 트리 문제에 대해, 우리는 어떤 그리디 전략이 최소의 가중치를 갖는 spanning tree를 만든다고 증명할수 있다. 비록 너가 이 챕터를 Chapter 16과 별개로 읽을 수 있을지라도, 여기에서 보여지는 그리디 방법들은 거기에서 소개된 이론적 개념들의 고전적인 적용이다.
섹션 23.1은 한 번에 한 개의 edge를 추가하여 spanning tree를 성장시키는 "generic" minimum-spanning-tree method를 소개한다. Section 23.2는 그 generic method를 구현하는 두 개의 알고리즘들을 준다. Kruskal 에 의해, 그 첫 번째 알고리즘은 Section 21.1의 connected-components algorithm과 유사하다. Prim에 의해 그 두 번째 알고리즘은 Dijkstra의 shortest-paths algorithm과 닮는다 (Section 24.3).
트리는 한 그래프의 유형이기 때문에, 정확해지기 위해서, 우리는 그것의 edges가 아닌 그것의 정점의 관점에서 또한 트리를 정의해야만한다. 이 챕터가 그것들의 edges의 관점으로 트리들에 집중할지라도, 우리는 트리 T의 정점들이 T의 edge가 있는 것들이라는 이해와 함께 작동할 것이다.
23.1 Growing a minimum spanning tree
우리가 연결되고, 가중치 함수 w : E -> R이 있는 방향이 없는 그래프 G = (V, E)를 가지고 있고, 우리가 G에 대한 최소 신장 트리를 찾기를 바란다고 가정하자. 우리가 이 챕터에서 고려하는 그 두 개의 알고리즘들은 그 문제에 대해 그리디 접근법을 사용한다. 비록 그것들이 이 접근법을 적용하는 방법에서 다를지라도.
이 그리디 전략은 다음의 generic method에 의해 포착된다. 그리고 이것은 한 번에 한 간선씩 minimum spanning tree를 성장시킨다. 그 generic method는 edges들의 한 집합 A를 관리한다. 그리고 다음의 loop invariant를 유지한다:
각 iteration 이전에, A는 어떤 minimum spanning tree의 subset(부분집합)이다.
매 단계에서, 우리는 이 invariant를 위반하지 않고 A에 추가할 수 있는 edge(u, v)를 결정한다. A U {(u, v)}가 또한 minimum spanning tree의 부분집합이라는 의미에서. 우리는 A에 대해 그러한 간선을 safe edge라고 부른다. 왜냐하면 우리가 그 invariant를 유지하면서, A에그것을 안전하게 추가하기 때문이다.
GENERIC-MST(G, w) 1 A = 0 2 while A does not form a spanning tree 3 find an edge(u,v) that is safe for A 4 A = A U {(u, v)} 5 return A
우리는 다음의 loop invariant를 사용한다:
Initialization : line 1 이후에, 그 집합 A는 자명히 loop invariant를 만족한다.
Maintenance : lines 2-4에서 그 loop는 오직 안전한 edges를 추가하여 invariant를 유지한다.
Termination : A에 추가된 모든 edges들은 최소 신장 트리에 있고, 그래서 line 5에서 반환되는 집합 A는 최소 신장 트리이다.
물론, 까다로운부분은 line 3에서 안전한 edge를 찾는 것이다. line 3가 실행 될 때, invariant가 A가 T에 포함되도록 하는 최소 신장 트리 T가 있다는 것을 명령하기 때문에, 그 하나가(safe edge) 존재해야 한다. 그 while loop body내에서, A는 T의 적절한 부분집합 이여야 한다. 그러므로 edge(u,v) in T가 있어야만 한다. (u,v)가 아직 A에 있지않고, (u,v)가 A에 대해 safe하도록.
이 섹션의 나머지에서 우리는 안전한 간선들을 인지하기 위해 한 규칙 (Theorem 23.1)을 제공한다. 그 다음 섹션은 효율적으로 안전한 간선들을 찾기위해 이 규칙을사용하는 두 개의 알고리즘들을 묘사한다.
우리는 처음에 몇 가지 정의들이 필요하다. 방향이 없는 그래프 G = (V, E)의 cut(S, V - S)는 V의 partition이다. 그림 23.2는 이 개념을 보여준다. 우리는 만약 끝점들 중 하나가 S에 있고, 다른 것이 V - S에 있다면, an edge (u,v) in E가 그 cut(S, V-S)를 가로지른 다고 말한다. 우리는 만약 A에 있는 어떠한 간선도 cut을 가로지르지 않다면, 한 cut은 edges들의 집합 A를 respect한다고 말한다. 만약 가중치가 cut을 가로지르는 어떤 가선들 중에서 최소라면, 한 edge는 한 cut을 가로지르는 light edge이다. ties의 경우에 cut을 가로지르는 한 개 이상의 light edge가 있을 수 있다는 것에 주목해라. 좀 더 일반적으로, 우리는 만약 가중치가 그 특성을 만족하는 어떤 간선중의 최소라면 한 edge가 주어진 특징을 만족하는 light edge라고 말한다.
safe edges를 인지하는 한 가지 규칙은 다음의 정리에 의해 주어진다.
Theorem 23.1
G = (V, E)가 E에 정의된 실수값의 가중치 함수 w가 있는 연결되어있고 방향이 없는 그래프라고 하자. A가 G에 대해 몇 가지 최소 신장 트리에 포함되는 E의 부분집합이라고 하고,
(S, V - S)가 A를 respect하는 G의 어떤 cut이라고 하고, (u, v)가 (S, V - S)를 가로지르는 light edge라고 하자. 그러면 edge(u, v)는 A에 대해 safe하다.
Proof T가 A를 포함하는 최소 신장 트리라고 하고, T가 light edge(u,v)를 포함하지 않다고 가정해보자. 만약 그렇게 한다면, 우리는 끝났기 때문이다. 우리는 cut-and-paste 기법을사용하여 A U {(u,v)}를포함하는 또 다른 최소 신장트리 T'를 구성할 거싱다. 그리고 그것으로 인해, (u, v)가 A에 대해 safe edge라는것을 보여준다.
그 edge(u, v)는 그림 23.3이 보여주듯이, T에서 u에서 v로 가는 간단한 경로 p에서의 edges들이 있는 cycle을 형성한다. u와 v가 cut (S, V - S)의 반대편에 있기 때문에, T에 있는 적어도 한 edge가 simple path p에 놓여있고, 또한 그 cut을 가로지른다. (x, y)가 그러한 edge라고 해보자. 그 edge(x,y)는 A에 있지 않다. 왜냐하면 그 cut이 A를 respect하기 때문이다. (x,y)가 T에서 u에서 v로 가는 unique simple path에 있기 때문에, (x, y)를 제거하는 것은 T를 두 컴포넌트들을 분해한다. (u, v)를 더하는 것은 그것들을 새로운 spanning tree
T' = T - {(x,y)} U {(u,v)} 를 형성하도록 재연결 한다.
우리는 다음에 T'가 minimum spanning tree라는 것을 보여준다. (u, v)가 (S, V - S)를 가로지르는 light edge이고, (x, y)가 또한 이 cut을 가로지르기 때문에, w(u, v) <= w(x,y)가 된다. 그러므로,
w(T') = w(T) - w(x,y) + w(u,v)
<= w(T)
그러나 T는 minimum spanning tree이다. w(T) <= w(T')가 되게하는. 따라서, T'는 또한 minimum spanning tree가 되어야 한다.
(u,v)가 실제로 A에 대해 safe edge라는 것을 보여줘할 것이 남아있다. 우리는 A in T'라는 것을 가졌다. 왜냐하면 A in T이고, not (x,y) in A이기 때문이다; 따라서, A U {(u,v)} in T'이다. 결과적으로 T'가 minimum spanning tree이기 때문에, (u,v)는 A에 대해 safe하다.
정리 23.1은 우리에게 연결된 그래프 G = (V, E)에 대한 GENERIC-MST method의 작동에 대한 더 좋은 이해를 준다. 그 method가 진행됨에 따라, 그 집합 A는 항상 acyclic이다; 만약 그렇지 않다면, A를 포함하는 minimum spanning tree는 cycle을 포함할 것이고, 모순이다. 실행하는 어떤 지점에서, 그 그래프 G_A = (V, A)는 forest이고, G_A의 연결된 컴포넌트들 각각은 tree이다. (트리들 중 몇몇은 하나의 정점을 포함할지도 모른다, 그럴 경우에 예를들어, 그 메소드가 시작된다: A는 비어있고, 그 forest는 |V| trees를 포함한다, 각 정점에 대해 하나씩) 게다가, A에 대한 어떤 safe edge (u,v)는 G_A의 별개의 컴포넌트들을 연결한다.
A U {(u, v)}가 acyclic해야하기 때문이다.
GENERIC-MST의 lines 2-4에서 while loop는 |V| - 1번 실행한다. 왜냐하면 그것은 각 반복에서 minimum spanning tree의 |V| - 1 간선들 중의 하나를 찾아야 하기 때문이다. 초기에, A = 0일 때, G_A에는 |V|개의 트리들이 있고, 각 반복은 그 숫자를 1씩 줄인다. 그 forest가 오직 단 하나의 tree만을 포함할 때, 그 메소드는 종료된다.
Section 23.2의 두 알고리즘들은 Theorem 23.1에 대해 다음의 따름 정리를 사용한다.
Corollary 23.2
G = (V, E)가 E에 정의된 실수값 가중치 함수 w가 있는 연결되고 방향이 없는 그래프라고 하자. A가 G에 대한 어떤 minimum spanning tree에 포함되는 E의 부분집합이라고 하고,
C = (V_c, E_c)가 그 forest G_A = (V, A)에서 연결된 컴포넌트 (tree)라고 하자. 만약 (u,v)가 G_A에 있는 어떤다른 컴포넌트에 C를 연결하는 light edge라면, 그러면 (u,v)는 A에 대해 safe하다.
Proof 그 cut (V_c, V - V_c)는 A를 respect하고, (u, v)는 이 cut에 대해 light edge이다. 그러므로, (u, v)는 A에 대해 safe하다.
23.2 The algorithms of Kruskal and Prim
이 섹션에서 설명되는 두 개의 최소 신장 트리 알고리즘들은 generic method를 정교하게 만든다. 그것들은 각각 GENERIC-MST의 line 3에서 safe edge를 결정하는 특정한 규칙을 사용한다. Kruskal의 알고리즘에서, 그 집합 A는 forest인데, 그 forest의 정점들이 주어진 그래프의 모든 정점들이다. A에 추가된 그 safe edge는 항상 그래프에서 두 개의 다른 컴포넌트들을 연결하는 least-weight edge이다. Prim의 알고리즘에서, 집합 A는 단일의 트리를 형성한다. A에 추가되는 safe edge는 항상 트리를 트리에 없는 정점으로 연결하는 least-weight edge이다.
========================================================
Kruskal 알고리즘을 공부하기전에, Chapter 21의 Disjoint sets에 대한 자료구조를 공부해야 한다.
http://chanhaeng.blogspot.com/2018/09/21-data-structures-for-disjoint-sets.html
========================================================
Kruskal's algorithm
Kruskal의 알고리즘은 forest에서 어떤 두 개의 트리들을 연결하는 모든 edges들 중에서 least weight인 한 edge(u,v)를 찾아서 growing forest에 더 할 safe edge를 찾는다. C1과 C2가 (u,v)로 연결되는 두 개의 트리라고 하자. (u, v)는 C1과 어떤 다른 트리를 연결하는 light edge이기 때문에, Corollary 23.2는 (u,v)가 C_1에 대해 light edge라는 것을 암시한다. Kruskal의 알고리즘은 greedy algorithm으로서 자격이 있는데, 매 단계에서, 그것이 forest에 가장 적을 가능성이 있는 weight의 한 edge를 추가하기 때문이다.
Kruskal algorithm의 우리의 구현은 Section 21.1의 connected components를 연산하는 알고리즘과 같다. 그것은 몇 가지 원소들의 서로소 집합을 유지하는 서로소 집합 자료구조를 사용한다. 그 연산 FIND-SET(u)는 u를 포함하는 집합의 대표 원소를 반환한다. 따라서, 우리는 FIND-SET(u)가 FIND-SET(v)와 같은지를 검사하여 두 개의 정점들 u와 v가 같은 tree에 속하는 지를 결정할 수 있다. 트리를 결합하기 위해서, Kruskal의 알고리즘은 UNION 절차를 호출한다.
MST-KRUSKAL(G, w) 1 A = 0 2 for each vertex v in G.V 3 MAKE-SET(v) 4 sort the edges of G.E into nondecreasing order by weight w 5 for each edge (u,v) in G.E, taken in nondecreasing order by weight 6 if FIND-SET(u) != FIND-SET(v) 7 A = A U {(u,v)} 8 UNION(u,v) 9 return A
그림 23.4는 Kruskal 알고리즘이 어떻게 작동하는지를 보여준다. Lines 1-3은 집합 A를 empty set으로 초기화하고 |V| trees를 만들도록 한다. 각 정점을 포함하는 하나씩. lines 5-8에 있는 for loop는 가중치를 가장 낮은것에서 높은 순으로 간선들을 조사한다. 그 loop는 각 간선(u,v)에 대해, 끝점 u와 v가 같은 트리에 속하는지를 체크한다. 만약 그렇다면, 그러면 그 edge(u,v)는 cycle만드는 것 없이 forest에 추가되어질 수 없다. 그래서 그 edge는 버려진다. 만약 그렇지 않다면, 두 개의 정점들을 다른 트리에 속한다. 이 경우에 line 7은 A에 edge(u,v)를 추가하고, line 8은 그 두 개의 트리들에 있는 정점들을 합친다.
그래프 G = (V, E)에 대한 Kruskal 알고리즘의 작동시간은 우리가 disjoint-set data structure를 어떻게 구현했는지에 달려있다. 우리는 우리가 Section 21.3의 union-by-rank와 path-compression heuristics가 있는 disjoint-set-forest 구현을 사용한다고 가정하자. 왜냐하면 그것이 asymptotically하게 알려진 것중에 가장 빠른 구현이기 때문이다. 그 집합 A를 line 1에서 초기화하는 것은 O(1) 시간이 걸리고, line 4에서 edges들을 정렬하는 시간은 O(ElgE)가 걸린다. (우리는 LINES 2-3의 for loop에 있는 |V| MAKE-SET 연산의 비용을 곧 설명할 것이다.) lines 5-8의 for loop는 disjoint-set forest에 대해 O(E) FIND-SET과 UNION operations을 수행한다. |V| MAKE-SET 연산에 따라, 우리는 총 O((V + E)a(V)) 시간이 걸린다. 여기에서 a는 Section 21.4에 정의된 바로 느리게 성장하는 함수이다. 우리가 G가 연결되었다고 가정하기 때문에, 우리는 |E| >= |V| - 1을 가지고, 그래서 disjoint-set operations는 O(Ea(V)) 시간이 걸린다. 게다가, a(|V|) = O(lgV) = O(lgE)이기 때문에, Kruskal 알고리즘의 총 작동 시간은 O(ElgE)이다. |E| < |V|^2인 것을 관찰하면, 우리는 lg|E| = O(lgV)라는 것을 갖게되고, 그래서 우리는 Kruskal 알고리즘의 작동 시간을 O(ElgV)라고 다시 말할 수 있다.
Prim's Algorithm
Kruskal의 알고리즘 처럼, Prim의 알고리즘은 Section 23.1의 generic minimum-spanning-tree의 특별한 경우이다. Prim의 알고리즘은 그래프에서 최단 경로를 찾는 Dijkstrak의 알고리즘처럼 작동한다. 그리고 우리는 24.3에서 그 다익스트라 알고리즘을 볼 것이다. Prim 알고리즘은 집합 A에 있는 간선들이 항상 single tree를 형성하는 특징을 가진다. 그림 23.5가 보여주듯이, 그 트리는 임의의 root vertex r부터 시작하고, 그 트리가 V에 있는 모든 정점을 가로지를 때 까지 성장한다. 각 단계는 그 트리에 A를 isolated vertex를 연결하는 light edge를 추가한다 - A의 edge가 incident하지 않는 것이다. Corollary 23.2에 의해, 이 규칙은 A에 safe한 edges들만을 더한다; 그러므로, 알고리즘이 종료될 때, A에 있는 간선들은 minimum spanning tree를 형성한다. 이 전략은 greedy로서 자격이 있다. 각 단계에서, 그것은 트리에 트리의 가중치에 가능한 최소의 양만을 기여하는 edge를 추가하기 때문이다.
Prim의 알고리즘을 효율적으로 구현하기 위해서, 우리는 A에서 edges들에 의해 형성되는 트리에 더 할 새로운 edge를 선택하는 빠른 방법이 필요하다. 아래의 슈도코드에서, 연결된 그래프 G와 성장될 minimum spanning tree의 root r은 알고리즘에 대한 입력들이다. 알고리즘을 실행하는 동안, 트리에 있지 않는 정점들은 key attribute를 기반으로 min-priority queue Q에 있다. 각 vertex v에 대해, v.key attribute는 v를 트리에 있는 한 정점에 연결하는 어떤 edge의 최소 가중치이다; 전통적으로 만약 그러한 edge가 없다면 v.key = infinity이다. v.pi attribute는 트리에 있는 v의 부모이다. 그 알고리즘은 implicitly하게, GENERIC-MST의 집합 A를 다음으로서 유지한다:
A = {(v, v.pi) : v in V - {r} - Q}.
그 알고리즘이 종료될 때, min-priority queue Q는 비어있다; G에 대한 최소 신장 트리 A는 따라서
A = {(v, v.pi) : v in V - {r}}.
MST-PRIM(G,w,r) 1 for each u in G.V 2 u.key = infinity 3 u.pi = NIL 4 r.key = 0 5 Q = G.V 6 while Q != 0 7 u = EXTRACT-MIN(Q) 8 for each v in G.adj[u] 9 if v in Q and w(u,v) < v.key 10 v.pi = u 11 v.key = w(u,v)
그림 23.5는 Prim의 알고리즘이 어떻게 작동하는지를 보여준다. Lines 1-5는 각 정점의 key를 infinity로 설정한다 (root r은 제외하고, 그 r의 key는 0으로 설정된다, 그것이 처리될 첫 번째 vertex 가 되도록 하기 위해서이다), 각 정점의 부모를 NIL로 설정하고, 그 min priority queue Q가 모든 정점을 포함하도록 설정해라. 그 알고리즘은 다음의 세 개의 파트의 loop invariant를 유지한다:
lines 6 - 11의 while loop의 매 반복전에,
- A = {(v, v.pi) : v in V - {r} - Q}.
- 최소 신장 트리에 이미 배치된 정점들은 V - Q에 있는 정점들이다.
- v in Q인 모든 정점들에 대해, 만약 v. pi != NIL이라면, 그러면 v.key < infinity이고, v.key는 v를 최소 신장 트리에 이미 배치된 어떤 정점에 연결하는 light edge (v, v.pi)의 무게이다.
Line 7은 그 cut (V - Q, Q)을 가로지는 light edge에서 Q에 있는 정점 u incident를 확인한다 (첫 번째 반복에서는 제외하고, 거깅서 line 4에 의해 u = r이다). 집합 Q로부터 u를 제거하는 것은 트리에 있는 정점들의 집합 V - Q에 그것을 더한다. 따라서, (u, u.pi)를 A에 더한다. lines 8 - 11의 for loop는 u에 인접한 모든 정점 v의 key와 pi attributes를 업데이트하지만, tree에 있는 것은 아니다. 그것으로 인해 이것은 그 loop invariant의 세 번째 부분을 유지한다.
Prim의 알고리즘의 작동시간은 우리가 min-priority queue Q를 어떻게 구현했는지에 의존한다. 만약 우리가 Q를 binary min-heap (see Chapter 6)로 구현한다면, 우리는 O(V) 시간에, lines 1- 5를 수행하기 위해 BUILD-MIN-HEAP procedure를 사용할 수 있다. 그 while loop의 body는 |V|번 실행한다. EXTRACT-MIN 연산은 O(lgV) 시간이 걸리기 때문에, EXTRACT-MIN의 모든 호출에 대한 총 시간은 O(VlgV)이다. lines 8-11에서의 for loop는 전적으로 O(E)번 실행한다, 모든 인접 리스트의 길이의 합계가 2|E|이기 때문이다. for loop 내에서, 우리는 line 9에서 Q에 있는 membership test를 그것이 Q에 있는지 없는지를 구분하는 각 정점에 대해 1비트를 유지하고 정점이 Q에서 제거될 때 그 비트를 업데이트하여 상수 시간으로 구현할 수 있다. line 11에서의 할당은 min-heap에서 implicit DECREASE-KEY 연산을 포함한다. 그리고 binary min-heap은 O(lgV) 시간으로 그것을 지원한다. 따라서, Prim 알고리즘의 전체 시간은 O(VlgV + ElgV) = O(ElgV)가 되고, 이것은 Kruskal 알고리즘 구현에 대해 asymptotically하게 같다.
우리는 Prim의 알고리즘의 asymptotic running time을 Fibonacci heaps를 사용하여 개선시킬 수 있다. Chapter 19는 만약 Fibonacci heap이 |V|개의 원소를 가지고 있다면, EXTRACT-MIN 연산이 O(lgV) amortized time이 걸리고, DECREASE-KEY 연산(LINE 11에서 구현한)이 O(1) amortized time이 걸린다는 것을 보여준다. 그러므로, 만약 우리가 min-priority queue Q를 구현하기 위해 Fibonacci heap을 사용한다면, Prim의 알고리즘의 작동 시간은 O(E + VlgV)로 개선된다.
댓글 없음:
댓글 쓰기