되추적(Backtracking).

Slides:



Advertisements
Similar presentations
1. 2 차원 배열  배열은 동일한 데이터 유형으로 여러 개의 변수를 사용할 경우 같은 이 름으로 지정하여 간편하게 사용할 수 있도록 하는 것으로서 앞에서 1 차원 배열을 공부하였습니다.  2 차원 배열은 바둑판을 생각하면 되며, 1 차원 배열에서 사용하는 첨자를 2.
Advertisements

알고리즘 기본 개념 정렬 알고리즘 탐색 알고리즘 알고리즘 복잡도.
이진 나무 구조 강윤섭 2008년 5월 23일.
과학 과제물 양파실험 5학년1반 박채빈.
T-tree 엄종진 강원대학교 컴퓨터과학과.
Report #5 - due: 4/13 다음 10*5의 희소 행렬 A, B를 고려하라.
RLC 회로 R L C 이 때 전류 i 는 R, L, C 에 공통이다.
Report #2 - Solution 문제 #1: 다음과 같이 프로그램을 작성하라.
7장 배열 ②.
되추적(Backtracking).
6장 그룹 함수.
07 그룹 함수 그룹 함수의 개념 그룹 함수의 종류 데이터 그룹 생성 HAVING 절.
P150 문제를 프로그래밍 할 것 Source file (헤더파일포함), 실행화면 (학번_이름_1.txt)
13 인덱스 인덱스의 개념 인덱스의 구조 인덱스의 효율적인 사용 방법 인덱스의 종류 및 생성 방법 인덱스 실행 경로 확인
제 11 장 다원 탐색 트리.
알고리즘(Algorithm) – Backtracking (되추적)
2007 1학기 11 프로젝트 기초 실습.
보고서 #5(제출기한: 10/14) 다음 문제를 해결하시오.
자료구조: CHAP 7 트리(1) 순천향대학교 컴퓨터공학과 하 상 호.
CHAP 7: 트 리 (1) 한 성 대 학 교 정보통신공학과 봉 정 식.
부분집합의 합 구하기 문제 부분집합의 합 구하기(Sum-of-Subsets) 문제
13 인덱스 인덱스의 개념 인덱스의 구조 인덱스의 효율적인 사용 방법 인덱스의 종류 및 생성 방법 인덱스 실행 경로 확인
탐욕적인 방법(Greedy Approach)
탐욕적인 방법(Greedy Approach)
9장. 특징 선택 오일석, 패턴인식, 교보문고, © 오일석, 전북대학교 컴퓨터공학.
Ⅲ. 이 차 방 정 식 1. 이차방정식과 그 풀이 2. 근 의 공 식.
CHAP 10:그래프 (2) 순천향대학교 하상호.
이미지 포렌식 작성자: liberte97.
사용자 함수 사용하기 함수 함수 정의 프로그램에서 특정한 기능을 수행하도록 만든 하나의 단위 작업
프로그래밍 개요
CHAP 9: 정렬 순천향대학교 컴퓨터학부 하 상 호.
군집 분석.
자료구조: CHAP 7 트리 –review 순천향대학교 컴퓨터공학과 하 상 호.
Tree & Heap SANGJI University Kwangman Ko
ROC curve Receiver-Operating Characteristic curve.
Quiz #7 다음 수들을 합병 정렬과 퀵 정렬 알고리즘을 이용하여 오름 차순으로 정렬하였을 때, 데이터 이동 회수를 각각 구하라. 여러분은 정렬 과정을 단계별로 보이면서 이동 회수를 추적해야 한다. 단, 퀵 정렬시에 피봇으로 배열의 왼쪽 첫 번째 원소를 선택한다. 5.
쉽게 배우는 알고리즘 7장. 상호 배타적 집합의 처리.
8장. 상호 배타적 집합의 처리.
Term Projects 다음에 주어진 2개중에서 한 개를 선택하여 문제를 해결하시오. 기한: 중간 보고서: 5/30 (5)
컴퓨터 프로그래밍 기초 - 10th : 포인터 및 구조체 -
합집합과 교집합이란 무엇인가? 01 합집합 두 집합 A, B에 대하여 A에 속하거나 B에 속하는 모든 원소로 이루어진 집합을 A와 B의 합집합이라고 하며, 기호 A∪B로 나타낸다. A∪B ={x | x∈A 또는 x∈B}
보고서 #7 (기한: 6/2) 2개의 스택, stk1, stk2를 이용하여 큐를 구현하라.
문자열 컴퓨터시뮬레이션학과 2015년 봄학기 담당교수 : 이형원 E304호,
객체기반 SW설계 팀활동지 4.
균형이진탐색트리 이진 탐색(binary search)과 이진 탐색 트리(binary search tree)와의 차이점
알고리즘 알고리즘이란 무엇인가?.
알고리즘 강의 슬라이드 6 분기한정법 Branch-and-Bound
알고리즘 강의 슬라이드 5 되추적 Backtracking
약식 진리표를 이용한 타당성 증명 진리표 그리기 방법의 한계
Excel 일차 강사 : 박영민.
DA :: 퀵 정렬 Quick Sort 퀵 정렬은 비교방식의 정렬 중 가장 빠른 정렬방법이다.
Ch.06 Branch-and-Bound (분기한정법) (Ch.05-7 포함)
5장. 선택 알고리즘.
05. General Linear List – Homework
 Branch-and-Bound (분기한정)
