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

Slides:



Advertisements
Similar presentations
Ⅰ. 연산자 Ⅱ. 제어 구조. 연산자 : 할당 연산자 - 사용자가 정의한 변수에 임의의 값을 저장하는 기능 strvar = strVar1+ “ Hello ”
Advertisements

1. 2 차원 배열  배열은 동일한 데이터 유형으로 여러 개의 변수를 사용할 경우 같은 이 름으로 지정하여 간편하게 사용할 수 있도록 하는 것으로서 앞에서 1 차원 배열을 공부하였습니다.  2 차원 배열은 바둑판을 생각하면 되며, 1 차원 배열에서 사용하는 첨자를 2.
14 장. 그래프 알고리즘 Internet Computing KUT Youn-Hee Han.
이진 나무 구조 강윤섭 2008년 5월 23일.
4장 배열과 함수 한빛미디어(주).
주요 내용 기본 용어 그래프의 표현 오일러(Euler) 그래프와 해밀턴(Hamilton) 그래프
제2장 주파수 영역에서의 모델링.
Report #5 - due: 4/13 다음 10*5의 희소 행렬 A, B를 고려하라.
되추적(Backtracking).
9장. C 언어의 핵심! 함수. 9장. C 언어의 핵심! 함수 9-1 함수의 정의와 선언 main 함수 다시 보기 : 함수의 기본 형태 { } 그림 9-1.
연결리스트(linked list).
Report #2 - Solution 문제 #1: 다음과 같이 프로그램을 작성하라.
보고서 #7 (기한: 6/2) 2개의 스택, stk1, stk2를 이용하여 큐를 구현하라.
부분집합의 합 구하기 문제 부분집합의 합 구하기(Sum-of-Subsets) 문제
7장 배열 ②.
되추적(Backtracking).
누구나 즐기는 C언어 콘서트 제8장 배열.
 Branch-and-Bound (분기한정)
11장. 포인터 01_ 포인터의 기본 02_ 포인터와 Const.
SqlParameter 클래스 선문 비트 18기 발표자 : 박성한.
쉽게 풀어쓴 C언어 Express 제10장 배열 C Express Slide 1 (of 32)
알고리즘(Algorithm) – Backtracking (되추적)
제8장 배열 1부 8.1 배열 8.2 배열의 초기화 8.3 배열의 응용 8.4 정렬과 탐색 8.5 다차원 배열.
그래프의 기본 연산 깊이-우선 탐색(DFS; Depth-First Search) (1) 출발 정점 v를 방문
2007 1학기 11 프로젝트 기초 실습.
CHAP 10: 그래프(part 2) 순천향대학교 하상호.
보고서 #5(제출기한: 10/14) 다음 문제를 해결하시오.
11장. 1차원 배열.
13. 연산자 오버로딩.
CHAP 10:그래프 (2) 순천향대학교 하상호.
C 프로그래밍 C언어 (CSE2035) (Chap11. Derived types-enumerated, structure, and union) (1-1) Sungwook Kim Sogang University Seoul, Korea Tel:
사용자 함수 사용하기 함수 함수 정의 프로그램에서 특정한 기능을 수행하도록 만든 하나의 단위 작업
프로그래밍 개요
어서와 C언어는 처음이지 제14장.
박성진 컴퓨터 프로그래밍 기초 [09] 배열 part 1 박성진
자료구조: CHAP 7 트리 –review 순천향대학교 컴퓨터공학과 하 상 호.
Ch.03 Dynamic Programming (동적 프로그래밍 or 동적 계획법)
Report #3 - due: 4/6 100*100의 2개의 희소 행렬 A, B를 전달 받아서 이들의 덧셈을 구하고, 그 결과의 행렬 C를 반환하는 add_sparse_matrix(A, B, C)를 다음과 같이 작성하라. 희소 행렬은 sparse_matrix 타입으로 표현된다.
Quiz #7 다음 수들을 합병 정렬과 퀵 정렬 알고리즘을 이용하여 오름 차순으로 정렬하였을 때, 데이터 이동 회수를 각각 구하라. 여러분은 정렬 과정을 단계별로 보이면서 이동 회수를 추적해야 한다. 단, 퀵 정렬시에 피봇으로 배열의 왼쪽 첫 번째 원소를 선택한다. 5.
쉽게 배우는 알고리즘 7장. 상호 배타적 집합의 처리.
8장. 상호 배타적 집합의 처리.
주요 내용 왜 그래프인가? 기본 용어 그래프의 표현 오일러(Euler) 그래프와 해밀턴(Hamilton) 그래프
쉽게 풀어쓴 C언어 Express 제14장 포인터 활용 C Express Slide 1 (of 22)
쉽게 배우는 알고리즘 12장. 상태공간 트리의 탐색.
Term Projects 다음에 주어진 2개중에서 한 개를 선택하여 문제를 해결하시오. 기한: 중간 보고서: 5/30 (5)
Chapter6 : JVM과 메모리 6.1 JVM의 구조와 메모리 모델 6.2 프로그램 실행과 메모리 6.3 객체생성과 메모리
컴퓨터 프로그래밍 기초 - 10th : 포인터 및 구조체 -
컴퓨터 프로그래밍 기초 - 8th : 함수와 변수 / 배열 -
9장. C 언어의 핵심! 함수. 9장. C 언어의 핵심! 함수 9-1 함수의 정의와 선언 main 함수 다시 보기 : 함수의 기본 형태 { } 그림 9-1.
객체기반 SW설계 팀활동지 4.
수학10-나 1학년 2학기 Ⅱ.부등식의 영역 2. 연립부등식의 영역 (3/5) 부등식 영역 수업계획 수업활동.
Chapter 7. 그래프.
알고리즘 강의 슬라이드 5 되추적 Backtracking
보고서 #2(제출기한: 09/23) 다음 문제를 해결하시오. (7)
Ch.06 Branch-and-Bound (분기한정법) (Ch.05-7 포함)
05. General Linear List – Homework
 Branch-and-Bound (분기한정)
