기본 콘텐츠로 건너뛰기

해 탐색 알고리즘 : 백트래킹 알고리즘(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의 개수를 파악하고 맞다면 반환.
==================================================
라벨:

댓글

댓글 쓰기

이 블로그의 인기 게시물

11004 : K번째 수 [C++]

# include < iostream > # include < cstdio > # include < algorithm > int main ( ) { int * Number = new int [ 5000000 ] ; int N , K ; scanf ( " %d %d " , & N , & K ) ; for ( int i = 0 ; i < N ; i + + ) scanf ( " %d " , Number [ i ] ) ; std :: sort ( Number , Number + N ) ; printf ( " %d " , Number [ K - 1 ] ) ; return 0 ; }
댓글 쓰기
자세한 내용 보기

1149 : RGB Street Coloring (Dynamic Programming) [C,C++]

The key to this problem lies in understanding the principles. Let me explain the algorithm to solve the problem by using DP. First, you need the same storage space like input data's size. When you draw any color of the nth house, the space will contain the minimum value. If you paint the red in the second house, this value is sum of blue or green of the first house.  You must use DP because you must use the previous value.  Of course, you can also use the recursive algorithm to solve it. But if it gets bigger, it will take a lot of time.  If you paint the red in the nth house in the same way, you should add the lower value of the blue and green of the n-1th house.  Therefore, the minimum value can be found in the value of the storage space (n-1) index. <pesudo code> *Source of the problem =  https://www.acmicpc.net/problem/1149 *문제 출처 : BAEKJOON ONLINE JUDGE
댓글 쓰기
자세한 내용 보기

11478 : 서로 다른 부분 문자열의 개수 (미제) [C++]

# include < iostream > # include < vector > # include < string > using namespace std ; int main ( ) { string sInput ; getline ( cin , sInput , '\n' ) ; int Time = 1 ; int Count = 0 ; vector < string > Storage ; for ( int i = 0 ; i < sInput . size ( ) ; i + + ) { for ( int j = 0 ; ( j + Time - 1 ) < sInput . size ( ) ; j + + ) Storage . push_back ( sInput . substr ( j , Time ) ) ; Time + + ; } bool * Visited = new bool [ Storage . size ( ) * sizeof ( bool ) ] ; for ( int i = 0 ; i < Storage . size ( ) ; i + + ) { Visited [ i ] = true ; for ( int j = 0 ; j < Storage . size ( ) ; j + + ) { if ( i ! = j & & Storage [ i ] = = Storage [ j ] ) { Visited [ i ] = false ; Visited [ j ] = true ; break ; } } } for ( int i = 0 ; i < Storage . size ( ) ; i + + ) if ( Visited [ i ] ) Count ...
댓글 쓰기
자세한 내용 보기