쉽게 배우는 알고리즘 2장. 점화식과 점근적 복잡도 분석
Chapter 10 데이터 검색1.
CHAP 9: 정렬 순천향대학교 컴퓨터학부 하 상 호.
[CPA340] Algorithms and Practice Youn-Hee Han
부분집합의 합 구하기 문제 부분집합의 합 구하기(Sum-of-Subsets) 문제
상관계수.
실습 UBLAB.
트리 (Logical) Data Structures Linear list Tree Graph Linear structures
동적메모리와 연결 리스트 컴퓨터시뮬레이션학과 2016년 봄학기 담당교수 : 이형원 E304호,
제 4 장 Record.
문제풀이방식-맹목적 탐색 Ai4.
(Permutations and Combinations)
교착 상태 해결 : 교착 상태 탐지 교착 상태 탐지(Deadlock Detection)
C++ Espresso 제15장 STL 알고리즘.
11. 트리.
Presentation transcript:

되추적(Backtracking)

되추적(Backtracking) 어떤 특정 집합에서 어떤 기준을 만족하도록 일련의 원소를 선택하는 문제를 위한 방법 체스

n-Queen 문제 n×n 서양 장기판에서 배치한 Queen들이 서로 위협하지 않도록 n개의 Queen을 배치하는 문제 깊이 우선 검색(depth-first search) 루트부터 검색하여 그것의 자식 노드를 방문하면 그 노드의 모든 후손 노드를 먼저 방문하는 방법

깊이 우선 검색 알고리즘

상태 공간 트리(state space tree) 4-Queens 문제 같은 행에 위치할 수 없다. 모든 경우의 수: 4x4x4x4 = 256 상태 공간 트리(state space tree)

가지친 상태 공간 트리(pruned state space tree) 4-Queen 문제 모든 후보를 검사? No! 되추적 기법 어떤 노드의 유망성을 점검한 후에 유망하지 않다고 결정되면 그 노드의 부모로 되돌아가(backtracking) 다음 자식 노드로 감 어떤 노드를 방문하였을 때 그 노드를 포함한 경로가 해답이 될 수 없으면 그 노드는 유망하지 않다고 하며, 반대로 해답의 가능성이 있으면 유망하다고 한다. 가지치기(pruning): 유망하지 않는 노드가 포함되는 경로는 더 이상 고려하지 않는다. 가지친 상태 공간 트리(pruned state space tree)

4-Queens 문제: 되추적 알고리즘 실제 트리를 만들 필요가 있을까?

4-Queens 문제: 되추적 알고리즘 두 알고리즘은 어떤 차이?

4-Queens 문제

상태 공간 트리

n-Queens promising 함수 같은 열과 대각선 피하기 대각선 판단: 열과 행의 차이가 같다. col(i): i번째 행에 있는 Queen의 열 위치 col(6) – col(3) = 4 – 1 = 3 = 6 – 3 col(6) – col(2) = 4 – 8 = -4 = 2 – 6

