[CPA340] Algorithms and Practice Youn-Hee Han

Slides:



Advertisements
Similar presentations
알고리즘 기본 개념 정렬 알고리즘 탐색 알고리즘 알고리즘 복잡도.
Advertisements

이진 나무 구조 강윤섭 2008년 5월 23일.
4장 배열과 함수 한빛미디어(주).
자료구조: CHAP 7 트리(1) 순천향대학교 컴퓨터공학과 하 상 호.
Maximum Flow.
T-tree 엄종진 강원대학교 컴퓨터과학과.
되추적(Backtracking).
각 행 (row) 에서 같은 첨자가 있는 곳은 비워두고, 그 밖에 cell에 수준수 (level) 또는 반복수를 기입
9장. C 언어의 핵심! 함수. 9장. C 언어의 핵심! 함수 9-1 함수의 정의와 선언 main 함수 다시 보기 : 함수의 기본 형태 { } 그림 9-1.
Report #2 - Solution 문제 #1: 다음과 같이 프로그램을 작성하라.
트리 이 현 직
Internet Computing KUT Youn-Hee Han
부분집합의 합 구하기 문제 부분집합의 합 구하기(Sum-of-Subsets) 문제
강의 #7 트리(Tree).
CHAP 7:트리 C로 쉽게 풀어쓴 자료구조 생능출판사 2011.
되추적(Backtracking).
Chapter 02 순환 (Recursion).
제 11 장 다원 탐색 트리.
알고리즘(Algorithm) – Backtracking (되추적)
그래프의 기본 연산 깊이-우선 탐색(DFS; Depth-First Search) (1) 출발 정점 v를 방문
2007 1학기 11 프로젝트 기초 실습.
보고서 #5(제출기한: 10/14) 다음 문제를 해결하시오.
제 5 장 트 리 5.1 트리 5.2 이진 트리 5.3 스레드 이진 트리.
자료구조: CHAP 7 트리(1) 순천향대학교 컴퓨터공학과 하 상 호.
자료구조: CHAP 4 리스트 (3) 순천향대학교 컴퓨터공학과 하 상 호.
프로그래밍 랩 – 7주 리스트.
CHAP 7: 트 리 (1) 한 성 대 학 교 정보통신공학과 봉 정 식.
부분집합의 합 구하기 문제 부분집합의 합 구하기(Sum-of-Subsets) 문제
13. 탐색 트리.
Tree & Heap SANGJI University Kwangman Ko
CHAP 7:트리 C로 쉽게 풀어쓴 자료구조 생능출판사 2005.
9장. 특징 선택 오일석, 패턴인식, 교보문고, © 오일석, 전북대학교 컴퓨터공학.
Ⅲ. 이 차 방 정 식 1. 이차방정식과 그 풀이 2. 근 의 공 식.
CHAP 10:그래프 (2) 순천향대학교 하상호.
프로그래밍 개요
자료구조: CHAP 7 트리 –review 순천향대학교 컴퓨터공학과 하 상 호.
Tree & Heap SANGJI University Kwangman Ko
CHAP 7:트리 C로 쉽게 풀어쓴 자료구조 생능출판사 2005.
Ch.06 Branch-and-Bound (분기한정법) (Ch.05-7 포함)
Quiz #7 다음 수들을 합병 정렬과 퀵 정렬 알고리즘을 이용하여 오름 차순으로 정렬하였을 때, 데이터 이동 회수를 각각 구하라. 여러분은 정렬 과정을 단계별로 보이면서 이동 회수를 추적해야 한다. 단, 퀵 정렬시에 피봇으로 배열의 왼쪽 첫 번째 원소를 선택한다. 5.
8장. 상호 배타적 집합의 처리.
쉽게 배우는 알고리즘 12장. 상태공간 트리의 탐색.
햄스터 미로찾기 광운대학교 로봇학부 박광현.
[CPA340] Algorithms and Practice Youn-Hee Han
컴퓨터 프로그래밍 기초 - 10th : 포인터 및 구조체 -
균형이진탐색트리 이진 탐색(binary search)과 이진 탐색 트리(binary search tree)와의 차이점
CHAP 12 : 탐색 C로 쉽게 풀어쓴 자료구조 Slide 1 (of 27).
알고리즘 알고리즘이란 무엇인가?.
알고리즘 강의 슬라이드 5 되추적 Backtracking
약식 진리표를 이용한 타당성 증명 진리표 그리기 방법의 한계
에어 PHP 입문.
DA :: 퀵 정렬 Quick Sort 퀵 정렬은 비교방식의 정렬 중 가장 빠른 정렬방법이다.
Ch.06 Branch-and-Bound (분기한정법) (Ch.05-7 포함)
5장. 선택 알고리즘.
 Branch-and-Bound (분기한정)
