백트래킹

@ 백트래킹(Backtracking)

 

백트래킹 (Backtracking)

해를 찾는 도중(완전탐색 중, 모든 경우를 따져보고 있는데...)
그 길이 막히면(더 고려해 볼 필요가 없을 때)
가던 길 경로를 포기하고
되돌아와 다른 길로부터 가며 ... 해를 찾는 기법

최적화(optimization) ,결정(decision) 문제 해결 (서로 상호 연결된 같은 문제...)

 

최적화(optimization) 문제 : 조건에 만족하는 (최단으로 가는 경로) 답을  찾으세요. 

결정(decision) 문제  : 문제의 조건에 만족하는 해의 존재 있냐 없냐 (예스 올 노)

 

예제 문제 )

미로찾기, n-Queen , 부분집합, 순열 관련 문제, 4컬러링

 

백트래킹 구현 방법 ) DFS, BFS 를 하는데 가지치기를 할 뿐...
                             유망성 보고, 함수를 재귀호출을 하겠다. 

 

@ DFS (깊이우선탐색) , BFS (너비우선탐색) 와 백트래킹의 차이

그래프 탐색(모든 정점 가는)을 하냐의 유무 : 유(DFS,BFS) 무(백트래킹)

백트래킹의 목적은 최적 해를 찾는데 , 완전탐색으로 다 보지 않고, 빨리 찾으려고 하는 것