[자료구조 및 알고리즘] #18 - Greedy Algorithms

0.

 

2024.06.09 - [학교 수업/자료구조 및 알고리즘] - 자료구조 및 알고리즘 #14 - Union-Find (Disjoint Set) and an Application

자료구조 및 알고리즘 #14 - Union-Find (Disjoint Set) and an Application

위 글에서 Greedy Algorithms인 Kruskal algorithms을 통해 MST를 구하는 문제를 본 적이 있습니다.

 

1. Greedy algorithms

 

탐욕 알고리즘 또는 그리디 알고리즘(* Greedy algoritm)은 최적의 해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 알고리즘을 말합니다.

 

출처: https://ko.wikipedia.org/wiki/%ED%83%90%EC%9A%95_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

탐욕 알고리즘 - 위키백과, 우리 모두의 백과사전

 

순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없습니다. 그렇기 때문에 그리디 알고리즘을 사용할 때는 정확성의 검증이 매우 중요합니다.

 

이 글에서는 MST(* Minimum Spanning Tree)를 찾는 알고리즘으로 그리디 알고리즘으로 알려진 Prim algoritm을 사용하고 증명해보겠습니다.

 

2. Prim algoritm

 

Prim 알고리즘은 매 순간 최선의 조건을 선택하는 그리디 알고리즘을 바탕에 두는 알고리즘입니다. 즉, 탐색 정점에 대해 연결된 인접 정점들 중 비용이 가장 적은 간선으로 연결된 정점을 선택하는 방식입니다.

 

정확한 단계는 아래와 같습니다:

1. 시작 단계는 시작 노드만이 MST집합에 속한다.
2. 트리 집합에 속한 정점들과 인접한 정점들 중 가장 낮은 가중치의 간선과 연결된 정점에 대해 간선과 정점을 MST트리 집합에 넣는다. 만약 그 간선이나 정점이 사이클을 만든다면 그 다음 순서에 해당하는 간선과 정점을 넣는다.
3. 2번 과정을 MST집합 원소 개수가 그래프의 정점 개수가 될 때까지 반복한다.

 

초기 상태

 

위 예시에서 시작 노드를 A라고 하고 Prim 알고리즘을 수행했을 때, 다음과 같은 과정을 거칩니다:

 

#1

 

A와 인접한 노드 B,C 중 C가 가장 가중치가 낮은 간선으로 연결되어 있으니 C를 집합에 넣고 비용에 AC의 가중치를 더합니다. 이때 가중치의 최소값을 구할 때는 PQ를 사용합니다.

PQ:

2024.06.02 - [학교 수업/자료구조 및 알고리즘] - 자료구조 및 알고리즘 #12 - an Application of Heap and Priority Queue

자료구조 및 알고리즘 #12 - an Application of Heap and Priority Queue

 

#2

 

AC와 인접한 노드들 중 가장 낮은 가중치로 연결된 정점은 B이기 때문에, 집합에 B를 넣고 CB가중치를 더합니다.

이렇게 계속 반복하면 됩니다.

#3

#4

#5

 

 

A,C,B,D,E와 인접한 노드들 중 가장 낮은 가중치로 연결된 정점 F를 집합에 넣고 DF 가중치를 더합니다. 트리의 집합에 속한 원소의 개수가 N(* 6개)이 되었으므로 탐색을 중단합니다.

탐색 결과 최소 신장 트리 구축의 비용은 13으로 확인되었습니다.

 

이를 다시 sudo code로 정리하면 다음과 같습니다:

T <- Empty set(* set of MST edges)
U <- {1}(* set of MST nodes, 1 is start node)
while U != V(* V is set of G nodes):
    U와 V-U를 연결하는 edge들 중 가중치가 최소인 edge를 uv라고 하자
    T <- uv
    U <- uv의 노드들

 

3. Correctness of Prim Algorithm

 

우선 MST가 존재하는 그래프 G가 있다고 하고, 그 MST를 Tmst라고 합니다.

또한 Prim Algoritm으로 얻을 트리를 T라고 한다면, 알고리즘을 진행하면서 만들어질 트리 T가 Tmst와 같아진다면,

Prim Algoritm의 정확성은 증명됩니다.

 

만약 T와 Tmst가 다르다고 가정했을 때, 모순이 발생하면 위 명제가 참입니다.(* 귀류법)

 

 

다음과 같은 그래프가 주어지고 Tmst는 (f)단계에서의 결과로 얻어진 트리입니다.

T

 

c단계, 즉 정점 0,5,4,3을 연결하는 것까지는 Tmst와 T가 똑같지만, Tmst와 다르게 T에서는 2가 아닌 6을 연결했다고 가정합니다.(* 귀류법 가정)

 

이때 36간선을 e라고 하고, 정답인 Tmst에서 e를 추가했을 때(* Tmst + {e}) 사이클이 만들어지는 간선들 중 c단계에서의 정답 간선 집합과 아직 도달하지 못한 간선 집합을 연결하는 Tmst의 간선을 e'이라고 하면(* 위 예시에서는 32간선)

 

3가지의 경우의 수가 나옵니다(* w(e)는 e의 가중치를 의미합니다.):

1. w(e) < w(e'): 그렇다면 Tmst에서 e대신 e'을 선택할 이유가 없습니다. 즉 Tmst보다 T가 더 낮은 가중치 합을 가지는 MST가 됩니다. 따라서 Prim 알고리즘을 수행해서 나온 결과 트리 T가 정답 트리인 Tmst보다 더 좋습니다. 모순입니다.
2. w(e) = w(e'): 그럴 수 있습니다. MST가 여러 개 있을 수 있고, T와 Tmst모두 정답이 됩니다. 즉 Prim 알고리즘이 틀리지 않았습니다.
3. w(e) > w(e'): 그럴 수 없습니다. 만약 Prim 알고리즘을 정확히 수행했다면 e와 e'중 가중치가 낮은 값을 선택했을 것이고, 그 선택의 결과가 e이므로, w(e) < w(e')입니다. 즉 모순입니다.

즉 3가지의 경우의 수 모두 모순이 발생하므로 귀류법의 가정은 거짓 명제이고, 따라서 Prim 알고리즘의 정확성이 증명됩니다.

 

4. Time complexity

 

노드 개수 N, 간선 개수 M이라고 할 때, 그래프를 만드는데에 O(N+M),

각 간선을 기준으로 했을 때, 각 간선은 PQ에 최대 두 번씩 들어가게 됩니다.

(* 노드들을 기준으로 알고리즘이 수행되고, 간선 하나에 노드는 두 개이니까, 중복을 허용한다면 두 번, 허용하지 않는다면 한 번만 PQ에 들어가게 됩니다.)

PQ에서 최소값을 구하는데에 logM이 소모되므로

 

결과적으로 O(M + N + 2MlogM) = O(N + M + MlogM)입니다.

(* 만약 PQ의 내용을 수정할 수 있는 피보나치 PQ같은 경우는 logN에 PQ를 수행할 수 있습니다. 새로운 노드에 대해 수행할 때마다 모든 간선을 전부 다시 넣을 필요없이 수정하면 되니까...)

 

배움

 

Amortization? 노드를 기준으로 시간 복잡도를 계산할 수 없는 이유