부분집합의 합 구하기 문제 부분집합의 합 구하기(Sum-of-Subsets) 문제

Presentation on theme: "부분집합의 합 구하기 문제 부분집합의 합 구하기(Sum-of-Subsets) 문제"— Presentation transcript:

1 부분집합의 합 구하기 문제 부분집합의 합 구하기(Sum-of-Subsets) 문제
n개의 양의 정수 wi와 양의 정수 W가 있을 때 부분집합의 원소들의 합이 W가 되는 모든 부분집합을 찾는 문제 예] n = 5, W = 21, {w1 = 5, w2 = 6, w3 = 10, w4 = 11, w5 = 16} w1+ w2+ w3 = = 21 w1+w5 = 5+16 = 21 w3+w4 = = 21 답: {w1, w2, w3}, {w1, w5}, {w3, w4}

2 부분집합의 합 구하기 문제 - 상태공간트리 부분집합의 합 구하기 문제에 대한 상태 공간 트리 구축 wi 를 오름차순으로 정렬

3 부분집합의 합 구하기 문제 - 상태공간트리 [상태공간트리 예]
n = 3, W = 6, {w1 = 2, w2 = 4, w3 = 5}

4 부분집합의 합 구하기 문제 - 상태공간트리 상태공간 트리에서 유망하지 않은 노드의 조건 및 Pruning
wi+1 : 수준 i에서 남아있는 가장 가벼운 무게 weight: 지금까지 포함한 wi들의 합. 각 노드에 값으로 기재됨 total: 아직까지 고려하지 않은 wi들의 합 [수준 i에 있는 노드가 유망하지 않을 조건] 1) weight + wi+1 > W or 2) weight + total < W [Example] n=4, W=13 {w1=3, w2=4, w3=5, w4=6} 수준 0

5 부분집합의 합 구하기 문제 - 알고리즘 알고리즘: include[i]  w[i]를 포함하면 true, 포함하지 않으면 flase 저장 - W는 전역적으로 선언 - main() 내부에서 호출: SumOfSubsets(0, 0, total); weight 값을 매개변수로 넘겨줄 필요 있음 weight 값을 매개변수로 넘겨받을 필요 있음

6 부분집합의 합 구하기 문제 – 분석 상태공간트리 상의 노드 수에 대한 상한은 다음과 같다.
Monte Carlo 기법을 사용하여, 실제 수행시간을 추정할 수 있다.

7 Graph Coloring? m-색칠하기 문제
응용 분야: 지도 색칠하기 이 그래프에서 두 가지 색으로 문제를 풀기는 불가능하다. 세 가지 색을 사용하면 총 여섯 개의 해답을 얻을 수 있다. 여러 답 중 하나 v1 : 색1 v2 : 색2 v3 : 색3 v4 : 색2

8 평면 그래프 (Planar Graph) 평면 그래프 (Planar Graph)
평면 상에서 이음선(edge)을 늘려서 그러한 이음선들이 서로 엇갈리지 않게 그릴 수 있는 그래프. 다음 두 그래프는 평면 그래프인가? 옆 그래프에서 (v1, v5)와 (v2, v4)를 추가하면 더 이상 평면 그래프가 아니다.

9 지도와 평면 그래프 (Planar Graph)
일반 지도를 평면 그래프로 변환 임의의 지도에서 각 지역을 그래프의 노드로 하고, 한 지역이 어떤 다른 지역과 인접해 있으면 그 지역들을 나타내는 노드들 사이에 이음선을 연결한다. 그러면, 모든 지도는 그에 상응하는 평면그래프로 표시할 수 있다.

10 지도와 평면 그래프 (Planar Graph)
결국 “m-색칠하기 문제”는 최대 m개의 색을 사용하여 인접한 지역이 같은 색이 되지 않도록, 지도를 색칠하는 방법이 얼마나 있는지를 구하는 문제로 해석할 수 있다.

11 Graph Coloring – Backtracking
Backtracking Strategy for 3-Coloring Problem

12 Graph Coloring – Algorithm (1/2)
A Backtracking Algorithm for the Graph Coloring Problem 입력: n – 노드의 수, m – 색깔의 수, W[i][j] – 이음선 있으면 true, 그렇지 않으면 false 출력: vcolor[i] - i번째 노드에 할당된 색(1 ~ m) void m_coloring(index i){ int color; if(promising(i)) if(i == n) System.out.print(vcolor[1] through vcolor[n]); else for(color=1;color <= m;color++) { vcolor[i+1] = color; //다음 노드에 모든 색을 시도해 본다. m_coloring(i+1); } 최상위 수준 호출: m_coloring(0);

13 Graph Coloring – Algorithm (2/2)
A Backtracking Algorithm for the Graph Coloring Problem (계속) boolean promising(index i){ index j = 1; boolean switch = true; while(j < i && switch) { if(W[i][j] && vcolor[i] == vcolor[j]) switch = false; j++; } return switch; 모든 vertex에 대해 “인접하고, 색이 같은지”의 여부를 조사한다.

14 Graph Coloring – 분석 상태공간트리 상의 노드 수에 대한 상한은 다음과 같다.
마찬가지로, Monte Carlo 기법을 사용하여, 실제 수행시간을 추정할 수 있다. n+1 n

15 Hamiltonian Circuits (1/2)
연결된 비방향성 그래프에서, 해밀토니안 회로(Hamiltonian Circuits)/일주여행경로(tour)는 어떤 한 노드에서 출발하여 그래프 상의 각 노드를 한번씩 만 경유하여 다시 출발한 노드로 돌아오는 경로이다.

16 Hamiltonian Circuits (2/2)
해밀토니안 회로 문제: 연결된 비방향성 그래프에서 해밀토니안 회로를 결정하는 문제 되추적 방법을 적용할 때의 유망(Promising) 여부 판단 기준 경로 상의 i번째 노드는 그 경로 상의 (i - 1)번째 노드와 반드시 이웃 해야 한다. (n - 1)번째 노드는 반드시 0번째 노드(출발점)와 이웃해야 한다. i번째 노드는 그 앞에 오는 i - 1개의 노드들 중 하나가 될 수 없다. (즉, 각 노드는 한번씩만 방문해야 한다.)

17 Hamiltonian Circuits 되추적 알고리즘(1/2)
알고리즘 5.6: 해밀튼의 회로문제를 푸는 되추적 알고리즘 입력: n – 노드의 수, W[i][j] – 이음선 있으면 true, 그렇지 않으면 false 출력: vindex[i] (i는 1부터 n) void hamiltonian(index i){ index j; if(promising(i)) if(i == n) System.out.print(vindex[1] through vindex[n]); else for(j=2 ; j<=n ; j++) { vindex[i+1] = j; //다음 노드에 모든 색을 시도해 본다. hamiltonian(i+1); }

18 Hamiltonian Circuits 되추적 알고리즘(2/2)
알고리즘 5.6: 해밀튼의 회로문제를 푸는 되추적 알고리즘 boolean promising(index i){ index j; boolean switch = true; if (i==n && !W[vindex[n]][vindex[1]]) switch = false; else if (i>1 && !W[vindex[i-1]][vindex[i]]) switch = false; else { j = 1; while(j<i && switch) { if (vindex[i] == vindex[j]) switch = false; j++; } return switch;

19 Hamiltonian Circuits vs. TSP
TSP Problem  Hamiltonian Circuits Problem Given a graph G with weighted edges, the problem of finding the Hamiltonian cycle of smallest possible weight is called the traveling salesman problem (TSP) on G. List of half of all possible Hamiltonian cycles, (for each route, the reverse route has the same cost)