Greedy Algorithm

답을 찾기 위해 선택을 반복하는 알고리즘들 중
비교적(?) 간단한 방법으로 선택하고
선택한 후 바꾸지 않는 알고리즘

Greedy Algorithm의 예시

Shortest path

언제나 성립하지는 않지만, 종종 사용할 수 있다. B에서 출발할지를 프로그램으로 짜는건 쉽지 않음!

Selection Sort

int sort(int a[], int n)  
{
    int i, j, m, t;  
    for (i = 0; i < n; i++)   
    {  
        // find min  
        m = i;  
        for(j = i; j < n; j++) if(a[m] > a[j]) m = i;  
        t = a[i];  
        a[i] = a[m];  
        a[m] = t;  
    }  
}  

selection sort도 greedy라 볼 수 있다. 전체를 살펴보고 제일 작은 것(a[m])을 찾는 거니까..!

참고로 어떤 알고리즘이 greedy다 아니다 판단하는건 blurry하다.

Minumum Spanning Tree

정의: 입력으로 graph가 주어졌을 때, edge의 subset을 골라 edge weight들의 합이 minimum이 되는 tree. (tree의 정의: connected acyclic graph. 연결돼있고 cycle이 없는 graph)

n개의 node를 가지는 tree는 edge가 n-1개니까 위의 예시에서처럼 node가 5개일 때는 edge 네 개가 된다.

Proof

수학적 귀납법으로 증명해보자.

base case: node가 하나일 때는 edge가 0개
step: node의 개수 n이 n=k-1일 때 edge의 개수 e가 e=k-2이면, n=k일 때 e=k-1을 보이면 된다.

tree가 connected acyclic graph이기 때문에 degree가 1인 노드가 있다는 것을 알 수 있다. (모든 node의 degree가 전부 2 이상이라 생각하면 한 node에 들어오면 항상 다른 node로 나갈 수 있다. 그러면 같은 node로 들어오게 되고 cycle이 만들어짐)

n=k인 node가 있으면 거기서 degree가 1인 node를 제거해보자. 그럼 n=k-1, edge=k-2이고 이 graph는 여전히 connected하며 acyclic하므로 여전히 tree이다. 여기서 아까 제거한 degree 1짜리 node를 다시 넣으면 node가 n개, edge가 k-1개인 tree가 만들어짐.

Prim Algorithm

Idea

하나의 node를 가진 tree에서 시작
tree에 인접한 edge들 중에서 가장 작은 weight를 가진 edge를 추가 (단, cycle을 만들지 않아야 함)
spanning tree가 될 때까지 반복

정확성

greedy가 정확하다는 걸 증명하는 standard한 방법이 있다. 근데 이 방법은 답이 여러 개 있을 때 어렵다. (mst도 해당됨)

우선 minimum spanning tree 중에 하나를 Tmst라 하고, Prim algorithm이 작동하는 매 step마다 보자. (이게 greedy가 맞다는 걸 보이는 standard한 방법이다!)

Tmst를 벗어나느냐 아니냐를 볼거임!

우선 아무 node나 하나 고른다. 이 node는 Tmst 내의 노드이므로 성립.
그 다음 weight가 가장 작은 edge를 고른다.
이걸 계속 반복하다가 정답에 없는 edge를 고르고, 이 edge를 e1이라고 하자.
이 graph는 이제 Tmst와는 모순이 되므로 Tmst를 만들 수 없다. 그렇지만 Tmst가 아닌 다른 mst를 만들 수도 있으니까 계속해보자.

이때 T’mst라는 tree가 있다고 하면, 지금까지 Prim algorithm이 만든 tree가 다른

Tsmt U {e1}를 하자. tree에다가 edge를 하나 추가했으므로 e1을 포함하는 cycle이 생기고 그러면 이 cycle 안에 이번 round에서 고려 대상이었던 다른 edge가 있다.
이때 tree에 없는 node에서 출발해 cycle을 거꾸로 돌면 반드시 tree에 들어있는 node를 만나게 된다. 이를 e2라고 하자.
e1의 weight과 e2의 weight를 비교해보자.
- w(e1) > w(e2)
  - Prim algorithm은 weight가 가장 작은 edge를 택하기 때문에 weight가 더 큰 e1을 골랐으면 안된다.
  - 따라서 Prim algorithm에 모순
- w(e1) < w(e2)
  - (Tmst - {e2}) U {e1}을 하면 정답보다 weight가 더 작아잔다.
  - 따라서 Tmst가 정답이라는 것에 모순
- w(e1) = w(e2)
  - (Tmst - {e2}) U {e1} = T’mst
  - 이 graph도 minimum spanning tree이다!

구현 및 성능

node들의 list를 만들고 tree에 들어있는 node index의 값을 1로 표시
edge는 e1=(a, b)는 표현할 수 있는데, cycle을 만들면 안되므로 a, b 둘 중 하나의 값은 0이어야 한다.
매 round마다 모든 edge를 살펴보면서 (1, 0)인 edge를 고르는데, 이렇게 하면 시간이 너무 오래 걸린다.
Prim algorithm은 n-1번의 round를 보기 때문에 이 때마다 edge m개를 보기 때문에 거의 O(Mn)정도의 성능을 보일 것이다. (너무 오래 걸림)

