알고리즘 ch8 Greedy algotithm

Optimization Problem

- 여러개의 가능한 답 중에 가장 최적의 답 또는 최적의 답과 가까운 답을 고르는  문제

- 비용을 최소화 한다거나 이익을 최대화 하는 답을 고르는 문제

Greedy Algorithm

- 최적해를 구하는 데에 사용되는 근사적인 방법. 

- 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.

  (미래를 생각하지 않고 각 단계에서 최선의 선택을 함)

Optimization problem 중 greedy 방법을 사용하는 문제

1. Minimum Spanning Tree (MST)

 - Spanning tree 중 사용된 간선들의 가중치 합이 최소인 트리

  즉, 그래프 내에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결하는 트리

+ Spanning Tree 신장트리 : connected, acyclic, undirected

    그래프 내에 모든 정점을 포함하는 트리로 그래프의 최소 연결(간선) 부분 그래프이다. 

     최소 연결이란 간선의 수가 가장 적다는 뜻

 - MST 구현 알고리즘 2개 -> greedy algorithm 사용

   1) Prim’s algorithm

: 시작 정점에서부터 출발하여 MST를 확대해가는 방식

 (정점 선택 방식, 이전 단계에서 만들어진 신장트리를 확장하는 방법)

 Vertex를 3개의 상태로 나눈다.

1) Tree vertex : MST에 속한 vertex

2) fringe vertex : tree vertex의 후보

3) Unseen vertex : Tree, fringe를 제외한 나머지 vertex

구현 순서

(1)   시작 단계에서는 시작 정점(starting vertex)만이 MST(최소 비용 신장 트리) 집합에 포함된다.

     (시작 정점은 임의로 결정)

(2)   앞 단계에서 만들어진 MST 집합에 인접한 정점들(Fringe vertex) 중에서 최소 가중치 간선으로 연결된 정점을 선택하여 트리를 확장한다. 

이미 트리에 포함된 정점(Tree vertex)에 연결된 간선이면 pass

(가장 낮은 가중치를 먼저 선택한다.) -> greedy

(3)   앞의 과정을 트리가 N-1개의 간선을 가질 때까지 반복한다.

        -> 알고리즘이 종료됐을 때 만들어진 트리가 MST

자세한 의사코드

n이 vertex수, m이 edge 수일때

Insert() +  removeMin()(=getMin()+DeleteMin()) + decreaseKey()

unsorted sequence로 구현시 :  O(n^2)+ O(m) = O(n^2)

binary heap으로 구현시 : O(nlogn)+ O(mlogn) = O(mlogn)

+ decreaseKey()는 간선 가중치 업데이트 하는 함수

   2) Kruskal’s algorithm

: 가중치가 작은 간선부터 선택하여 MST를 구한다.

(간선 선택 방식, 이전 단계에서 만들어진 신장 트리랑 상관없이 무조건 최소 간선만 선택)

 구현 순서

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

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

즉, 가장 낮은 가중치를 먼저 선택한다. ->greedy

사이클을 형성하는 간선을 제외.

(3)   해당 간선의 두 정점이 연결되어 있지 않다면 현재의 MST(최소 비용 신장 트리)의 집합에 추가한다.

 

 사이클 생성하는지 확인하고, 안 생성할 경우 정점을 연결하는 작업은

 Union-find 연산을 이용

+Union-find 연산 : Kruskal 알고리즘 말고도 널리 사용되는 연산

  - Union(u,v) : 원소 u와 v가 속해있는 집합을 입력받아, 두 집합을 합쳐주는 연산

  - Find(u) : 원소 u가 속해있는 집합을 반환해주는 연산

의사코드

n이 vertex수, m이 edge, 

Union할때 A weighted Union heuristic 방법사용 -> 원소개수가 큰쪽에 작은쪽을 흡수시키는 방법, 하나의 vertex가 update될 횟수를 줄이기위해

heap 구현

Make_set()  = O(n)

sort = O(mlogm)

Find() = O(m)

Union() = O(1) * 2 + O(n) * O(logn) = O(nlogn)

=> O(mlogm) => m<=n^2이므로 logm <=2logn 따라서 O(mlogn)

2. Single source shortest path = Single pair shortest path

 - 특정한 vertex 사이의 최단 경로를 찾는 문제

최단경로 shortest path =  minimum weight paths

 - shortest path property : 최단 경로를 이루는 부분 거리도 최단 경로이다.

x,y,z의 vertex가 있다고 하자.

x -> ,,, ->y -> ,,,->z 로 가는 path가 있을때 이 path가 shortest path이면 x -> ,,, ->y 와 y -> ,,,->z  각각도 최단 경로다.

단, 역은 성립하지 않는다. x -> ,,, ->y 와 y -> ,,,->z  각각이 최단 경로라고 x -> ,,, ->y -> ,,,->z 가 최단경로임을 보장할 수 없다.

 - Dijkstra Algorithm : 하나의 정점에서 다른 정점들 사이의 최단 경로를 구하는 알고리즘

 

                              Edge가 음수 가중치를 가질 경우 사용 불가능 하다.

   의사코드

  

 인접행렬로 구현시 O(n^2)

 heap으로 구현시 O(mlogm) => m ≤ n^2이므로 O(mlogn)

3. All pairs shortest path

 - Floyd-Warshall Algorithm : 모든 정점끼리의 최단경로를 구하는 알고리즘, 음수가중치에서도 사용가능

단순히 반복문 3개를 돌기때문에 O(n^3) 시간복잡도, O(n^2) 공간복잡도

 - Dijkstra로 All pairs 구현시 O(nmlogn) time