되추적(Backtracking).

Presentation on theme: "되추적(Backtracking)."— Presentation transcript:

1 되추적(Backtracking)

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

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

4 깊이 우선 검색 알고리즘

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

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

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

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

9 4-Queens 문제

10 상태 공간 트리

11 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

12 n-Queens 알고리즘

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

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

15 마디의 개수

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

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

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

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

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

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

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

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

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

25 0-1 배낭 채우기: 예

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

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