Algorithm Prim (G, T) // G: 입력 graph(adjacency list. matrix면 n^2가 되니까) T: 출력(edge set)
    T <- empty set // array로 구현하면 됨
    U <- {1} // tree에 들어있는 node들을 표현. 시작할 떄는 1번 node만 marking 되어있음
    U의 한 node (marked node)와 V-U의 한 node(unmarked node)를 있는 edge들 중 weight가 가장 작은 uv: pq/heap 쓰면 됨!
        이때 값이 1, 1인 노드는 버리고 0, 1 또는 1, 0인 노드만 선택한다. 
    uv를 T에 추가
    v를 U에 추가 (mark하기)

모든 edge가 pq에 두 번씩 들어갔다 나오게 되고, pq에서 한번 나올 때 logm만큼 걸리니까 전체를 보면 O(2mlogm)의 시간이 걸린다.
따라서 전체 성능은 O(n + mlogm)이 된다.

Kruskal Algorithm

Prim 알고리즘이 한 군데에서 퍼져나가는 방식이었다면 Kruskal은 그래프 전체를 보면서 남은 것 중 weight가 가장 작은 edge를 계속 추가한다.

Idea

Keep adding edges

from smaller weights
- sorting 하면 됨
as long as no cycle results
- Prim 알고리즘에서는 tree에 이미 들어있는 node끼리만 연결하지 않으면 cycle이 생기지 않았다.
- Kruskal에서는 edge를 추가함으로써 생기는 ‘덩어리’들 내의 node들을 연결하지 않으면 cycle이 생기지 않는다.
until n-1 edges are added

정확성

Prim 알고리즘처럼 정답 중 하나가 있다는 방식으로 증명한다.

정답 중의 하나를 Tmst라 하고, Kruskal 알고리즘이 edge를 추가하는 것을 Tmst와 계속 비교해 Tmst과 모순이 없는 edge를 추가하고 있으면 정답.

어느 순간 우리가 정답으로 잡지 않은 edge를 추가했다고 하고, 이 edge를 e라 부르자. Tmst U {e}, 즉 tree에다 edge를 하나 추가했으므로 cycle이 생기고 이 cycle은 e를 포함한다. cycle에는 e 말고도 Tmst에 있지만 알고리즘이 아직 추가하지 않은 edge들이 있다. 그 중 하나를 e’라 하자. e’은 서로 다른 덩어리를 연결한다.

e의 weight와 e’의 weight를 비교해보자.

w(e) > w(e’)
- 알고리즘에 의하면 weight가 작은 edge부터 추가해야 하니까 e’가 먼저 tree에 추가됐어야 한다. 따라서 알고리즘에 모순
w(e) < w(e’)
- (Tmst - {e}) U {e} –> 더 좋은 답!
w(e) = w(e’)
- (Tmst - {e’}) U [e} –> 이것도 정답이다!

구현 및 성능

Algorithm Kruskal(G, T)
	T <- empty set
	while |T| < n-1 do
		E에서 가장 작은 weight를 가진 edge 선택 // 처음에 sorting해놓으면 배열에서 순서대로 보기만 하면 됨 --> O(n logn)
		E = E - {e}
		if (V, T U{e})에 cycle이 없으면
			T <- T U {e} // Union-Find를 사용하면 거의 상수 시간안에 할 수 있다. 

성능

edge(a, b, w) (a, b는 node, w는 weight)들을 sort by weight 해놓자. 그리고 node a와 b가 같은 덩어리 안에 있는지 확인하면 된다. 확인하는 방법은 몇 가지가 있는데,

DFS로 확인하면 O(n+m)만큼의 시간이 걸린다.
Union-find를 사용하면 훨씬 더 빠른 시간 안에 확인할 수 있다.
- 덩어리마다 내장 node가 생기고, 특정 node에서 find(a)하면 대장(덩어리마다 대장이 하나씩 있음)의 번호가 나온다. find(a)와 find(b)가 같으면 같은 덩어리에 있다는 뜻

MST 문제의 solution의 수는 몇 개인가?

node와 edge가 같다고 해도 weight가 다르다면 답의 수가 달라질 수 있다.
–> 학부생 수준에서는 너무 어려우니, 답이 유일할 조건 중 충분 조건 중 하나만 알아보자.

weight가 모두 다르면 MST의 답이 유일하다.

(충분조건이라 했음. MST의 답이 유일하다고 해서 weight가 모두 다르다는 건 아님!)

Prim and Kruskal can find ANY solution

Some algorithms cannot find some of the possible solutions.
- Stable sort
  - (a, 2), (b, 3), (c, 1), (d, 2), (e, 3), (f, 2)을 숫자 순으로 정렬하자.
  - a, d, f는 숫자가 같으므로 아무 순서로 정렬해도 된다.
  - 그러나 stable sort는 같은 숫자가 있을 때 입력 순서를 유지해야 하므로 답을 (c, 1), (a, 2), (d, 2), (f, 2), (b, 3), (e, 3)만 만들어준다.
Prim and Kruskal can find any solution. 즉, 입력 그래프에서 나올 수 있는 모든 가능한 답을 다 찾아준다. 무슨 choice를 선택하느냐의 차이임.
Tmst를 무엇을 잡고 시작하던지 간에 Kruskal 알고리즘이 어떤 답이든 만들 수 있다.

Is that property important?

Yes, it can be used to show that if all weights are different there is exactly one solution to the MST problem.

Proof

Fix any solution Tmst
Show Prim can find THAT solution weight가 같은 경우에는 그 중 어떤 걸 먼저 넣을지 선택할 수 있다. 그러나 모든 weight가 다르면 알고리즘이 진행되는 동안 선택권이 없다. 즉 Kruskal 알고리즘은 유일한 답을 생성한다.

Greedy Algorithm