😈 Greedy & Prims Algorithm (feat MST)

탐욕 알고리즘이란

• 답을 하나씩 고르는데
• 미리 정한 기준에 따라
• 매번 가장 좋아 보이는 답을 선택한다.

*동적 프로그래밍과 마찬가지로 최적화 문제를 푸는데 사용된다.

---

동적 계획법과 다른점

동적 계획법
 1. 재귀 관계식을 세워서
 2. 입력 사례를 더 작은 입력사례로 분할

탐욕법
 1. locally 최적의 경우 선택
 2. 적절성 검사
 3. 해답 점검

*전체적으로 최적인 해를 구하지만 항상 최적인 해를 얻는다는 보장이 없다.
--> 최적인 해답을 얻는지 확인하는 절차가 반드시 필요하다.

---

거스름 돈 문제

: 동전의 개수가 최소가 되도록 거스름돈을 주는 문제

1. 빈손으로 시작한다.
2. 액면가가 가장 높은 동전을 집어 손에 올린다. (선택과정)
3. 손에 있는 거스름 돈의 총액이 거슬러 주는 액수를 초과하는지 확인한다. (적절성 검사)
4. 액수를 초과하지 않으면 거스름돈에 포함한다. (해답점검)
5. 액수가 같은지 검사 한다. (해답점검)

while(동전이 남아있고 문제 미해결){
	가장 액면가 높은 동전을 집는다;				//선택과정
    if(동전을 더해 거슴돈 액수가 초과)			//적절성 검사
    	동전을 뺸다.
    else
    	거스름돈을 포함시킨다.
        
    if(거스름돈 총액 == 거슬러줘야하는 액수){		// 해답점검		
    	문제해결
    }
    

*선택과정 -> 적절성 검사 -> 해답 점검

 

---

최소비용 신장트리(MST)

예시) 모든 도시 사이를 연결하는 자동차 도로 건설 계획에서 도로의 길이의 총 길이가 최소여야하는 문제

• 가중치의 합이 최소가 되는 부분 그래프틑 꼭 트리가 된다. (순환경로가 없어야함)
• 신장트리 : 그래프의 마디를 모두 포함하면서 트리인 연결된 그래프
• 존재하는 신장트리를 모두 찾아보는 무작정 방법으로 최소 비용 신장 트리를 찾으면 최악의 경우 지수시간보다 나쁘다.

---

프림 알고리즘

1. 이음선의 F의 부분집합인 공집합과 임의의 마디를 포함하도록 초기화 된 마디의 부분집합에서 시작한다. Y={V1}
2. V2는 Y에서 가장 가까운걸 Y에 추가하고 이음선은 F에 추가한다.
   (같은 가중치가 두개이상 있으면 임의로 선택한다.)
3. Y=V가 될 때까지 반복한다.

프림 알고리즘 코드

// A Java program for Prim's Minimum Spanning Tree (MST) algorithm. 
// The program is for adjacency matrix representation of the graph 

import java.util.*; 
import java.lang.*; 
import java.io.*; 

class MST { 
	// Number of vertices in the graph 
	private static final int V = 5; 

	// A utility function to find the vertex with minimum key 
	// value, from the set of vertices not yet included in MST 
	int minKey(int key[], Boolean mstSet[]) 
	{ 
		// Initialize min value 
		int min = Integer.MAX_VALUE, min_index = -1; 

		for (int v = 0; v < V; v++) 
			if (mstSet[v] == false && key[v] < min) { 
				min = key[v]; 
				min_index = v; 
			} 

		return min_index; 
	} 

	// A utility function to print the constructed MST stored in 
	// parent[] 
	void printMST(int parent[], int graph[][]) 
	{ 
		System.out.println("Edge \tWeight"); 
		for (int i = 1; i < V; i++) 
			System.out.println(parent[i] + " - " + i + "\t" + graph[i][parent[i]]); 
	} 

