Greedy Algorithm(프림/크루스칼/다익스트라)

1. Optimization Problems : 최적해 문제

-> 최적해 문제란, 총 비용을 최소화하거나, 총 이익을 최대화 하는 등의 특정한 목적을 갖고 있다.

- 가능한 모든 값을 분석해 가장 좋은 것을 고르거나, 매번 선택을 할때 가장 최적의 결과를 낳는 일련의 선택을 하게 된다.

 

2. Greedy Algorithm

: 탐욕 알고리즘은 최적해 문제를 해결하는 여러가지 방법 중 하나로, 선택 당시에 가장 좋아보이는 방법을 고른다.

"매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"라는 모토를 갖고 있다.

-> 따라서, 이를 결정하는 일정한 기준이 존재해야 한다.

: 어떤 것을 고를지는 오랜 시간이 걸려서는 안되며, 이를 계산하는데 너무 많은 비용이 들어서도 안된다.

EX) 갈림길에서 어느 길로 갈지 고민할때, 그 순간 가장 덜 막히는 길을 택한다.

 

-> 이 방식이 매번 통하는 것은 아니며, 외려 비용이 많이 들수도 있지만 몇몇의 문제를 효율적으로 해결할 수 있다.

 

 

3. Graph Optimization Problems 

: Greedy Algorithm으로 해결할 수 있는 그래프 최적화 문제가 존재한다.

1) 모든 정점을 최소 비용으로 연결하는 방법 : Minimum Spanning Tree

2) 두 정점 사이의 최소 거리 : Single-Source Shortest Paths Algorithm

 

4. Minimum Spanning Tree (최소 신장 트리)

1) Spanning Tree

- Spanning Tree는 G의 Subgraph이고, G에 존재하는 모든 vertice를 갖고 있으며 connected, Acyclic한 상태이다.

 

2) Minimum Spanning Tree

: 최소의 가중치합을 갖는 Spanning Tree를 의미한다.

-> Spanning Tree는 여러 형태로 존재할 수 있지만, 이 중에서 최소 비용합을 갖는 그래프를 찾아야 한다.

: 이를 찾는 두가지 알고리즘이 존재한다. Prim Algorithm & Kruskal Algorithm

 

5. Prim's Algorithm

: Tree Size를 하나씩 키워나가는 알고리즘으로, N번째 단계에선 N개짜리 Tree가 만들어진다.

 

- Prim Algorithm Strategy

1) 임의의 정점을 선택하여 비어있는 Tree에 포함시킨다.

2) 이 정점과 연결되어있는 정점들의 거리를 업데이트 한다. ( 가장 최소 비용이 드는 거리를 선택)

-> 즉, 각 Fringe Set의 정점들은 인접한 Tree Set과의 거리중 가장 짧은 거리를 고른다.

-> G에 인접한 Tree Set이 두개인 경우에 B-G, A-G 에서 어떤 간선을 고를지 결정해야 한다. BG=6, AG=3 이므로 G로 연결되는 간선은 A가 된다.

 

 

 

 

3) 선택된 정점들과 연결되어있는 간선들 중에서, 가장 짧은 길이의 간선을 선택해서 연결시킨다.

4) 선택된 간선 반대편의 정점을 Tree Set로 편입한다. 

 

- Vertice's Classification

 1) Tree vertice : 이미 Tree로 편입된 vertice

 2) Fringe Vertice : Tree에 들어가지는 않았지만, 이미 Tree Set에 포함된 정점들과 인접한 정점

 3) Unseen Vertice : 그 외의 Vertices

 

- Pseudocode

: 모든 Step의 개수는 Tree의 개수가 1개씩 증가하므로 O(n)시간이 걸린다.

-> 여기서 Fringe Set을 어떻게 관리하느냐에 따라서 시간 복잡도가 달라진다.

1) Fringe Set를 Unsorted Array로 관리할때 : 모든 정점들을 탐색해봐야 하므로 minimum V를 고르는데 O(n)이 걸린다.

=> 따라서 각 Step별로 O(n), 결과적으로 O(n^2+m) = O(n^2) 이 걸린다. (m은 초기화시간, m<n^2)

 

2) Fringe Set를 Priroity Queue로 관리할 때

: Min Heap을 구현해 넣으면 매번 최소 간선을 가진 vertex을 고르는데 O(logn)시간이 걸린다.

: 가중치를 기준으로 하여 가장 작은 가중치를 갖는 Fringe set의 vertex를 선택한다.

=> 따라서 각 Step별로 O(logn), 결과적으로 O(nlogn)시간이 걸리게 된다. (엄밀히 말하자면 O(ElogV))

 

 

 

