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

==================================================

MrCodeMania