	// Function to construct and print MST for a graph represented 
	// using adjacency matrix representation 
	void primMST(int graph[][]) 
	{ 
		// Array to store constructed MST 
		int parent[] = new int[V]; 

		// Key values used to pick minimum weight edge in cut 
		int key[] = new int[V]; 

		// To represent set of vertices included in MST 
		Boolean mstSet[] = new Boolean[V]; 

		// Initialize all keys as INFINITE 
		for (int i = 0; i < V; i++) { 
			key[i] = Integer.MAX_VALUE; 
			mstSet[i] = false; 
		} 

		// Always include first 1st vertex in MST. 
		key[0] = 0; // Make key 0 so that this vertex is 
		// picked as first vertex 
		parent[0] = -1; // First node is always root of MST 

		// The MST will have V vertices 
		for (int count = 0; count < V - 1; count++) { 
			// Pick thd minimum key vertex from the set of vertices 
			// not yet included in MST 
			int u = minKey(key, mstSet); 

			// Add the picked vertex to the MST Set 
			mstSet[u] = true; 

			// Update key value and parent index of the adjacent 
			// vertices of the picked vertex. Consider only those 
			// vertices which are not yet included in MST 
			for (int v = 0; v < V; v++) 

				// graph[u][v] is non zero only for adjacent vertices of m 
				// mstSet[v] is false for vertices not yet included in MST 
				// Update the key only if graph[u][v] is smaller than key[v] 
				if (graph[u][v] != 0 && mstSet[v] == false && graph[u][v] < key[v]) { 
					parent[v] = u; 
					key[v] = graph[u][v]; 
				} 
		} 

		// print the constructed MST 
		printMST(parent, graph); 
	} 

	public static void main(String[] args) 
	{ 
		/* Let us create the following graph 
		2 3 
		(0)--(1)--(2) 
		| / \ | 
		6| 8/ \5 |7 
		| /	 \ | 
		(3)-------(4) 
			9		 */
		MST t = new MST(); 
		int graph[][] = new int[][] { { 0, 2, 0, 6, 0 }, 
									{ 2, 0, 3, 8, 5 }, 
									{ 0, 3, 0, 0, 7 }, 
									{ 6, 8, 0, 0, 9 }, 
									{ 0, 5, 7, 9, 0 } }; 

		// Print the solution 
		t.primMST(graph); 
	} 
} 
// This code is contributed by Aakash Hasija 

 

---

프림 알고리즘 복잡도

최소 변 비용 자료 구조시간 복잡도 (총합)

인접 행렬, 검색	V^2
이진 힙(아래 의사코드를 보라.) 및 인접 리스트	O((V+E)logV)=ElogV
피보나치 힙 및 인접 리스트	E+Vlog V

 

---

프림 알고리즘이 MST 최적해를 주는지 증명

Lemma 4.1

무엇을 증명하는가: F는 promising 하면 Prims 에서 선택되는 추가적인 edge를 합쳐도 promising 하다.

• 만약 e가 F'에 있는 걸 선택했다면
  1. 당연히 F에 있는것도 subset이 되니 trivial 하다.
  2. 끝
• 만약 e가 F'에 없는 거라면
  1. F'에 새로운 e를 더한다 했을때 spanning tree는 cycle이 생긴다. 
  2. 이 cycle은 Y 와 V-Y 두 그릅을 연결하면서 생긴 cycle이다.
  3. 다시말해 이 두 그룹을 연결하는 다른 edge가 반드시 있다는 것이다.
  4. 이 edge를 e'라 할때 F'+{e}-{e'}는 cycle 이 제거가 된 spanning tree 가 된다.
  5. e는 최소 weight 이기 때문에 e <= e' 이다.
  6. 그래서 F'+{e}-{e'} 가 MST 여야 한다.
  7. 따라서 F+{e} 는 F'+{e}-{e'}의 부분집합니다.
  8. 다시말해 F는 Promising 하다.

본 증명

수학적 귀납법을 사용한다.

• 증명: 귀납법을 사용하여 while 루프가 매번 실행 후 집합 F가 promising 하다는 것을 증명한다.
• 귀납 기초: 공집합은 당연히 promising 하다.
• 귀납 가장: while 루프에서 어떤 주어진 반복이 이루어 진 후 그때까지 선택한 edge의 집합은 유망하다고 가정한다.
• 귀납 절차: F+{e}가 유망하다는 것을 보이면 된다.
  1. e는 다음 반복을 실행할 때 선택되는 이음선이다.
  2. e는 Y에 속산 어떤 vertex를 V-Y에 속한 어떤 verex와 연결하는 edge중에서 최소의 가중치를 가지고 있기 때문에 Lemma 4.1을 통해 promising 하다. 
  3. 귀납 증명에 의하여 edge의 최종 집합은 promising 하다. 그래서 이 집합은 MST 를 만족한다.

 

---