6. Kruskal's Algorithm

: 프림 알고리즘에서는 단계별로 노드들을 Tree안으로 편입했으나, 크루스칼 알고리즘에서는 모든 노드를 각각 하나의 Tree로 만든다. 이때, N개의 Tree를 한번에 한개씩 Merge한다. 

=> 따라서, Tree의 개수는 줄지만, Size는 커지고, 모든 Tree가 하나가 되면 종료한다.

: 어떤 정점을 통합할지 Edge를 선택할때 Tree가 아닌 Cycle을 만들면 이 Edge는 선택하지 않는다. (따라서 이미 path가 존재하면 선택하지 않음)

 

- Strategy

1) 그래프의 간선들을 가중치의 오름차순으로 정렬한다

2) 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택한다

 : 가장 낮은 가중치를 선택하며, 사이클을 형성하는 간선은 제외한다

3) 해당 간선을 현재의 MST 집합에 추가한다. -> 따라서 Tree가 merge되며 하나 줄어들게 된다.

 

Q) 그래서 간선이 사이클을 형성하는지 어떻게 판별할 수 있나?

-> 이는 Union-find 알고리즘으로 알아낼수 있다.

- Edge가 Distinct tree를 연결하면 이를 선택하는 방식을 사용하는데, 이를 위해서 disjoint set의 모음을 유지하는 자료구조가 필요하다. Union-Find는 두가지 operation을 갖고 있다.

 

1) Find(u) : u를 갖고 있는 set의 setid를 return한다

2) Union(u,v): u,v가 속한 집합이 다를때 합집합시키는 연산. 이를 통해 tree를 merge하게 된다.

=> 계속 find/union 연산을 계속하면서 MST를 만들어 갈 수 있다.

 

-Kruskal Algorithm의 시간 복잡도

: 어떻게 구현했냐에 따라서 Union, Find 연산의 시간 복잡도가 달라진다.

-> Doubly linked list을 이용해 Set을 표현할 수도 있다. 

: 이때 Head node를 SetID로 하고, 두 set을 union할때 다른 list를 뒤에 연결하면 된다.

 

Q) 그렇다면, 두 리스트를 연결할때 어떤 list는 그대로 두고, 어떤 list를 뒤로 연결해야 더 효율적일까?

A) 이를 해결하는 것을 Weighted Union Heuristic이라고 하며, 크기가 작은 list를 뒤에 붙여야 Setid를 바꾸는 시간이 줄어든다. 두 리스트의 총 원소 개수가 n이라면 , 둘을 합치는 시간은 n/2시간을 넘지 않는다.

 

: 원래는 탐색 연산 시에 구조를 변화시키진 않으나, 이 구현은 효율성을 위해 find를 호출하면서 구조를 변경할 수도 있다.

: 또, 원래는 merge시에 link만 연결하고 setid를 바꾸지 않는다. 이러면 Union은 O(1)에 끝나지만, find시에 head까지 가야 하는 경우가 생겨 오래 걸린다. 따라서 head로 link를 direct하게 연결하면 find 또한 O(1)에 가능하다.

 

 

 

크루스칼 알고리즘의 시간복잡도:  모든 간선을 정렬하는 시간+union&find하는 시간 = O(mlogm)에 가능하다. 

-> union&find는 어떻게 구현하든 mlogm보다 작으므로 시간 복잡도에 고려하지 않아도 된다.

여기서, m은 최대 n^2이므로 O(mlogn^2)=O(2mlogn)=O(mlogn)이라고 해도 무방하다.

(m은 edge개수, n은 vertex 개수)

 

 

- Correctness of Kruskal Algorithm

: 만약 vertex u-v를 연결할때 Kruskal Alg.이 선택한 edge가 MST를 만들수 없다고 가정하자. 이후에 간선을 연결해가면서 u-v를 많은 정점을 거쳐서 연결하게 되었다고 했을때, 이후에 선택된 Edge가 절대 원래의 edge보다 작을 수가 없다.

 

 

 

Q) Prim Algorithm이 빠른가, Kruskal Algorithm이 빠른가?

1) Prim Algorithm : PQ를 Unsorted Array로 구현하면 매 step에서 최솟값을 구하기 위해 최대 n개가 들어갈수 있는 fringe set을 모두 탐색해야 하기 때문에 W(n)=O(n^2) 이다.

-> PQ에 노드를 insert할때 O(1), fringe-tree를 연결하고, 업데이트 하는데 O(1) : 무시.

 

2) Kruskal algorithm: O(mlogn)

 

=> 뭐가 더 좋은지는 그래프가 어떻게 생겼는지에 따라서 다르다.

