기본 콘텐츠로 건너뛰기

해 탐색 알고리즘 : 백트래킹 알고리즘(Backtraking Algorithm)

해 탐색 알고리즘 중 하나.
해를 찾는 도중에 해가 아니면 되돌아가서 다시 해를 찾아 가는 기법
백트래킹 기법은 최적화(optimization) 문제와 결정(decision) 문제를 해결

결정 문제: 문제의 조건을 만족하는 해가 존재하는지의 여부를 ‘yes’ 또는 ‘no’가 답하는 문제
-미로 찾기
-해밀턴 경로 문제 (모든 꼭짓점을 한번씩 지나는 경로)
-부분 집합의 합 문제(집합의 부분집합 중에서 원소를 다 더한 값이 0이 되는 경우 있는지)

백트래킹 알고리즘은 기본적으로 상태공간트리를 이용한다.
어떤 노드의 유망성을 점검한 후, 유망하지 않다고 판단이 되면 
그 노드의 후손노드들에 대한 탐색을 중지하고, 부모노드로 돌아가서(Backtracking) 다른 후손노드에 대한 탐색을 계속하는 절차

깊이우선탐색(DSP)과 다른 점!
깊이우선탐색은 완결탐색
백트래킹 기법은 가지치기를 하여 완결탐색보다 효율적!

다시 정리하면,

Backtracking Algorithm
->기본 알고리즘
①상태공간트리에서 깊이우선탐색을 실시
②각 노드가 유망한지를 점검

->유망하지 않은 노드들은 검색을 하지 않음 (가지치기)
->유망한 노드에 대해서만 그 노드의 자식노드를 탐색
->깊이우선탐색(DSP)보다는 빠르지만 여전히 지수시간을 가짐

예로는 여행자 문제, N개의 퀸 문제(2의 n승의 체스판에 n개의 퀸을 놓는 문제)

==================================================
N개의 퀸 문제

BLANK, FILLED, CHECKED, QUEEN

1.모두 BLANK로 표시(Init)
2.행마다 CHECKED 표시(Check)
3.CHECKED마다 QUEEN 표시.(IsTherePossible)
4.QUEEN을 못 놓는 부분을 FILLED 표시(Fill)
5.QUEEN의 개수를 파악하고 맞다면 반환.
==================================================
라벨:

댓글

댓글 쓰기

이 블로그의 인기 게시물

1094 : 막대기 [C++]

# include < iostream > # include < vector > using namespace std ; int main ( ) { vector < int > Stick ; Stick . push_back ( 64 ) ; int Target ; cin > > Target ; int Last = 0 ; while ( true ) { if ( Target = = 64 ) break ; int Sum = 0 ; for ( int i = 0 ; i < Stick . size ( ) ; i + + ) Sum + = Stick [ i ] ; if ( Target = = Sum ) break ; else if ( Target < Sum ) { Stick [ Last ] / = 2 ; Sum = 0 ; for ( int i = 0 ; i < Stick . size ( ) ; i + + ) Sum + = Stick [ i ] ; if ( Target < = Sum ) continue ; else Stick . push_back ( Stick [ Last + + ] ) ; } } cout < < Stick . size ( ) ; ...
댓글 쓰기
자세한 내용 보기

2407 : 조합 (Dynamic Programming) [C++]

어려웠다. 문제를 풀면서 솔직히 이게 되려나?? 메모리 제한걸리려는게 아닌가 싶었는데 만들면서 최대한 메모리를 작게 만들었더니 맞았습니다! 주어진 입력 값은 최대 100인데, 입력값을 입력하면 오버플로우가 나므로 자릿수 배열을 만들어주어야 한다! 처음으로 한 생각은 재귀! (n == m || m == 0) 참이면 1 거짓이면 [n-1], [n]번째에 계속 접근하기 결과는 20이 넘어가면 엄청난 시간이 걸림. 두 번째 한 생각은 3차원 배열이었다. 2차원 배열에 또 배열을 만들어 자릿 수를 다 저장하려 했으나~ for문이 3개나 들어가서 시간이 엄청 오래걸렸음. 결국 2차원 배열이지만 3차원의 효과를 내게끔 선언하였다. 2차원배열이 원래이런 식이라면 1 11 121 1331 14641 내가 만든 배열은 111121133114641 즉 한 차원을 줄일 수 있었고, 각 원소에 대한 파스칼의 삼각형을 이용한 덧셈 공식은  그 줄의 자릿수 사이즈를 이용하여 전에 있는 줄에 접근하였다. DP 사용!! Answer[i] = Answer[i-Answer[i].size()] + Answer[i-Answer[i].size()+1] 그리고 저장한 자릿수들을 거꾸로 출력해주면 그것이 정답! Combination() : 각 줄의 번호만큼 자릿수를 가지는 벡터 생성, 계속 쓰는 Sum 벡터 생성 Increase() : 각 자릿수가 10이 넘어가면 올림을 해준다. GetSum() : 각 자릿수를 더해준다. GetAnswer() : DP, 올림, 출력  Combination :: Combination ( ) { this - > Sum . push_back ( 0 ) ; for ( int i = 1 ; i < = 101 ; i + + ) Sum . push_back ( S...
댓글 쓰기
자세한 내용 보기

11401 : 이항계수 3 (Dynamic Programming, Divide and Conquer) [C++]

1번, 2번 문제들과 확연히 차이나는 입력의 범위. 400만 ! DP를 사용해서 풀 수 없는 문제이다 . 하지만 DP가 쓰이긴 한다! 수학은 너무 어렵다. 곱셈의 역원을 공부해보다가 모르겠어서 도움을 구했다. 왜 곱셈의 역원을 구해야하는가? N! / (K! * (N-K)!) 에서 K! * (N-K)! 의 역원을 구해야 하기 때문! 곱셈의 역원을 구하는 정리인 페르마의 소정리를 이용하면 p가 1000000007 이지만 분할 정복을 이용한 제곱 수 계산 덕분에 logP 시간 소요. 분할 정복을 이용한 제곱 수 계산은 계속 써먹을 것 같아서 따로 올려놓았다. DP가 쓰이는 부분은 구해준 400만의 역원을 바탕으로 모든 역원을 구하는 부분이다. 그러므로 총 시간 소요는 O(N+LogP) long long BinomialCoefficient :: GetNum ( int N , int K ) { this - > Factorial [ 1 ] = 1 ; for ( int i = 2 ; i < = 4000000 ; i + + ) this - > Factorial [ i ] = ( this - > Factorial [ i - 1 ] * i ) % P ; this - > Invert [ 4000000 ] = this - > Pow_DC ( this - > Factorial [ 4000000 ] , P - 2 ) ; for ( int i = 4000000 - 1 ; i > 0 ; i - - ) this - > Invert [ i ] = ( this - > Invert [ i + 1 ] * ( i + 1 ) ) % P ; if ( N = = K | | K = ...
댓글 쓰기
자세한 내용 보기