MST – Kruskal 알고리즘 (추상적)
[CPA340] Algorithms and Practice Youn-Hee Han
9 브라우저 객체 모델.
부분집합의 합 구하기 문제 부분집합의 합 구하기(Sum-of-Subsets) 문제
컴퓨터공학과 손민정 Computer Graphics Lab 이승용 교수님
트리 (Logical) Data Structures Linear list Tree Graph Linear structures
동적메모리와 연결 리스트 컴퓨터시뮬레이션학과 2016년 봄학기 담당교수 : 이형원 E304호,
제 4 장 Record.
쉽게 배우는 알고리즘 12장. 상태공간 트리의 탐색
[CPA340] Algorithms and Practice Youn-Hee Han
문제풀이방식-맹목적 탐색 Ai4.
(Permutations and Combinations)
교착 상태 해결 : 교착 상태 탐지 교착 상태 탐지(Deadlock Detection)
Presentation transcript:

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

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

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

부분집합의 합 구하기 문제 - 상태공간트리 상태공간 트리에서 유망하지 않은 노드의 조건 및 Pruning wi+1 : 수준 i에서 남아있는 가장 가벼운 원소값 (오름차순 정렬에 의한 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

부분집합의 합 구하기 문제 - 알고리즘 알고리즘: include[i]  w[i]를 포함하면 true, 포함하지 않으면 flase 저장 - W는 전역적으로 선언 - w[1], w[2], … : 오름차순으로 정렬된 각 원소값 - main() 내부에서 호출: SumOfSubsets(0, 0, total);  total 은 모든 원소의 합 추가적으로 weight 값을 매개변수로 넘겨주어야 함 weight 값을 매개변수로 넘겨받아야 함

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

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

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

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

지도와 평면 그래프 (Planar Graph) 결국 “m-색칠하기 문제”는… “최대 m개의 색을 사용하여 인접한 지역이 같은 색이 되지 않도록, 지도를 색칠하는 방법이 얼마나 있는지”를 구하는 문제, 또는 “최대 m개의 색을 사용하여 인접한 두 노드가 같은 색이 되지 않도록, Planar Graph의 각노드를 색칠하는 방법이 얼마나 있는지” 로 표현된다.

Graph Coloring – Backtracking Backtracking Strategy for 3-Coloring Problem

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);

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에 대해 “인접하고, 색이 같은지”의 여부를 조사한다.

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

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

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

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); }

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;

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)