printf("hellow coding");

이번 포스트에서는 Branch and Bound(분기한정법) 기법에 대해서 다루도록 하겠습니다. 

분기한정법은 이전 포스트에서 다루었던 backtrackingr과 매우 유사하지만, backtracking이 존재할 수 있는 모든 알고리즘의 해를 찾는 방법이라면, branch and Bound기법은 마찬가지로 상태공간 트리를 구축하여 문제를 해결하지만, 궁극적으로 모든 가능한 해를 다 고려하여 최적의 해를 찾는다는 점이 큰 차이점이라 할 수 있겠습니다. 

Branch and Bound 기법은 크게 두가지 단계로 나뉩니다. 

1. 어떤 노드에 도달하였을 때, 해당 노드가 promising 한지 아닌지를 판단하기 위해 노드의 바운드를 계산하는 일 

2. 헌재 노드의 바운드가 이제까지 찾은 best solution보다 작다면, 그 노드는 non-Promising 하다 판단, pruning.

이러한 방법은 이전 벡트래킹 포스트에서 다루었던 0-1 Knapsack Problem의 문제와 매우 유사한 형태 입니다. 

다만 이전 포스트에서 다루었던것은 이러한 분기한정법을 깊이우선 탐색을 통해 Backtracking으로 해결하였다면, 이번 포스트에서는 Breadth-First-Search , Best-First Search 탐색 방법으로 분기한정법을 다루도록 하겠습니다.

이 방식은 분기한정법을 너비우선 탐색으로 진행한 방법입니다. 

말 그대로 루트노드를 먼저 검색하고, 다음level에 있는 모든 노드를 왼쪽에서 오른쪽순으로 검색한다음, 마찬가지로 다음 레벨에 대해서도 이와 같은 순서로 탐색을 진행하며 최적의 해를 찾아나가는 방식입니다. 그림을 통해 진행과정을 하나하나 알아보도록 하겠습니다. 

bound를 계산하는 방식은 이전 backtracking 포스트의 0-1 knapsack문제에서 다루었기 때문에 자세히 다루지 않겠습니다. 첫번째 루트노드 탐색에선, 현재가지 찾은 best solution이 0, bound값을 계산하였을 때 115의 값을 가집니다. 따라서 bests olution보다 bound값이 크므로 promising하다 판단하여 해당 노드를 queue에 삽입하고, 그 자식노드들에 대한 탐색을 진행합니다. 이와같은 연산을 Queue가 empty가 될 때까지 탐색을 진행합니다. 

이전 queue에 저장된 Node0을 Pop하고, 그 자식노드들에 대해서 탐색을 진행합니다. Node1, Node2는 각각 해당 레벨에 해당하는 item(1번 item)을 넣기로 한 경우와 넣지 않기로 한 경우를 표현한 것입니다. 먼저 물건을 넣기로 한 경우인 Node1의 profit은 40으로 현재까지 중에 가장 best solution입니다.  또한 각 노드의 bound값을 계산하면 각각 115, 82이고 이는 현재 best_solution인 40보다 큰 bound값이므로 모두 queue에 삽입합니다.

마찬가지로 이전 queue에 저장된 {Node0, Node1}을 모두 pop하여 그 자식노드들에 대해서 profit 값과 bound 값을 계산합니다. 계산결과 현재까지의 최적의 해는 Node3의 값인 70이며, Node6의 bound값은 60으로 현재까지의 최적의 값보다 bound값이 작으니 non-promising하다는 것을 알 수 있습니다. 따라서 Node6의 자식노드에 대해서는 더이상 탐색할 필요가 없으니 이를 제외한 나머지 노드들 만을 Queue에 삽입합니다. 

마지막 레벨탐색에서 Node15는 item4를 넣을경우 무게가 초과 되기때문에 non-promising하고 그 외 

Queue가 모두 빌 때까지 마찬가지로 연산을 진행하면 위와같이 best_solution이 90임을 알 수 있습니다.

이제 상태공간트리와 알고리즘의 흐름을 파악하였으니 이를 토대로 Breadth-First-Search 방식으로 수도코드를 작성해 보도록 하겠습니다. 재귀(recursive)로 구현하기에는 상당히 복잡하므로 queue를 이용하도록 하겠습니다

#include <iostream> //Breath-First Search with Branch and Bound #include <iostream> #include <queue> class node{ int level; int profit; int weight; }; int knapsack2(int n, int[] p, int[] w, int W){ queue<node> Q; node u,v ; int maxProfit; clear(Q); //큐를 빈 대기열로 초기화 v.level = 0 ; v.profit = 0; v. weigth=0; Q.push(v); while(!empty(Q)){ v = Q.pop(); u.level = v.level + 1; //take care of the left child: 현재아이템을 넣기로 한경우 u.weight = v.weight + w[u.level]; u.profit = v.profit + p[u.level]; if (u.weight <= W && u.profit > maxProfit) maxProfit = u.profit; if (bound(u) > maxProfit) Q.push(u); //take care of the right child ;현재 아이템을 넣지 않는경우 u.weight = v.weight; u.profit = v.profit; if(bound(u) > maxProfit) Q.push(u); } return maxProfit; } float bound(node u){ int j, k; int totWeight; float result ; if (u.weight>=W) return 0; else{ result = u.profit; j = u.level + 1; while(j<=n && totWeight + w[j] <= W){ totWeight = u.weight + w[j]; result += p[j]; j++; } k = j ; if(k <= n){ result += (W-totWeight)*(p[k]/w[k]); } return result; } }

이 방법은 최정의 해에 더 빨리 도달하기 위한 전략입니다. bound 값이 큰것이 더 좋은 결과값을 낼 확률이 높다는 것에 기반하여 너비우선 탐색과같이 순차적으로 검색하는 것이 아닌, 우선순위 큐를 사용하여 바운드 값이 큰 순서대로 탬색을 진행합니다.  그림을 통해서 동작방식을 살펴보도록 하겠습니다. 루트노드를 삽입하는 부분은 위에 그림과 겹치므로, level2 탐색부터 보겠습니다. 

우선 순위 큐에 의해서 큐에는 bound값이 큰것이 먼저 나올 수 있도록 정렬되어 있습니다. 이제까지의 bestsolution은 70이며, 다음에 탐색할 노드는 바운드 값이 가장 큰 Node3의 자식노드입니다. 

탐색결과 Node3의 자식노드인 Node5는 무게초과로 Non-promising, Node6는 bound값이 80으로 아직까진 현재 best_solution인 70보다는 값이 크므로 promising으로 판단하고 우선순위 큐에 넣어줍니다. 다음에 탐색할 노드는 bound값이 가장 큰 Node4의 자식노드입니다. 

Node4의 자식노드인 Node7을 검색한 결과, 현재까지의 bestSolution은 90으로 갱신됩니다. Node7의 bound는 90보다 크므로 큐에 삽입하고, Node8의 바운드값은 90보다 작으므로 non-Promising 하다 판단하여 큐에 넣지 않습니다. 

이런식으로 순차적으로 탐색을 진행하면, 최종적으로 큐에 남은 Node2, Node6는 best_solution보다 작은 bound값을 가지고 있으므로 non-Promising이라 판단, 따라서 더이상 그 자식노드들을 살펴보지 않고 그대로 탐색을 종료하게 됩니다.  딱 봐도 탐색 과정이 이전 너비우선 탐색기반 bound & branch법 보다 상당히 줄어든 것을 확인할 수 있습니다.

이와 같이 최고우선탐색 기법을 사용하면, 너비우선 탐색에 비해서 일반적으로 검색 성능이 좋아집니다. 

이제 동작방식을 확인하였으니 마찬가지로 수도코드를 작성해 보겠습니다. 

