되추적(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에 있는 노드의 자식 노드의 총 개수 총 노드 추정치

그래프 색칠하기 m-색칠하기 문제(m-coloring): 인접한 노드는 같은 색깔로 색칠할 수 없다는 제약 조건 하에 무방향 그래프의 노드를 최대한 m개의 색으로 색칠하는 문제 m = 3

평면 그래프(Planar Graph) 평면 상에서 이음선(edge)들이 서로 엇갈리지 않게 그릴 수 있는 그래프 지도에서 각 지역을 그래프의 정점으로 하고, 한 지역이 어떤 다른 지역과 인접해 있으면 그 지역들을 나타내는 정점들 사이에 이음선을 그으면, 모든 지도는 그에 상응하는 평면그래프로 표시할 수 있다

그래프 색칠하기: 상태 공간 트리

그래프 색칠하기: 분석 상태 공간 트리의 노드의 총 수 실제 노드 수의 추정 Monte Carlo 기법 사용

해밀튼의 회로 외판원 문제 해밀토니안 순환 경로 해밀토니안 순환경로 문제 연결된 무방향 그래프에서 주어진 정점에서 출발하여 모든 정점을 정확하게 한번 방문하고 출발한 정점으로 되돌아오는 경로 해밀토니안 순환경로 문제 연결된 무방향 그래프에서 해밀토니안 순환경로를 찾는 문제

해밀튼의 회로

해밀튼의 회로 되추적 방법 경로 상의 i번째 정점은 그 경로 상의 (i - 1)번째 정점과 반드 시 이웃 해야 한다. (n - 1)번째 정점은 반드시 0번째 정점(출발점)과 이웃 해야 한다. i번째 정점은 처음 i - 1개의 정점이 될 수 없다.

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 배낭 채우기: 예