Graph optimization Problems and Greedy Algorithms

Optimimzation Problems

- 최소/최대 total cost 계산

- 모든 가능한 outcome을 계산해 최선의 것을 찾는다.

 

Greedy Algorithms

- “short term” criterion에 따라, 각각의 선택이 최선이 되게 함.

- 한번 결정되면 취소할 수 없음. 나중 가서 그게 나쁜 선택이었을지라도 어쩔 수 없음.

 

Graph Optimization Problems

- 몇몇 optimization 문제들은 greedy algorithm으로 해결할 수 있다.

- Minimum cost for connectiong all vertices - Minumum spanning tree 알고리즘 -> Prim, Kruskal

- Shortest Path between two vertices - Sigle-Source Shortest Path 알고리즘 -> Dijkstra

 

1.2 Minimum Spanning Tree (MST, 최소 신장 트리)

- undirected graph G=(V, E)에 대한 최소 신장 트리는 G의 모든 정점을 포함하는, G의 subgraph인 undirected tree(connected, acyclic, undirected)

 

- (a)의 spanning tree인 b, c, d 중 minimum인 것은 b, c

Prim’s Algorithm

- 무작위로 starting vertex (root)를 고른다

- 각 iteration마다 edge를 선택해서 트리에 연결한다.

- 선택되는 edge는 연결될 수 있는 edge들 중 weight이 가장 작은 edge. (Greedy)

- 과정 중에 정점들은 세 가지 카테고리로 나뉜다.

- Tree vertex: 트리에 포함된 정점

- Fringe vertex: 트리에는 없지만, 트리 안에 있는 어떤 정점과 adjacent인 정점

- Unseen vertex: 나머지들

 

- distance array, status array 만들어서 업데이트하는..

- 시간복잡도

	sorted sequence	unsorted sequence	binary heap
insert	O(n)	O(1)	O(logn)
removeMin	O(1)	O(n)	O(logn)
decreaseKey	O(n)	O(1)	O(logn)

1) unsorted sequnce: O(n2+m) -> m은 n2에 근사하므로 O(n2)

2) binary heap: O(nlogn+mlogn) -> O(mlogn)

 

Kruskal’s Algorithm

- Sorting 이용: O(mlogm) -> O(mlogn2) -> O(mlogn)

- 우선순위 큐(heap) 이용: O(mlogm) -> O(mlogn2) -> O(mlogn)

  // prim에서 heap 쓸 때랑 수행시간이 같다.

- Data Structure

- 이 알고리즘은 forest를 유지한다.

- 서로 다른 트리일 때만 edge를 추가한다.

- disjoint set (union-find ADT) 사용

- find(u): u를 포함하는 set을 리턴

- union(u, v): u를 포함하는 집합과 v를 포함하는 집합을 하나의 트리로 합침

- weight이 가장 작은 edge부터 시작, 그 edge가 잇는 두 vertex가 서로 다른 집합이면 union

- 그 뒤로 가장 작은 edge를 찾고 다르면 union... 반복

- 같은 집합인지 체크는 serid로 한다. (setid는 union할때 정함. 제일 작은 수로 한다든지..)

 

2. Single-Source Shortest Paths Problem

- 두 정점을 잇는 최소 weight path를 찾아라.

- Lemma: y를 지나는 x->z가 최단일 때, x->y path와 y->z path는 최단이다. (역은 성립하지 않는다.)

 

Dijkstra’s Shortest-Path Algorithm

- Greedy 알고리즘 사용.

- Weight은 음이 아니어야 함.

- 모든 정점을 unseen으로 두고, d(s,t)+W(tv)가 최소인 fringe 정점을 tree로 업데이트 하는 방식.

- 시간 복잡도

- unsorted array: O(n2)

- heap: O(mlogn)