탐색 (Search) 컴퓨터가 문제를 자율적으로 해결하기 위해 해 혹은 해에 이르기 위한 경로를 찾아가는 과정
Chapter 07 트리.
9 브라우저 객체 모델.
부분집합의 합 구하기 문제 부분집합의 합 구하기(Sum-of-Subsets) 문제
트리 (Logical) Data Structures Linear list Tree Graph Linear structures
쉽게 배우는 알고리즘 12장. 상태공간 트리의 탐색
수치해석 ch3 환경공학과 김지숙.
[CPA340] Algorithms and Practice Youn-Hee Han
문제풀이방식-맹목적 탐색 Ai4.
아날로그 신호를 디지털 신호로 변환하는 A/D 변환기 A/D 변환 시 고려하여 할 샘플링 주파수 D/A 변환기
(Permutations and Combinations)
교착 상태 해결 : 교착 상태 탐지 교착 상태 탐지(Deadlock Detection)
7 생성자 함수.
6 객체.
11. 트리.
Presentation transcript:

[CPA340] Algorithms and Practice Youn-Hee Han http://link.kut.ac.kr Ch.05 Backtracking (되추적) [CPA340] Algorithms and Practice Youn-Hee Han http://link.kut.ac.kr

되추적(backtracking)? 갈림길에 표시를 해 두었더라면…  간단히 말해서 되추적은 갈림길에 표시를 해 두고 막다른 골목에 다다르면 갈림길까지 되돌아가서 다른 골목으로 가보는 방법이다.

되추적의 개요 Backtracking 은 제약조건 만족 문제 (Constraint Satisfaction Problem) 에서 해를 찾기 위한 전략 중 하나이다. Backtracking 은 올바른 답을 구할 때까지 각각의 가능성을 시도한다. 해를 찾기 위한 깊이우선 탐색 (Depth First Search) 과 관련성이 깊다. 탐색도중에, 새로운 탐색이 무의미하다고 판단되면, 다른 새로운 탐색이 가능한 선택 포인트 (choice point) 로 backtrack 하여 새로운 탐색을 시도하게 된다. 더 이상의 선택 포인트가 존재하지 않게되면, 탐색은 실패로 끝난다

트리의 탐색 Tree Traversal (트리 순회) process each node once and only once in a predetermined sequence Two general approach Depth-first traversal (depth-first search: DFS) Breadth-first traversal (breadth-first search: BFS, level-order) 1 4 6 2 5 7 3 1 5 6 2 3 7 4 depth-first traversal breadth-first traversal

트리의 탐색 Depth-first traversal (깊이 우선 탐색) in Binary Tree The processing proceeds along a path from the root through one child to the most distant descendent of that first child before processing a second child. Preorder traversal Root  left subtree  right subtree Inorder traversal Left subtree  root  right subtree Postorder traversal Left subtree  right subtree  root