(sudo 코드가 아닌 실전 코드를 확인하고 싶으시다면 (여길 참조하시면 좋을 것 같습니다
-http://yimoyimo.tk/Dynamic,Branch-and-bound-Knapsack/#branch-and-bound--01-%EB%B0%B0%EB%82%AD%EC%B1%84%EC%9A%B0%EA%B8%B0-best--first-search)

#include <iostream> //Best-First Search with Branch and Bound #include <iostream> #include <queue> #include <vector> #include <stdlib.h> using namespace std; struct node{ int weight; int profit; int level; float bound; }; struct cmp{ bool operator() (node x, node y) { return y.bound > x.bound; } }; public int knapsack3(int n, int[] p, int[] w, int W) { priority_queue <node, vector<node>, cmp> PQ; node u, v; int maxProfit=0 ; clear(Q); v.level = 0; v.profit = 0; v.weight = 0 ; v.bound = bound(v) PQ.push(v); while(!PQ.empty()){ u.level = v.level+1; //take care of left child : item넣었을때 u.weight = v.weight + w[u.level]; u.profit = v.profit + p[u.level]; if(u.weight<=W && u.profit> maxProfit) maxProfit = u.profit; u.bound = bound(u); if(u.bound > maxProfit) PQ.push(u); //take careof right child: item넣지 않았을 떄 u.weight = v.weight; u.profit = v.profit; u.bound = bound(u); if(u.bound > maxProfit) PQ.push(u); } } #bound 함수부분, public float bound(node u){ int j,k ; int totWeight; float result ; if(u.weight >= W) return 0 else{ result = u.profit; j = u.level +1 ; totWeight = u.weight; while(j<=n && totWeight + w[j]<=W){ totWeight += w[j]; result += p[j]; j++; } k =j ; if(k<=n){ result += (W-totWeight)*(p[k]/w[k]); return result; } } }

The Traveling SalesPerson Problem (with BFS_B&B)

이제 마지막으로 TSP문제를 Best-First-Search 기반 Branch Bound방식으로 해결해 보겠습니다.

T.S.P문제는 다음과 같습니다.

• 외판원이 어느 한도시에서 출발하여, 다른 도시들을 각각 한번씩만 방문하고
  자기 도시로 돌아오는 가장 짧은 일주경로를 걸정하는 문제 
• 일반적으로 이 문제는 음이 아닌 가중치가 있는 방향성 그래프를 입력값으로 받는다
• 여러 개의 일주여행경로 중에서 길이가 최소가 되는 경로가 최적의 경로가 된다. 

이 문제를 분기한정법으로 해결하기 위해서는 먼저 

1. 상태공간트리의 노드가 어떤 식으로 표현이 되어야 하는가 정의 

2. 어떤 노드의 서브트리를 탐색했을 때 얻을 수 있는 최적의 bound값을 계산하는 방법 

이 두가지에 대해서 생각해야 합니다. 

먼저 상태공간트리가 어떤 식으로 정의 될 지 생각해보면 다음과 같습니다. 

아마도 뻗어나가는 경로를 표현할 수 있어야 하므로, level 1은 출발지, level2는 출발지에서 다음 노드 까지의 경로..

이런식으로 노드를 표현할 수 있을 겁니다. 이런 식으로 뻗어나가서 단말노드(leaf node)에 도달하게 되면 비로소 완전한 일주경로를 가지게 되는 것이죠 

따라서 우리는 단말노드에 있는 일주 경로를 모두 검사하여 그중에서 가장 길이가 짧은 일주경로를 찾으면 됩니다. 위 그림에서 만약 경로에 저장되어 있는 노드가 n-1개가 되면 더 이상 뻗어 나갈 필요가 없는데, 그 이유는 어차피 n번째 노드를 방문한다면 자연스럽게 처음의 노드로 회귀해야 때문입니다. 

이제 상태공간 트리를 생각해 보았으니 bound값을 계산할 수 있는 방법에 대해서 생각해 봅시다. 

상태 공간트리에서 k번째 레벨에 있는 노드들은 k+1번쨰 정점을 방문한 상태를 의미합니다. 

먼저 위 그림을 하나하나 해석해보겠습니다.

[1, ..., k]의 여행경로를 가진 노드의 한계치는 다음과 같이 계산할 수 있습니다.  

- A = V - ([1, .., K] 경로에 속한 모든 노드의 집합) -> 그림상으로 주황색 점선 안

- bound = [1,...,k] 경로의 총 가중치 합 _
 + v_k에서 A에 속한 정점으로 가는 것중 최소의 cost 값 

 + (시그마)vi를 제외한  정점들 중 (빨간색 박스안 정점들을 제외한 정점들 중) cost가 최소인 것들의 합

   (말이 상당히 애매하지만, 밑에서 그림과 설명하도록하겠습니다) 

글로 정의하였지만 아직 잘 와닿지 않을 수 있습니다. 

이 과정을 아래 예제를 통해서 확인해 보도록 하겠습니다. 

루트노드의 하한 구하는 방법:

어떤 일주경로라도, 각 정점을 최소한 한번은 떠나야 하므로, 각 정점을 떠나는 이음선의 cost 최소값의 합이 bound값이 됩니다. 즉 각각의 경우중 최소의 값만 다 더하면,  bound 값은 4 + 7 + 4 + 2+ 4 = 21 입니다. 

단, 여기서 주의할 점은 bound값은 "이러한 가중치를 가지는 경로가 존재 한다는 것"이 아니라 이보다 더 cost가 작은 경로가 존재할 수 없다는 의미를 가지는 것입니다. 그래서 하한(lower bound)라는 말을 사용하는 겁니다. 

이제 각 레벨별로 어떻게 알고리즘이 동작하는지 살펴보도록 하겠습니다. 

먼저 bound계산 알고리즘에 대한 좀더 자세한 이해를 위해 [1,2]를 선택했을 때의 bound값 계산과정을 살펴보도록 하겠습니다. 

이미 v2를 선택하였음으로, v1->v2의 비용은 이음선의 가중치인 14가 됩니다. 나머지는 앞서 설명한대로 구해보면 

- v2에서 A에 속한 값 중 가중치 중에 (7, 8, 7) 최소인값 : 7 

- v3에서 전체에서 v2를 제외한(4, 7, 16) 가중치 중 최소인 값 : 4 

- v4에서 전체에서 v2를 제외한(11, 9, 2) 가중치 중 최소인 값 : 2

- v5에서 전체에서 v2를 제외한(18, 17, 4) 가중치 중 최소인 값 : 4

- [1,2]노드의 bound값 : 31 

따라서 이런 방식으로 나머지 노드들에 대해서 계산을 해보면 다음과 같은 상태가 됩니다. 

마지막으로 한번더 노드 [1,2,3]을 선택한 경우의 bound값을 구해보도록 하겠습니다. 

이미 v2와 v3를 선택하였으므로 v1->v2->v3의 cost는 14 + 7 = 21이 됩니다.

나머지는 앞서 설명한 방법과 동일하게 계산해 보면 

- v1 ->  14

- v2 -> 7 

- v3 에서 A에 속한 값중 (7, 16)가중치가 최소인 값 : 7

- v4 에서 전체에서 v2, v3를 제외한 값중 (11,2) 가중치가 최소인 값 : 2

- v5 에서 전체에서 v2, v3를 제외한 값중 (18, 4) 가중치가 최소인 값: 4 '

- [1,2,3]노드의 bound값 : 14 + 7 + 7 + 2 + 4 = 34 

따라서 이런 방식으로 나머지 노드들에 대해서 계산을 해보면 레벨3의 상태공간트리는 다음과 같은 상태가 됩니다. 위에 예시를 [1,2,3]을 선택한 경우를 들었지만 우선순위 큐에 의해 [1,3]을 선택한 경로의 자식노드부터 탐색을 시작하는군요;

이와 같이 계속 계산해 나가다 보면 결국 최종적으로 단말노드(level n-1)까지 계산할 수 있습니다. 

드디어 첫번째 best_solution값이 나왔습니다. 이제 여태 해왔던 것처럼 Queue를 하나씩 꺼내어 bound값을 bestSolution과 비교하여 bound값이 더 작다면(최적이라면) 그대로 탐색하지않고 종료를, 아니라면 해당노드의 밑으로 탐색을 진행하고, 더 좋은 best solution값이 나오면 값을 갱신하는 방법으로 진행해 나가면 최종해를 구할 수 있습니다

결국 큐에 있는 모든 노드들의 bound값이 최적의 해인 30보다 모두 큰 값이므로 최적의 경로는 30의 가중치를 가진 v1 -> v4 -> v5 -> v2 -> v1 경로인것을 구할 수 있습니다. 이제 동작방식을 이해하였으니 sudo코드를 작성해 보도록 하겠습니다. 

#include <iostream> #include <iostream> #include <queue> #include <vector> #include <stdlib.h> using namespace std; struct node{ int level; int path[] ; int bound; }; struct cmp{ bool operator() (node x, node y) { return y.bound < x.bound; } }; public int TSP(int n, int[] W, node optTour) { priority_queue <node, vector<node>, cmp> PQ; node u, v; int best_solution = 10000; //무한대와 같은 큰값 clear(PQ); v.level = 0; v.path = [1]; while(!empty(PQ)){ v = PQ.pop(); //if v is promising if(v.bound < best_solution) { //take_care_of_children u.level = v.level + 1 ; for (all i such that 2<=i<= n && i not in v.path){ u.ordered_path = v.ordered_path; put i at the end of u.path; if(u.level == n-2){ put index of only vertex not in u.path at the end of u.path; put 1 at the end of u.path ; if(bound(u) < best_solution){ best_Solution = bound(u); optTour = u.path; } } else{ u.bound = bound(u); if(u.bound < best_solution) PQ.push(u) } } } } }

자세한 알고리즘은 생략하였지만 결론은 branch and bound 기법으로 문제를 접근하여도 여전히 시간복잡도가 지수적이거나 그보다 못하다는 점입니다. 즉 n=40정도가 된다면 문제를 풀 수 없는 것과 다름이 없다고 할 수 있습니다. 

이 문제는 아직까지 최적의 알고리즘이 밝혀지지 않은 문제중 하나인데요, 오늘은 이렇게 해서 B&B방식을 3개의 예제를 통해서 알아보았습니다. 이상으로 포스트 마치겠습니다. 

이번 포스팅에서는 백 트래킹 기법에 대해서 포스팅 하도록 하겠습니다. 

사실 백 트래킹이라는 것은 알고리즘이라기 보단 어떤 문제를 풀기위한 전략? 에 가까운데요,

어떤 제약조건 만족 문제에서 해를 찾기 위한 전략으로 백 트래킹(backtracking) or 퇴각 검색(backtrack)으로 부릅니다.

해를 찾기 위해, 후보군에 제약 조건을 점진적으로 체크하다가, 해당 후보군이 제약 조건을 만족할 수 없다고 판단되는 즉시 backtrack (다시는 이 후보군을 체크하지 않을 것을 표기)하고, 바로 다른 후보군으로 넘어가며, 결국 최적의 해를 찾는 방법입니다. 

실제 구현시, 고려할 수 있는 모든 경우의 수 (후보군)를 상태공간트리(State Space Tree)를 통해 표현

(반드시 트리형태로 만들 필요는 없습니다, 컨셉상 트리를 의미, 뒤에 예제와 함께 설명드리겠습니다. )

• 각 후보군을 DFS(깊이 우선 탐색) 방식으로 확인
• 상태 공간 트리를 탐색하면서, 제약이 맞지 않으면 해의 후보가 될만한 다른 곳으로 바로 넘어가서 탐색
  • Promising: 해당 루트가 조건에 맞는지를 검사하는 기법
  • Pruning (가지치기): 조건에 맞지 않으면 포기하고 다른 루트로 바로 돌아서서, 탐색의 시간을 절약하는 기법

즉, 다시한번 요약하자면 백트래킹은 트리 구조를 기반으로 DFS로 깊이 탐색을 진행하면서 각 루트에 대해 조건에 부합하는지 체크(Promising - 솔루션이 될수 있는지), 만약 해당 트리(나무)에서 조건에 맞지않는 노드는 더 이상 DFS로 깊이 탐색을 진행하지 않고, 가지를 쳐버림 (Pruning - 이 노드 아래의 모든 값들은 탐색할 필요가 없다) 라는 겁니다. 

글로봤을 때는 무슨 말인지 잘 와닿지 않겠지만,  예제를 풀다보면 이것들이 무슨 의미인지 좀더 이해가 쉬울겁니다. 이제 백 트래킹 예제를 풀어보면서 살펴보겠습니다.

N Queen 문제

문제는 다음과 같습니다.

• NxN 크기의 체스판에 N개의 퀸을 서로 공격할 수 없도록 배치하는 문제
• 퀸은 다음과 같이 이동할 수 있으므로, 배치된 퀸 간에 공격할 수 없는 위치로 배치해야 함

이 N Queen 문제는 대표적인 백 트레킹 문제입니다. 

만약 4X4 크기의 체스판이라고 가정한다하면 16개의 칸중에 4개의 퀸자리를 선택하는 경우의 수만 해도 

C(16,4) = 1820 , 각 행마다 하나씩 자리를 선택한다하도 4x4x4x4 = 256 가지의 경우의 수가 존재합니다.

이 모든 경우의 수를 다 참조하여 솔루션을 판단하는 것은 매우 비효율적이죠, 어디서 부터 시작해야 할지도 참 난감합니다; 우선 위에서 기술한 대로 고려할 수 있는 모든 경우의 수를  State Spae Tree로 표현해 봅시다.

State Space Tree로 모든 경우의 수를 표현해본 그림입니다.

(위 그림은 개념적으로 트리형태로 표현한 것이지 구현시 반드시 트리구조를 이용해야하는 것은 아닙니다) 

각 노드의 레벨은 체스판의 행번호와 같습니다.  [1,1] 노드는 레벨이 1이므로 1행에 1열에 Queen을 배치하겠다는 의미입니다.  그림에서 보이는 것과 같이 [3,4]은 [1,1], [2,1] 상태에서 추가적으로 [3,4] 위치에 퀸을 배치된 상태를 의미합니다.  

이제 Promising한 노드와 non-promising 한 경우를 살펴 봅시다.

그림이 조금 난해합니다; 

이 문제에서 promising 한것은 해당 노드가 배치된 퀸들끼리 서로의 공격범위에 들어가있지 않은 상태를 의미합니다.

예를 들면 위 그림과 같이 [1,2] 노드 상태는 아직 퀸하나만 배치되어 있으므로 promising 조건을 만족합니다. 

(즉 그대로의 의미처럼 이 밑으로 솔루션이 나올수 있는 유망한 노드라는 뜻입니다.)

이럴경우 해당 노드의 밑으로 계속해서 깊이 우선탐색을 진행합니다. 

하지만 non-promising, 예를 들면 [1,1] -> [2,1] 노드처럼 이미 서로의 공격범위에 노출되어있는 상태의 노드들은 

이 밑으로 경우의수를 탐색해봤자 더 이상 의미가 없습니다. 어차피 이 밑으로 탐색을 진행해도 솔루션을 만족하지 못하는  non-promising (유망하지 않은) 노드라는 것입니다. 이럴경우 [2,1] 밑으로는 탐색을 하지않고 (Pruning, 가지치기다시 backtrack 하여 다른 promising한 노드들을 찾아 조사를 시작합니다. 

이제 Backtracking이란 기법이 어떻게 적용되는지 감이 오시나요?  다시한번 요약하자면 아래와 같습니다. 

Backtracking

• 기본적으로 깊이 우선 탐색을 실행하지만, 더깊은 노드를 탐색하는 것은 현재 노드가 promising 한지에 달려있다. 
• 만약 non-promising 하다면, backtrack하여 해당 노드의 부모노드로 돌아가 다른 노드를 search 한다  

이제 본격적으로 코드를 짜기위해 Promising 한지를 판단하기 위한 규칙을 정의해 보겠습니다.

Col(i)를 i행에 위치한 퀸이 위치한 열의 번호라 정의

• 두 퀸이 같은 열에 위치하는 지 check 하려면 :  Col(i) = Col(k) 인지 판단 
• 두 퀸이 서로 같은 대각선에 위치하는지 check 하려면:   |Col(i) - Col(k)| = i-k 인지 판단 

위 조건들을 check해서 두 조건에 해당하지 않는다면 해당 노드는 pomising하다고 판단할 수 있습니다.

이를 기반으로 코드를 작성하면 다음과 같습니다 .

1. promising한지를 판단하는 함수구현 

2. promising 한지 체크하며 재귀적으로 깊이 우선탐색을 실행하는 함수  

#include <iostream> using namespace std; int N; //체스판 사이즈 int col[15]; int result = 0; bool promising(int i) { for(int j=0;j<i; j++) { if(col[j] == col[i] || abs(col[i]-col[j])==(i-j)) return false; } return true; } void N_qeen(int i) { if(i==N) result +=1; else { for(int j=0 ; j<N, j++) { col[i] = j; if(promising(i)) N_qeen(i+1); } } } int main() { cin>>N; N_qeen(0); cout<<result<<endl; return 0; }

코드를 구현하였으니 분석을 진행해볼 시간입니다! 

N-queen 문제의 경우, 정확한 n에 대한 값을 계산하기는 어렵지만 대략적으로

이 정도 이상은 방문하지 않겠다라는 upper bound 값은 계산할 수는 있습니다.

먼저 알고리즘을 고려하지 않고 최대 탐색할 수 있는 노드의 수를 계산해보면 

깊이 1에는 -> 1개 

깊이 2에는 -> n개 ,

깊이 3에는 각 노드에서 또 n개 씩 가지가 나온다고 가정하면 -> $ n^2 $ 

이런 식으로 깊이 n까지 나아간다면 최대로 탐색할 수 있는 노드의 수는 

1 + n + $n^2$ + $n^3$ + ... + $n^n$=($n^{n+1}$-1)/(n-1)

이와 같이 Maximum upper Bound를 정할 수 있습니다.

열이 다른 것들을 제외했을 때의 promising 한 노드를 거치는 경우만  따져도 나름 대로

upperbound을 계산할 수 있으니 따져보면 

Upper Bound on number of pormising nodes :

깊이 1 -> 1

깊이 2 -> n

깊이 3 -> $n\times (n-1)$  (열이 겹치는 경우를 하나 뺀경우)

깊이 4 ->  $n\times (n-1)\times (n-2)$

이 모든 경우를 더하면 1+ n + n(n-1) + .. + n! 임을 알 수 있습니다.  

Graph Coloring 문제

문제는 다음과 같습니다.

• 어떤 방향성이 없는 그래프가 주어졌을 때, 그래프의 각 노드에 m개의 색깔중 하나를 선택해서 칠함 
• 서로 인접한 노드의 색깔은 같은 색이 되지 않도록 칠해야 한다. 

처음 접했을 때는 어떻게 접근해야 할지 막막하지만 왼쪽그림을 오른쪽과 같이 그래프로 표현할 수 있다는 점을

깨닫는 다면 쉽게 접근이 가능합니다. 이제 오른쪽 그림과 같은 그래프를 토대로 상태공간트리를 표현해보겠습니다. 

각 단계를 (level을) 노드라고 정의한다면 오른쪽과 같이 상태공간 트리를 표현할 수 있습니다. 

이제 state space tree를 정의하였으니 이것을 토대로 탐색을 계속 진행할지 여부를 반단하는 promising함수와 

promising한 노드를 재귀적으로 탐색할 backtracking 함수를 구현하기만 하면 됩니다. 

먼저 backtracking 부분을 구현해 봅시다. 

backtracking 함수를 구현할 때 필요한 부분은 다음 두가지 입니다. 

1. 모든 탐색이 끝났을 때 탐색을 종료하는 분기점 

2. promising하다면 해당노드로 다음탐색을 진행하는 부분 

위 두가지 내용을 반영하여 backtracking 함수를 구현하면 다음과 같습니다. 

#include <iostream> using namespace std; int N = 4 ; int W[4][4]; int result[4]; int COLOR = 3; void backtracking(int node) { if(promising(node)){ if(node == N){ //cout<<result[1] ~ result[4] 결과값 출력 } else{ for(int color=0; color<COLOR ; color++){ result[node+1] = color; backtracking(node+1); } } } }

이제 promising 함수를 구현해봅시다.

promising한 조건을 만족하지 못하는 경우는 어떤경우가 있을까요?

아마 어느 두 노드가 서로 이어져있고, 이어져 있는 두 노드가 같은 색깔을 갖는다면 그것은 promising 하지 않은 상태일 겁니다. 이를 간단한 코드로 구현한다면 다음과 같이 표현할 수 있습니다.

#include <iostream> bool promising(int i){ int j=1; int Switch =true; while(j<i && Switch){ if(W[i][j] && result[i]==result[j]) Switch = false; j++; } return Switch }

The 0-1 Knapsack 문제

문제는 다음과 같습니다.

• 배낭에 담을 수 있는 무게의 최댓값은 정해져 있다. 
• 배낭에 넣을 물건들은 각자 무게와 가치가 정해져 있다.
• 짐들을 배낭에 넣을 때 가치의 합이 최대가 되도록 집을 고르는 방법을 찾아라 

앞서 나온 문제들이 백 트레킹으로 특정 결과값을 구하는 문제였다면 이 문제는 앞의 문제들과는 조금 다릅니다. 

바로 특정 값을 구하는 것이 아닌 조건을 만족하는 해중 가장 최적의 해를 찾는 문제라는 겁니다. 

우선 state space tree를 어떻게 정의할 지 생각해봅시다. 

최적의 값을 비교하기 위해선 우선 현재의 노드가 가지고 있는 현재 가치(profit)와 무게(weight)에 대한 정보가 필요할 겁니다.  하지만 이것만으로는 state space tree를 생각하기 쉽지 않습니다.  백트레킹을 구현하기 위해서는 필요없는 노드들을 pruning 할 수 있는 조건이 필요한데, 위 두 정보만으로는 이를 구현하기 어렵기 때문이죠..

따라서 다음과 같은 정보를 상태공간 트리 노드에 추가해 줍니다. 

The upper bound on the maximum profit

-> 물픔을 조각내어(fraction) 채워넣는것을 허용하였을 때, 현재 노드에서 향후 얻을 수 있는 최대 이득값  

말이 조금 애매할 수 있지만, 정리하자면 현재 노드의 가능성, 즉 현재상태에서 최대로 얻을 수 있는 이득값(upper bound)를 계산하여 정보를 가지고 있다면, 탐색중 만약 현재 노드의 upper bound 보다 큰 가치(profit)값을 가지고 있는 다른노드가 존재 한다면,  현재 노드 아래의 값은 더 이상 최적이 값이 아니며 탐색할 필요가 없다는 뜻이 되므로 필요없는 노드들을 pruning 하고  backtracking을 할 수 있게 되는 겁니다.  

이제 profit, weight , upper bound 값을 포함한 노드를 토대로 state space tree를 정의해 봅시다. 

각 물품들은 무게대비 가격이 높은 순으로 정렬되어 있으며, 최대 무게 제한은 16입니다. 

upper bound란 값은 노란색 말풍선 처럼 계산 됩니다. 물품은 위에서부터 아래로 순차적으로 채워지며 

item1 -> 이득 : 40 , 무게 : 2  =>  누적무게: 2  

item2 -> 이득 : 30 , 무게 : 5  =>  누적무게: 7  

item3 -> 이득 : 50 , 무게 : 10  =>  누적무게: 17  -> 무게 초과로 fraction 해서 채워넣는다. 

item3 -> 이득: 50 * 9/10, 무게 10* 9/10 => 누적 무게 16 , 총 upperbound profit = 115

(9/10은 (16 - 7) / item3의 무게로 구한 값)  

위와 같은 계산과정을 통해서 계산이 됩니다. 따라서 위 space state tree를 기반으로 

Upper bound 계산하는 부분과 promising 함수를 정의 할 수만 있다면,

이 문제를 backtracking으로 해결 할 수 있을 겁니다. 

백트래킹 함수 부분: 

최적의 값이 나오면 값을 갱신. 

i 레벨까지 (i번쨰 아이템을 넣었을 떄) promising 하다면,

다음 아이템(i+1)을 넣거나, 넣지않았을 경우 2가지에 대해서

재귀적으로 backtracking 함수 호출 

#include <iostream> //global variables int maxProfit = 0; //최대 이득값 저장 int numBest = 0; char bestSet[4]; //최적의 값을 갖는 노드의 물품 구성 저장 char curruent_Set[4]; // 예시 | y | y | n | y | int p[4] //문제에서 주어지는 물품의 profit 정보 int w[4] // 문제에서 주어지는 물품의 weight 정보 void backtracking(int i , int profit int weight){ if (weight <= W && profit > maxProfit) { maxProfit = profit; numBest = i; bestSet = current_Set ; } if(promising(i)){ current_Set[i+1] = "y"; backtracking(i+1, profit+ p[i+1], weight+ w[i+1]); current_Set[i+1] = "n"; backtracking(i+1,profit, weight); } }

promising 함수 부분: 

만약 현재 무게가 W=16을 초과한다면 false 반환, 

아니라면 upper bound값을 계산해서 현재의 upperbound가 maxProfit값보다 크다면 true 반환 

#include <iostream> bool promising(int i){ if(weight >= W) return false; else{ // upper bound 를 계산하는 부분 j = i+1 ; bound = profit; totWeight =weight; while(j<=n && totWeight+ w[j] <=W ){ totWeight += w[j]; bound += p[j]; j++; } k = j; if (k <= n) bound = bound + (W-totWeight)*p[k]/w[k]; return bound > maxProfit; // upper bound 가 maxprofit 보다 크면 참을 반환 } }

이로서 백트레킹에 대한 대표 예제들에 대해서 살펴보았습니다. 

백트레킹으로 문제를 접근하기 위해선 먼저 space state tree를 정의해야 하며

이를 토대로 backtrack함수와 promising 함수를 정의하면 보다 쉽게 문제를 해결할 수 있음을 알아보았습니다.

다음 포스트에서는  Branch and Bound (분기 한정법) 에 대해서 알아보도록 하겠습니다. 

이제 본격적으로 프림 알고리즘을 파이썬 코드로 작성해 보도록 하겠습니다! 

파이썬으로 프림 알고리즘을 간단하게 구현하기 위해서 두 가지 라이브러리를 소개 해드리겠습니다. 

참고) heapq 라이브러리 활용을 통해 우선순위 큐 사용하기

우선순위 큐는 우선 순위가 가장 높은 자료(data)를 가장 먼저 꺼낼 수 있는 자료 구조인데요, 파이썬에서는 이를 heapq라는 라이브러리로 정의해 놓았습니다! 이 자료구조는 삽입연산이 O(logN)으로 빠른 연산속도를 보여줍니다 

(자세한 내용은 여기서는 스킵) 

아무튼 요지는 이 라이브러리를 사용하면 가중치가 작은 것부터 우선적으로 쉽게 값을 참조하고 뽑아 쓸수 있어 프림알고리즘을 구현하는데 굉장이 유용하다는 것입니다! 

heapq에 내장된 함수인 heapify함수는 입력으로 받은 리스트 데이터를 자동으로 heap형태로 한번에 변환해줍니다! 

import heapq 

graph_data = [[2, 'A'], [5, 'B'], [3, 'C']]

 
heapq.heapify(graph_data)

for index in range(len(graph_data)):

    print (heapq.heappop(graph_data))

print (graph_data)

결과: [2, 'A'] [3, 'C'] [5, 'B'] []

참고) collections 라이브러리의 defaultdict 함수 활용하기

defaultdict 함수는 key에 대한 value를 지정하지 않았더라도 자동으로 빈 리스트로 초기화해주는 함수입니다. 

from collections import defaultdict

list_dict = defaultdict(list)
print (list_dict['key1'])

결과: []

프림 알고리즘 구현 

앞서 포스트에서 프림알고리즘 동작 방식 5단계를 기억하시나요? 이를 좀더 구현에 집중하여 살펴보겠습니다. 

1. 모든 간선 정보를 저장 (adjacent_edges)
2. 임의의 정점을 선택, '연결된 노드 집합(connected_nodes)'에 삽입
3. 선택된 정점에 연결된 간선들을 간선 리스트(candidate_edge_list)에 삽입
4. 간선 리스트(candidate_edge_list)에서 최소 가중치를 가지는 간선부터 추출해서,
   • 해당 간선에 연결된 인접 정점이 '연결된 노드 집합'에 이미 들어 있다면, 스킵함(cycle 발생을 막기 위함)
   • 해당 간선에 연결된 인접 정점이 '연결된 노드 집합'에 들어 있지 않으면, 해당 간선을 선택하고, 해당 간선 정보를 '최소 신장 트리(mst)'에 삽입
     • 해당 간선에 연결된 인접 정점의 간선들 중, '연결된 노드 집합(connected_nodes)' 에 없는 노드와 연결된 간선들만 간선 리스트(candidate_edge_list) 에 삽입
       • '연결된 노드 집합(connected_nodes)' 에 있는 노드와 연결된 간선들을 간선 리스트에 삽입해도, 해당 간선은 스킵될 것이기 때문임
       • 어차피 스킵될 간선을 간선 리스트(candidate_edge_list)에 넣지 않으므로 해서, 간선 리스트(candidate_edge_list)에서 최소 가중치를 가지는 간선부터 추출하기 위한 자료구조 유지를 위한 effort를 줄일 수 있음 (예, 최소힙 구조 사용)
5. 선택된 간선은 간선 리스트에서 제거
6. 간선 리스트에 더 이상의 간선이 없을 때까지 3-4번을 반복

프림 알고리즘 파이썬 코드

이제 위에서 작성한 글을 토대로 파이썬 코드를 구현해 보겠습니다

먼저 이전 포스트에서 예시로 든 그래프를 다음과 같이 리스트 형태로 저장하였다 가정합시다. 

#중복되는 간선들을 제외하고 표시함 
myedges = [
    (7, 'A', 'B'), (5, 'A', 'D'),
    (8, 'B', 'C'), (9, 'B', 'D'), (7, 'B', 'E'),
    (5, 'C', 'E'),
    (7, 'D', 'E'), (6, 'D', 'F'),
    (8, 'E', 'F'), (9, 'E', 'G'),
    (11, 'F', 'G')
]

이제 부터 위 그래프와 시작할 임의의 노드를 입력으로 받아서 최소신장트리 값을 반환하는 prim 이라는 함수를 작성해 보도록 하겠습니다! 

from collections import defaultdict 
from heapq import *

def prim(start_node, edges):
	mst = list() 
    adjacent_edges = defaultdict(list)
    for weight, n1, n2 in edges: 
    	adjacent_edges[n1].append((weight, n1, n2)) 
        adjacent_edges[n2].append((weight, n2, n1)) 
      
    connected_nodes = set(start_node) 
    candidate_edge_list = adjacent_edges[start_node] 
    heapify(candidate_edge_list)     

먼저 기본적인 변수 설정과 초기화 과정입니다.  최종적인 결과값(mst)를 반환할 리스트 mst, 

모든 쌍방 간선들의 정보를 저장할 adjacent_edges, 연결된 노드들을 저장할 connected_nodes,

후보군 간선들을 저장할 최소우선순위 큐로 정의된 candidate_edge_list  를 정의하여 줍니다

중간에 for 문으로 시작하는 부분이 이해가 안가실 수 도 있는데, 이는 어떤 노드를 시작으로 접근하더라도 해당하는 간선 정보를 불러올 수 있도록 모든 쌍방으로 연결된 간선을 저장하는 것입니다. 

입력으로 받는 myedges 그래프 같은 경우는 중복되는 간선이 없습니다. 

즉 (7, `A' , 'B') 라는 간선이 저장되어 있다면 (7, `B' , 'A') 라는 간선은 저장되어 있지 않다는 말입니다. 

하지만 for 문 연산을 통해 adjacent_edges에 그 쌍방의 간선정보까지 모두 저장해 줍니다.

왜 이런 짓을 하냐구요? 그래야지 어떤 노드의 값으로 접근하든 그 노드에 인접한 모든 간선의 값들을 조회할 수 있기 떄문 입니다.  만약에 그저 입력으로 들어온 그래프 값으로만 조회한다면 노드 B로 참조를 시도했을 때 

 (7, `B' , 'A') 라는 간선의 정보는 저장되어 있지 않기 때문에 인접 간선정보가 누락이 되버릴 겁니다. 

이제 초기화까지 완료하였으니 핵심 알고리즘을 구현해 보도록 하겠습니다.

while candidate_edge_list:
	weight, n1, n2 = heappop(candidate_edge_list)
    if n2 not in connected_nodes: 
    	connected_nodes.add(n2)
        mst.append((weight, n1, n2)) 
        
        for edge in adjacent_edges[n2]:
        	if edge[2] not in connected_nodes:
            	heappush(candidate_edge_list, edge) 

return mst
 

글로는 엄청 복잡했던 것 같은데, 구현하니 채 10줄 정도 밖에 나오지 않습니다;; 

구현은 위에서 작성한 구현 알고리즘을 그대로 따라 가시면 됩니다

먼저 candidate_edge_list 에 저장된 mst에 저장될 수 있는 후보 간선을 최소값이 작은것 부터 차례대로 불러옵니다. 

만약 (weight, n1->n2) 인 간선을 뽑았을 때 새롭게 잇게 되는 노드인 n2가 아직 connected_nodes에 저장되지 않았다면?  

해당 간선에 연결된 인접 정점이 '연결된 노드 집합'에 들어 있지 않으면, 해당 간선을 선택하고, 해당 간선 정보를 '최소 신장 트리(mst)'에 삽입

위에서 작성한 구현 알고리즘을 그대로 작성해 주시면 됩니다.

connected_node에 n2 노드를 추가하고 mst에 해당 간선 정보를 저장합니다. 

그리고 나서 새롭게 연결된 n2에 연결되어 있는 간선들의 정보를 candidate_edge_list에 저장해 주는 겁니다. 

해당 간선에 연결된 인접 정점의 간선들 중, '연결된 노드 집합(connected_nodes)' 에 없는 노드와 연결된 간선들만 간선 리스트(candidate_edge_list) 에 삽입 

앞서 adjacent_edges는 모든 쌍방의 간선 정보들을 저장하고 있다고 말씀드렸죠?

여기서 노드 n2에서 시작하는 모든 간선들을 조회했을 때 각 간선들의 목적지(이어주는 노드) 노드가 이미 connected_nodes에 저장이 되어있다면? 무시해버리면 됩니다! 어차피 안쓸거니까요 

저장이 안되어있는 것들만 후보 간선 리스트, candidate_edge_list에 넣어주시면 되는겁니다! 

그런식으로 모든 후보 간선들이 다 제거가 되고나면 (while candidate_edge_list) 이제 최소신장트리가 완성되었다는

뜻이며 이 최종결과값을 반환 해 주기만 하면 알고리즘은 끝이 납니다

결과값 :

prim ('A', myedges)

[(5, 'A', 'D'), (6, 'D', 'F'), (7, 'A', 'B'), (7, 'B', 'E'), (5, 'E', 'C'), (9, 'E', 'G')]

이 프림알고리즘의 시간 복잡도는 최악의 경우, while 구문에서 모든 간선에 대해 반복하고,

최소 힙 구조를 사용하므로 O(ElogE) 시간 복잡도를 가집니다. 

이를 개선하여 O(ElogV)의 시간 복잡도를 가진 프림알고리즘도 있긴 하지만 이는 기회가된다면 다음에 다루도록 하겠습니다. 이로서 프림알고리즘에 대한 포스트를 마치겠습니다.

프림 알고리즘은 크루스칼 알고리즘과 함께 어떤 그래프가 주어졌을 때 그 그래프에서 최소신장트리(MST) 를 찾아내는 알고리즘 입니다. 최소신장트리에 대한 개념은 앞에 포스트했던 크루스컬 알고리즘에서 정리하였으니 참고하시기 바랍니다.

https://buganddog.tistory.com/2

크루스칼 알고리즘에서 먼저 간선을 선택하고 그다음 노드를 하나씩 붙여가는 식이였다면 프림알고리즘은 반대로 시작 정점을 먼저 선택한 후 정점에 연결된 간선을 추가해서 하나씩 붙여나가는 방식으로 알고리즘이 진행됩니다. 말이 참 애매한데; 좀더 명확히 정리해보도록 하겠습니다. 

프림 알고리즘 (Prim's algorithm)

• 대표적인 최소 신장 트리 알고리즘
  • Kruskal’s algorithm (크루스칼 알고리즘), Prim's algorithm (프림 알고리즘)
• 프림 알고리즘
  • 시작 정점을 선택한 후, 정점에 인접한 간선중 최소 간선으로 연결된 정점을 선택하고, 해당 정점에서 다시 최소 간선으로 연결된 정점을 선택하는 방식으로 최소 신장 트리를 확장해가는 방식
• Kruskal's algorithm 과 Prim's algorithm 비교
  • 둘다, 탐욕 알고리즘을 기초로 하고 있음 (당장 눈 앞의 최소 비용을 선택해서, 결과적으로 최적의 솔루션을 찾음)
  • Kruskal's algorithm은 가장 가중치가 작은 간선부터 선택하면서 MST를 구함
  • Prim's algorithm은 특정 정점에서 시작, 해당 정점에 연결된 가장 가중치가 작은 간선을 선택, 간선으로 연결된 정점들에 연결된 간선 중에서 가장 가중치가 작은 간선을 택하는 방식으로 MST를 구함. 

프림알고리즘의 동작을 이해 하기위해선  다음 5단계만 기억하시면 됩니다! 

1. 임의의 정점을 선택, '연결된 노드 집합'에 삽입
2. 선택된 정점에 연결된 간선들을 간선 리스트를 만들어서 리스트에 삽입
3. 간선 리스트에서 최소 가중치를 가지는 간선부터 추출해서,
   • 해당 간선에 연결된 인접 정점이 '연결된 노드 집합'에 이미 들어 있다면, 스킵! (cycle 발생을 막기 위함)
   • 해당 간선에 연결된 인접 정점이 '연결된 노드 집합'에 들어 있지 않으면, 해당 간선을 선택하고, 해당 간선 정보를 '최소 신장 트리'에 삽입
4. 추출한 간선은 간선 리스트에서 제거
5. 간선 리스트에 더 이상의 간선이 없을 때까지 3-4번을 반복

처음에는 간선 리스트가 무엇이며, 연결된 노드 집합이라는 건 무엇인지 감이 잘 오지 않으실 겁니다. 

이러한 세부적인 부분들은 후에 구현 부분에서 다루기로하고, 우선 프림알고리즘의 동작방식에 대한 큰 개념을 잡는것을 목표로 하고 이를 그림으로 확인해 보도록하겠습니다. 

먼저 시작단계입니다. 위에서 5단계를 잘 염두하고 그래프를 보도록하겠습니다. 

시작은 임의의 정점을 선택하는 것에서 시작합니다.

여기서는 A라는 정점을 선택했군요! 

그림상에서 보이지는 않지만, 선택한 A 노드를 '연결된 노드집합' 으로 정의된 자료구조에 넣고 선택된 정점에 연결된 

간선들. 또한 '연결된 간선 리스트' 라는 자료구조를 정의해서 그안에 넣어 두도록 합시다. 

앞서 말씀드렸듯이. 어떻게 넣는지에 대해서는 생각을 잠시 미루고, 큰 개념을 우선적으로 보겠습니다.

( 위 그림에서는 리스트에 넣어진 간선은 빨간색, MST에 들어간 노드와 간선들은 파란색으로 표시해줍니다 ) 

그림에서는 노드 A가 선택되고 A와 연결된 가중치 5, 7인 간선 2개가 간선리스트에 추가가되고, 따라서 리스트에 저장된 간선중 가중치가 최소인 (5 ,A->D) 간선을 꺼내서 조사를 합니다. (3단계 과정)   

• 해당 간선에 연결된 인접 정점이 '연결된 노드 집합'에 이미 들어 있다면, 스킵! (cycle 발생을 막기 위함)
• 해당 간선에 연결된 인접 정점이 '연결된 노드 집합'에 들어 있지 않으면, 해당 간선을 선택하고, 해당 간선 정보를 '최소 신장 트리'에 삽입

현재 그림에서는 간선에 연결된 노드 D 가 연결된 노드집합에 속해 있지 않으므로 노드 D를 연결된 노드 집합에 추가해 줍니다! 그 후 조사했던 간선 (5 ,A->D) 는 연결된 간선리스트에서  제거해줍니다! 

동작방식이 조금은 이해 되시나요? 

이와 같은 과정을 계속해서 반복하여 더 이상 연산가능한 간선이 없을 때 까지 계속해서 반복하는것이 프림알고리즘 입니다! 계속해서 확인해 보도록 하겠습니다. 

노드 D와 연결된 간선들 리스트에 저장 -> 리스트에서 가중치 최소인 간선 (5, D->F) 추출 ->  연결된 노드집합에 F가 없으므로 노드집합에 추가 ->    (5, D->F) 간선을 '최소 신장 트리'에 삽입  ->  간선리스트에서 (5, D->F)제거

이제 좀 더 감이 확실히 잡히는 느낌입니다. 이제 나머지 동작그림을 한눈에 봐보도록 하겠습니다

마지막 6번에서 리스트에 저장된 간선들(빨간색 간선)을 모두 조사를 하지만 (9,E-G)를 잇고 나서는 모든 노드들이 

연결되어있고, 최소신장트리가 완성되어 있으므로 그 이외의 나머지 간선들은 위 단계3 에서 정의한 조건

• 해당 간선에 연결된 인접 정점이 '연결된 노드 집합'에 이미 들어 있다면, 스킵! (cycle 발생을 막기 위함) 을 

만족하지 못하기 때문에 리스트에 추가되는 과정없이 스킵이 됩니다! 이렇게 모두 스킵이 되어 더이상 연산을 진행할 간선이 없게 된다면 알고리즘이 종료되는 것입니다. 

여기까지 이해를 하셨다면 프림알고리즘을 구현하는데 있어서 필요한 동작개념을 완벽히 이해를 하신겁니다 ㅎ 

다음 포스트에서는 이 개념을 염두해서 파이썬으로 프림 알고리즘을 구현해 보도록 하겠습니다.  

이번 포스트에서는 파이썬으로 크루스칼 알고리즘을 구현해 보도록 하겠습니다. 

(게시글의 자료들은 잔재미코딩(https://www.fun-coding.org/Chapter20-prim-live.html) 사이트를 참조하였습니다)

먼저 앞선 포스트에서 다룬 그래프를 다음과 같은 그래프를 딕셔너리 형태로 구현하도록 하겠습니다. 

이제 구현까지 살펴 보았으니 시간복잡도를 살펴봅시다. 

시간 복잡도

• 크루스컬 알고리즘의 시간 복잡도는 O(E log E)
  • 다음 단계에서 2번, 간선을 비용 기준으로 정렬하는 시간에 좌우됨
    (즉 간선을 비용 기준으로 정렬하는 시간이 가장 많이 든다)
  • 모든 정점을 독립적인 집합으로 만든다. - 복잡도 O(V) 
  • 모든 간선을 비용을 기준으로 정렬하고, 비용이 작은 간선부터 양 끝의 두 정점을 비교한다.
    • 퀵소트를 사용한다면 시간 복잡도는 O(n log n) 이며, 간선이 n 이므로 O(E log E)
  • 두 정점의 최상위 정점을 확인하고, 서로 다를 경우 두 정점을 연결한다. (최소 신장 트리는 사이클이 없으므로, 사이클이 생기지 않도록 하는 것임)
    • union-by-rank 와 path compression 기법 사용시 시간 복잡도가 결국 상수값에 가까움, O(1)

이상으로 크루스칼 알고리즘에 대한 포스트를 마치도록하겠습니다. 

지난 포스트에서는 크루스칼 알고리즘이 동작하는 개념에 대해서 살펴보았는데요

이번 포스트에서는 그 동작에 대한 세부적인 기준과 알고리즘을 살펴보도록 하겠습니다.

(게시글의 자료들은 잔재미코딩(https://www.fun-coding.org/Chapter20-prim-live.html) 사이트를 참조하였습니다)

지난 포스트에서 노드를 이를 떄 트리로 묶어 두 노드가 같은 집합인지, 다른집합인지 판단했었던것 기억하시나요? 

이를 Union-Find 알고리즘이라 하는데 그림을 통해서 다시한번 확인해 보도록 하겠습니다. 

Union-Find 알고리즘

• Disjoint Set을 표현할 때 사용하는 알고리즘으로 트리 구조를 활용하는 알고리즘
• 간단하게, 노드들 중에 연결된 노드를 찾거나, 노드들을 서로 연결할 때 (합칠 때) 사용
• Disjoint Set이란
  • 서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조
  • 공통 원소가 없는 (서로소) 상호 배타적인 부분 집합들로 나눠진 원소들에 대한 자료구조를 의미함
  • Disjoint Set = 서로소 집합 자료구조

요약하자면 

initial - 각각의 집합요소들을 개별적인 집합으로 분할하는 초기화 과정 
union - 합치는 알고리즘 
find - 중복되는지 검사(사이클 검사) 

크루스칼은 모든 간선이 비용기준으로 정렬을해서 비용이 작은 간선부터 사이클이 생기지않는선에서 모든노드들을 연결합니다.  다만 여기서 두노드를 이었을때 사이클이 생기는지 안생기는지를 판단하기 위해서 union find알고리즘을 사용하는데,  간선끼리 이미 연결된 노드들을 부분집합으로 관리하고 특정 두노드를 뽑아서 그 노드 2개가 루트노드가 동일하다고 한다면  사이클이 생긴다고 가정 , 그게아니면 사이클이 아니라고 판단하고 union 로직을 사용해서 둘을 합친다 .

여기까지가 지난시간에 살펴보았던 내용이었습니다. 그렇다면 과연 Union이란 두 집합을 합치는 과정은 어떠한 기준으로 합치는 걸까요? 지난 포스트에서 막연하게 루트노드끼리 갖다 붙이라고만했지 정확한 방침이 나와있지않은데 
잘못하면 일렬로 나열하게되어 최악의 시간복잡도를 가지게 될 수도 있습니다. 

  특별한 기준없이 위와 같이 그저 한쪽 방향으로만 노드를 이어나가는 방식으로 트리를 구현해 보았다고 가정합시다. 위와 같이 구현하였다고 가정한다면 Union 순서에 따라 최악의 경우 링크드 리스트와 같은 형태가 될 수도 있습니다.  즉 Union, Find 동작시 계산량이 O(N)으로 트리구조를 만드는 이점이 없는 겁니다;; 이러한 사태를 방지하기위해 

nion-by-rank, path compression 기법을 사용합니다.

union-by-rank 기법

• 각 트리에 대해 높이(rank)를 기억해 두고,

• Union시 두 트리의 높이(rank)가 다르면, 높이가 작은 트리를 높이가 큰 트리에 붙임 (즉, 높이가 큰 트리의 루트 노드가 합친 집합의 루트 노드가 되게 함)

• 높이가 h - 1인 두 개의 트리를 합칠 때는 한 쪽의 트리 높이를 1 증가시키고, 다른 쪽의 트리를 해당 트리에 붙임

초기화시, 모든 원소는 높이(rank) 가 0 인 개별 집합인 상태에서, 하나씩 원소를 합칠 때, union-by-rank 기법을 사용한다면,

• 높이가 h 인 트리가 만들어지려면, 높이가 h - 1 인 두 개의 트리가 합쳐져야 함
• 높이가 h - 1 인 트리를 만들기 위해 최소 n개의 원소가 필요하다면, 높이가 h 인 트리가 만들어지기 위해서는 최소 2n개의 원소가 필요함
• 따라서 union-by-rank 기법을 사용하면, union/find 연산의 시간복잡도는 O(N) 이 아닌, O(logN) 로 낮출 수 있음

path compression 기법 

• Find를 실행한 노드에서 거쳐간 노드를 루트에 다이렉트로 연결하는 기법
• Find를 실행한 노드는 이후부터는 루트 노드를 한번에 알 수 있음

#참고

union-by-rank 와 path compression 기법 사용시 시간 복잡도는 다음 계산식을 만족함이 증명 되었다.

• 𝑂(𝑀𝑙𝑜𝑔∗𝑁)O(Mlog∗N)
• 𝑙𝑜𝑔∗𝑁log∗N 은 다음 값을 가짐이 증명되었음
  • N이 265536265536 값을 가지더라도, 𝑙𝑜𝑔∗𝑁log∗N 의 값이 5의 값을 가지므로, 거의 O(1), 즉 상수값에 가깝다고 볼 수 있음

find 를 실행해서 해당 노드의 루트노드를 찾고, 만약 A-B-C-D로 이어진 트리가 있다면 D노드의 루트노드를 찾을 때 그 중간노드가아닌 바로 A노드를 찾아주는 것을 path compressino기법이라고 합니다.

무작위로 트리를 구성하였을 때 O(N)의 시간복잡도를 가졌던 것이 두 알고리즘 기법을 통해 거의 상수에 가까운 시간복잡도를 갖게 되었습니다.  위 방법들을 염두해 두고 다음 포스트에서는 드디어 크루스컬 알고리즘을 파이썬으로 구현 해 보도록 하겠습니다. 

이번 포스트에서는 크루스칼 알고리즘을 다루도록 하겠습니다

긴호흡의 글이 될 것 같아 3개의 글로 나눠 포스트 하도록 하겠습니다. 

이번 포스트에서는 크루스칼알고리즘의 개념을 이해하는데 중점을 두고 구현은 다음 글에서 작성하도록 하겠습니다. 

(게시글의 자료들은 잔재미코딩(https://www.fun-coding.org/Chapter20-prim-live.html) 사이트를 참조하였습니다)

먼저 크루스칼 알고리즘을 이해하기 위해서 최소 신장트리의 개념을 알아야 합니다. 

왜냐면 크루스칼 알고리즘이 어떠한 그래프가 주어졌을 때 그래프의 최소신장 트리를 찾아내는 알고리즘이니까요

신장 트리(Spanning Tree) 란?

• 원래의 그래프의 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 그래프

• 신장 트리의 조건

  • 본래의 그래프의 모든 노드를 포함해야 함
  • 모든 노드가 서로 연결
  • 트리의 속성을 만족시킴 (사이클이 존재하지 않음

이 부분은 그림을 보시면 한눈에 확인 할 수 있습니다. 

보시는 바와같이 그래프의 모든노드가 빠짐없이 이어져 있으며, 각 간선들이 사이클을 생성하지 않습니다, 사이클이란 쉽게 말하면 간선들이 이어진 모양이 태두리로 둘러싸여 막힌 모양이라고 생각하시면 되겠습니다. 

그렇다면 최소신장트리란 무엇인지 감이 오시나요? 

최소 신장 트리

• Minimum Spanning Tree, MST 라고 불리움
• 가능한 Spanning Tree 중에서, 간선의 가중치 합이 최소인 Spanning Tree를 지칭함

왼쪽과 같이 간선에 가중치가 설정된 original그래프가 있다고 가정합시다. MST란 이 가중치가 설정된 그래프에서 

spanning tree를 구현하였을 때 각 간선들의 가중치합이 가장작은 신장트리를 의미합니다. 만약 최소 가중치합 6이라 가정했을때 신장트리중에 가중치 합이 6인 트리가 여러개라면, MST도 여러개 존재할 수 있습니다. 위 예시에서는 하나만 존재하는군요 

따라서 이번 포스트에서 알아볼 크루스칼 알고리즘이란 어떠한 그래프가 주어졌을 때 최소 신장 트리를 찾을 수 있는 알고리즘입니다. 대표적인 최소 신장 트리 알고리즘은 Kruskal’s algorithm (크루스칼 알고리즘), Prim's algorithm (프림 알고리즘)이 있는데, 순차적으로 알아보도록 하겠습니다.  

크루스칼 알고리즘 (Kruskal's algorithm)

1. 모든 정점을 독립적인 집합으로 만든다.
2. 모든 간선을 비용을 기준으로 정렬하고, 비용이 작은 간선부터 양 끝의 두 정점을 비교한다.
3. 두 정점의 최상위 정점을 확인하고, 서로 다를 경우 두 정점을 연결한다. (최소 신장 트리는 사이클이 없으므로, 사이클이 생기지 않도록 하는 것임)

위 단계는 크루스칼 알고리즘을 구현하기 위한 단계를 크게 분류해 놓은겁니다. 

당장은 글이 잘 이해가 안될 수 도 있습니다. 먼저 그림으로 어떻게 동작하는지에 대한 개념을 살펴봅시다 .

먼저 모든 간선들이 가중치가 작은순서대로 정렬되어있다고 가정합시다. 

따라서 간선의 가중치가 가장작은 A-D 간선을 선택하여 해당 노드를 이어줍니다. 그리고 차례대로 그다음으로 가중치가 같거나 작은 간선을 선택하여 노드를 이어줍니다. 위 예시에서는 E와 C노드가 되겠네요 

그 다음으로 가중치가 작은 간선인 D-F노드를 선택합니다. A의 루트노드는 D, B는 독립적인 노드로 자기자신이 루트노드이니, 서로의 루트노드가 다르기 때문에 아래와 같이 트리형식으로 한 집합으로 묶어줍니다. 이 노드들을 묶는 방법에 대해서는 다음 포스트에서 설명할 예정이니 우선 개념적인 부분만 이해하는걸 목표로 합시다 ㅎ 

그 다음으로 작은 가중치는 7이므로 먼저 A-B 간선을 추가하여 이어봅시다. A-B 역시 서로 한 집합에 있지않은 독립적인 집합이었으므로 이어주는 것이 가능합니다. A의 루트노드는 D, B는 기존에 없던 독립적인 노드이니 하나로 합쳐주는 것이 가능합니다. 

이제 B-E간선을 선택해서 이어봅시다. 마찬가지로 트리에서 각각 B , E 노드의 루트노드가 다르기에 두 집합을 하나로 묶을 수 있습니다. 

이제 다음으로 가중치가 작은 D,E 간선을 선택했다고 가정합시다.  D,E 를 연결하게 되면 사이클이 생기게 됌을 확인할 수 있습니다. 트리 구조를 확인해 보면 역시나 D의 루트노드는 E, E 노드는 본인이 루트노드 이므로 서로의 루트노드가 같습니다. 즉, D,E는 서로 같은 집합(트리)에 속해있다고 볼 수 있는거지요 

이제 왜 간선을 추가 할 떄마다 각 노드를 잇는 집합을 트리로 표시하는지, 감이 조금 오시나요? 

크루스칼 알고리즘은 간선을 선택했을 때 간선이 사이클을 생성하는지의 여부를 두 노드가 서로 같은 집합에 속하는지 여부로 판단을 합니다.  이 같은 집합에 속한다는것을 판단하기 위한 도구로 각 간선을 선택할 때 해당노드들을 트리로 만들어 확인하는 겁니다. (이 트리를 생성하는 방법에 대해서는 다음 포스트에서 설명하도록 하겠습니다) 

따라서 위와 같은 사이클이 생기는 경우들을 배제하고, 순차대로 가중치가 작은 간선들을 선택해서 묶어주다보면 위와 같이 주어진 그래프에서 MST를 찾아 낼 수 있는겁니다 ! 

여기까지가 크루스칼 알고리즘이 동작하는 아주 큰 관점에서의 개념을 살펴보았습니다. 

다음 포스트에서는 그렇다면 어떤 방식으로 노드들을 묶고 트리를 생성 하는지에 대한 방법을 다루도록 하겠습니다