n-Queens 알고리즘

n-Queens 문제 분석 모든 노드의 수 두 개의 queen이 같은 열에 위치 할 수 없다. 대각선은? 즉, 유망하지 않은 노드 수까지 계산에 포함됨

그렇다면 어떻게 마디의 개수를 알 수 있을까? 유망한 마디의 개수를 정확하게 구하기 위한 유일한 방법은 실제로 알고리즘을 수행하여 구축된 상태 공간 트리의 마디 개수를 세어보는 수 밖에 없다. 그러나 이 방법은 진정한 분석 방법이 될 수 없다. 왜냐하면 분석은 알고리즘을 실제로 수행하지 않고 이루어져야 하기 때문이다.

마디의 개수

Monte Carlo 기법 되추적 알고리즘의 수행시간 추정 어떤 입력이 주어졌을 때 점검하게 되는 상태 공간 트리의 전형적인 경로를 무작위로 생성하여 이 경로 상에 점검하게 되는 노드의 수를 계산 이 과정을 여러 번 반복하여 계산된 결과의 평균값을 이용하여 알고리즘의 성능을 추정

Monte Carlo기법을 위한 요구조건 조건 1. 상태 공간 트리에서 같은 레벨에 있는 모든 노드의 유망성 여부를 점검하는 절차는 같아야 한다. 조건 2. 상태 공간 트리의 같은 레벨에 있는 모든 노드의 자식 수는 같아야 한다. n-Queens 문제?

Monte Carlo 알고리즘 무작위 경로 생성 ti: 레벨 i에 있는 노드의 자식 노드의 총 개수 총 노드 추정치 위 과정을 더 이상 자식 노드가 없을 때까지 반복한다. ti: 레벨 i에 있는 노드의 자식 노드의 총 개수 총 노드 추정치

0-1 배낭 채우기 되추적으로 하기전에…

부분집합의 합 구하기 부분집합의 합 구하기 문제(Sum-of-Subset) n개의 양의 정수 wi와 양의 정수 W가 있을 때 부분집합의 원소들의 합이 W가 되는 모든 부분집합을 찾는 문제 오름차순으로 무게 정렬

부분집합의 합 구하기 weight(w) total(t) X Node w+wi+1>W w+t<W

부분집합의 합 구하기: 알고리즘

0-1 배낭 채우기 되추적 기법을 이용한 0-1 배낭 채우기 문제 무게에 따른 노드의 유망 여부 ???에 따른 유망 여부 부분집합의 합 구하기와 동일한 형태의 상태 공간 트리 이용 무게에 따른 노드의 유망 여부 weight: 지금까지 포함한 item 무게의 총 합 weight > W: X 노드 weight = W: X 노드 자식 노드를 점검할 필요가 없음 ???에 따른 유망 여부

0-1 배낭 채우기 이익에 따른 유망 여부 item들을 pi/wi의 값에 따라 내림차순으로 정렬한다. 빈틈없이 배낭 채우기 문제를 이용하여 0-1 배낭 채우기 문제의 상한 값을 계산할 수 있다. 0-1 배낭 채우기 문제의 최대 이익은 빈틈없이 배낭 채우기 문제의 최대 이익보다 클 수 없다. profit: 지금까지 포함한 item들의 이익의 총 합 bound: profit의 상한 값(빈틈없이 배낭 채우기 문제를 통해 계산)

0-1 배낭 채우기: 예

기말 프로젝트 발표(001반) 12/3(월) 1조~8조, 12/5(수) 9조~15조 조당 발표시간 10분 이내 파워포인트로 발표자료 준비 도움을 받은 출처 명확히 프로그램 시연 원래의 알고리즘과 차이점 토의 발표 후에 자료 제출

기말 프로젝트 발표(002반) 12/3(월) 조당 발표시간 10분 이내 파워포인트로 발표자료 준비 도움을 받은 출처 명확히 프로그램 시연 원래의 알고리즘과 차이점 토의 발표 후에 자료 제출