깊이우선검색 (Depth-first search) (1/2) 루트 노드(root node)를 먼저 방문한 뒤, 그 노드의 모든 후손노드(descendant)들을 차례로(보통 왼쪽에서 오른쪽으로) 방문한다. (= preorder tree traversal). 재귀호출의 Return 이 되추적(Backtracking)과 같은 역할을 한다. void depth_first_tree_search(node v){ node u; visit v; for (each child u of v) // from left to right depth_first_tree_search(u) }

깊이우선검색 (Depth-first search) (2/2) 예제

n-Queens 문제 n-Queens 문제: 4-Queens 문제: n×n 서양장기판(chess) 에 배치되는 n개의 Queen들이 서로 위협하지 않도록 배치하는 문제 기준: 어떤 두 Queen도 서로를 위협하지 않아야 한다. 같은 행이나, 같은 열이나, 같은 대각선 상에 위치하지 않아야 한다. 4-Queens 문제: 4개의 Queen을 서로 상대방을 위협하지 않도록 4  4 서양장기(chess)판에 위치시키는 문제

무작정 알고리즘으로 구현할 때 고려해야 할 Candidate Solution 개수 n-Queens 문제 4-Queens 문제: 첫째 행에 올 수 있는 경우의 수 = 4 둘째 행에 올 수 있는 경우의 수 = 4 셋째 행에 올 수 있는 경우의 수 = 4 넷째 행에 올 수 있는 경우의 수 = 4 4  4  4  4 = 256가지 무작정 알고리즘으로 구현할 때 고려해야 할 Candidate Solution 개수

4-Queens 문제의 상태공간트리 상태공간트리: State Space Tree (i,j)  i번째 queen 이 j번째 열에… 첫 번째 queen이 놓일 수 있는 곳 두 번째 queen이 놓일 수 있는 곳 세 번째 queen이 놓일 수 있는 곳 네 번째 queen이 놓일 수 있는 곳 후보답: Candidate Solution

상태공간트리의 이용 루트 노드에서 리프 노드(leaf node)까지의 경로는 해답후보(candidate solution)가 되는데, 깊이우선검색을 하여 그 해답후보 중에서 제한조건을 만족하는 해답을 찾을 수 있다. 그러나 단순하게 이 방법을 사용하면 해답이 될 가능성이 전혀 없는 노드의 후손노드(descendant)들도 모두 검색해야 하므로 비효율적이다.

상태공간트리의 이용 노드의 유망성(promising): 전혀 해답이 나올 가능성이 없는 노드는 유망하지 않다 (non-promising)고 하고 (해당 노드의 서브트리 검색은 무의미), 그렇지 않으면 유망하다(promising)고 한다.

상태공간트리의 이용 되추적이란? 되추적 알고리즘은 상태공간트리에서 깊이우선검색을 실시하는데, 어떤 노드의 유망성을 점검한 후, 유망하지 않다고 판정이 되면 (그 노드의 후손 노드(서브 트리)들에 대한 검색을 중지하고, 그 노드의 부모노드(parent)로 돌아간다(“backtrack”). 그런 다음, 다시 후손 노드에 대한 검색을 계속하게 되는 절차이다. 되추적 알고리즘은 상태공간트리에서 깊이우선검색을 실시하는데, 유망하지 않은 노드들은 가지쳐서(pruning) 검색을 하지 않으며, 유망한 노드에 대해서만 그 노드의 자식노드를 검색한다.

되추적 알고리즘의 개념 [Summary] 되추적 알고리즘의 절차 1. 상태공간트리의 깊이우선검색을 실시한다. 1. 상태공간트리의 깊이우선검색을 실시한다. 2. 각 노드가 유망한지를 점검한다. 3. 만일 그 노드가 유망하지 않으면, 가지치기를 수행하고, 그 노드의 부모노드로 돌아가서 검색을 계속한다. void checknode(node v){ node u; if (promising(v)) // 각 응용마다 promising 함수는 다르다. if (there is a solution at v) write the solution; else for (each child u of v) checknode(u); } [Note] 실제 트리를 만들어 알고리즘을 수행할 필요는 없다. 즉, 상태공간트리는 묵시적으로(implicitly) 존재한다.

4-Queens 문제의 되추적 상태공간트리 (1/2) 순수한 깊이우선검색의 검색 노드 수 = 155 노드 (전체는 (1+4+16+64+256)개이나, 그 이전에 솔루션(2-4-1-3)이 찾아지므로…) 되추적방법에 의한 검색 노드 수 = 27 노드

4-Queens 문제의 되추적 상태공간트리 (2/2)

4-Queens 문제: 개선된 되추적 알고리즘 void checknode(node v) { node u; if (promising(v)) if (there is a solution at v) write the solution; else for (each child u of v) checknode(u); } void expand(node v){ node u; for (each child u of v) if (promising(u)) if (there is a solution at u) write the solution; else expand(u); //유망한 마디만을 확장 } 이전 알고리즘은 유망하지 않은 마디의 활성화레코드를 불필요하게 생성 개선된 알고리즘은 유망성 여부의 점검을 노드를 방문하기 전에 실시하므로, 그만큼 방문할 노드의 수가 적어져서 더 효율적이다. 그러나 일반 알고리즘이 이해하기는 더 쉽고, 일반 알고리즘을 개량된 알고리즘으로 변환하기는 간단하다. 따라서, 앞으로 본 강의에서의 모든 되추적 알고리즘은 일반 알고리즘과 같은 형태로 표시한다.

n-Queens Problem – 알고리즘 (1/3) 유망함수 구현을 위해, col[i]가 i-번째 행에서 Queen이 놓여있는 열이라 하자. 먼저, 같은 열에 있는지 검사하기 위해서는 col[i] = col[k]이 성립하는지 검사하면 된다. 다음으로, 같은 대각선에 있는지 검사하기 위해서는 다음 등식이 성립하는지 검사하면 된다. |col[i] – col[k]| = |i – k| 열의 차이 = 행의 차이

n-Queens Problem – 알고리즘 (2/3) A Backtracking Algorithm for the n-Queens Problem void checknode(node v){ node u; if (promising(v)) if (there is a solution at v) write the solution; else for (each child u of v) checknode(u); } 최상위 수준 호출: queens(0); void queens(index i){ index j; if(promising(i)) if(i == n) System.out.print(col[1] through col[n]); else for(j=1 ; j <= n ; j++) { col[i+1] = j; // 다음 위치 선택 queens(i+1); }

n-Queens Problem – 알고리즘 (3/3) A Backtracking Algorithm for the n-Queens Problem (계속) boolean promising(index i){ index k = 1; boolean switch = true; while(k < i && switch) { // k <= n if(col[i] == col[k] || abs(col[i]-col[k]) == i-k) switch = false; k++; } return switch;

n-Queens Problem – 분석 1 (1/2) 상태공간트리 전체에 있는 노드의 수를 구함으로서, Backtracking에서 활용할 상태공간트리의 노드의 개수의 상한 (upper bound) 을 구한다. 깊이가 i인 노드의 개수는 ni개 이고, 이 트리의 깊이는 n이므로, 노드의 총 개수는 상한(upper bound)은 다음과 같다. Recall

n-Queens Problem – 분석 1 (2/2) 그러나 이 분석은 별 가치가 없다. 왜냐하면 되추적함으로서 점검하는 노드 수를 줄이게 되기 때문이다. 즉, 되추적을 통해 점검 노드 수를 얼마나 줄였는지는 상한값을 구해서는 전혀 알 수 없다.

n-Queens Problem – 분석 2 유망한 노드만 세어서 상한을 구한다. 두 번째는 기껏해야 남은 7열 중에서만 위치시킬 수 있다. 세 번째는 남은 6열 중에서 위치시킬 수 있다. 이런 식으로 계속했을 경우 노드의 수는 1 + 8 + 8  7 + 8  7  6 + …+ 8! = 109,601가 된다. (여기서 1 = root) 이 결과를 일반화 하면 유망한 노드의 수의 상한은 다음과 같다.

n-Queens Problem – Discussion 앞서의 두 가지 분석 방법은 알고리즘의 복잡도를 정확히 얘기 해주지 못하고 있다. 왜냐하면: 대각선을 점검하는 경우를 고려하지 않았다. 따라서 실제 유망한 노드의 수는 훨씬 더 작을 수 있다. 실제로 복잡도 결과에 포함된 노드 중에서 유망하지 않은 노드가 훨씬 더 많을 수 있다.

n-Queens Problem – 분석 3 유망한 노드의 개수를 정확하게 구하기 위한 유일한 방법은 실제로 알고리즘을 수행하여 구축된 상태공간트리의 노드의 개수를 세어보는 수 밖에 없다.

n-Queens Problem – 분석 3 되추적 없이 상태공간트리를 깊이우선검색으로 모든 노드를 검색하는 알고리즘 제안한 되추적 알고리즘 (같은 행, 열, 대각선에 올 수 없다는 제한을 이용) checknode() 대신 expand()를 사용하여 유망노드 검색을 먼저 하는 알고리즘

n-Queens Problem – 분석 4 그러나 이 방법은 진정한 분석 방법이 될 수 없다. 왜냐하면 분석은 알고리즘을 실제로 수행하지 않고 이루어져야 하기 때문이다. (또한, 입력 개수 n은 매번 달라질 수 있기 때문이다.) 그럼, 정확한 분석은 어떻게 하나?  Monte Carlo Technique (확률적 알고리즘)

Monte Carlo Technique? Monte Carlo 기법은 어떤 입력이 주어졌을 때 점검하게 되는 상태공간트리의 “전형적인” 경로를 무작위(random)로 생성하여 그 경로 상에서 검사하게 되는 시뮬레이션 기법 상기 과정을 여러 번 반복하여 나오는 결과의 평균치를 추정치로 사용한다. ( 확률적 복잡도를 구한다.) 대학원 과정에서 심도있게 배울 수 있음 [Note]Monte Carlo: 모나코의 유명한 도박의 도시