1) Dense한 그래프일때(edge가 많은 그래프) m이 최대 n^2까지 들어갈 수 있으므로, n^2logn이 되어 Kruskal이 불리하다.

2) Sparse한 그래프일때는 : 대체로 kruskal이 유리하나(m<n일 때), sparse한 그래프는 fringe set를 만들때 탐색하는 간선도 줄어드므로 이 경우에도 Prim Algorithm이 빠를 수도 있다. (어쩌라고...)

 

 

7. Dijkstra's Shortest-Path Algorithm

- Problem

: 두 특정 vertices 사이의 shortest path를 찾아라.

-> 최악의 경우에는 1:1 사이의 path를 찾는데 1:n보다 오래 걸릴 수도 있다. 따라서 그냥 1:n 문제를 풀게 된다

 

+) SRC: DST 의 비에 따라서 어떤 문제를 풀어야 하는지가 다르다.

1) 1:1 -> s,t사이의 최단 경로를 알고 싶어함

2) 1:n -> s와 다른 모든 정점 사이의 최단 경로를 알고 싶어함

3) n:n  -> 각각의 pair에 대해 shortest path를 모두 찾아야 한다. (all pairs shortest path problem)

 

 

-Shortest path의 정의

1) P는 nonempty path이며, k개 edge로 이루어져있고, vertex x,y사이가 이어져 있어야 한다. (XV1,V1V2,V2V3,...,Vk-1Y)

2) W(p)=W(XV1)+W(V1V2)+W(V2V3)+..+W(Vk-1Y) -> P를 구성하는 각 간선들의 Weight Sum이 최소여야 한다.

3) x=y일때, 이를 empty path라고 하고, empty path의 weight는 0이다. 

 

 

- Lemma : Shortest Path Property (보조정리)

-> 만약 xz가 shortest path라면, xz를 구성하는 path xy,yz는 각각 모두 shortest path이다.

- 귀류법으로 증명)

ㄱp 혹은 ㄱq라고 가정해보자. p가 shortest path가 아니라면 다른 path인 p'가 shortest path이고, W(p)>W(p') 이다. 그리고 pq를 잇는 결과인 r은 shortest path라고 가정했을때, W(R)=W(p)+W(q)인데, 이보다 작은 W(p')+W(q)가 존재한다면 W(R)는 shortest path 가 아니게 된다. 

 

- Pseudocode/ Strategy

 

1) 모든 정점들을 초기화한다.

2) 출발할 한 정점을 선택한다.

3) 해당 정점과 인접한 모든 정점을 fringe set으로 고른다.

4) fringe vetice들을 처리한다.

  - tree set의 vertice T, fringe set의 vertex V에 대해서 (D(s,t)+W(tv))가 최소인 edge를 고른다.

  : 즉 이제까지의 tree set의 shortest path+ tree set-fringe set간의 거리 합이 최소인 edge를 골라야 함

 - 해당 fringe set vertex V를 tree로 편입시키고, D(s,v)를 D(s,t)+W(tv)로 update한다.

: ( 만약 두 길이가 같으면 알파벳 순서로 편입한다.)

 - 모든 V에 인접한 unseen vertices들을 fringe set로 추가한다.

 

+) 각 vertex에 대한 시간 복잡도

  1) min vertex 찾기: O(n)+ 2) Tree로 편입: O(1)+ 3) V.incidentEdges: O(degV) (각 vertex의 tree,unseen,fringe를 결정하는데 모두 O(1)이 걸림) -> 따라서 모든 과정은 O(n^2+m)=O(n^2) 만큼 걸리게 된다.

 

 

- Correctness

만약 s,y의 shortest distance가 d(s,y)라고 가정했을때, 만약 yz가 y에 존재하는 모든 edge와 vertex z사이의 거리를 최소화하는데 선택되었다고 가정하자. (d(s,y)+W(yz))

-> 그렇다면 모든 s-y사이의 shortest path를 구성하는 path는 s-z까지의 shortest path에 반드시 포함된다.

: 따라서, 다익스트라 알고리즘은 계속해서 shortest path를 구성해나가고 있다고 볼 수 있다.

 

+) 증명은 매우 복잡하나 간단하게 얘기하면, tree set에 s,t,y가 존재하고, fringe set에 x,y가 존재한다고 할때 s-t-x와 s-y-z 사이에서 s-y-z가 결정되었다는 것은 d(s,t)+w(t,x)>=d(s,y)+w(y,z)임을 의미한다. 따라서 나중에 어떻게 돌아와서 s->t->x,,,->z로 연결되었다고 해도 s->y->z보다 무조건 클 수 밖에 없다.