Back Tracking
2019. 03. 26 (Tue)
끊임없이 파고들고 의심할 것
자료구조의 논리적인 모습, 구조적인 모습을 구분
I. 백트래킹
해를 찾는 도중에 해가 아니면 되돌아 가서 다시 해를 찾아 가는 기법
dfs를 기본 동작으로새로운 선택지의 집합 생성
현재까지의 결과를 기준으로 미래를 예측
최적화, 결정 문제 해결
- 결정 문제: 조건을 만족하는 해가 존재하는지 여부를 y or n로 답하는 문제
자신이 쥐고 있는 정보, 자기가 처리해야 할 정보가 필요
1. 가지치기
모든 후보를 검사하지 않는다.
어떤 노드가 유망(promising)하다면 경로를 추적. 아니면 경로를 제외
가지치기 논리는 사람마다, 문제마다 다름
가지치기: 어떤 노드에서 출발하는 경로가 해결책으로 이어지지 않을것 같으면 그 경로를 탐색하지 않음
모든 후보를 검사하는게 아니다
- 어떤 노드를 방문했을 때, 그 노드를 포함한 경로가 해답이 될 수 없다면 그 노드는 탐색하지 않음
2. dfs와 백트래킹의 차이
dfs: 비선형 자료구조를 빠짐없이 모두 순회
- 상태 공간 트리를 모두 탐색
백 트래킹: 어떤 경로가 해답으로 이어질지 않을 거 같으면 그 경로를 가지치기(prunning)
- 시도 횟수를 줄인다
동작방식은 같다. 불필요한 경로를 미리 차단하느냐 마냐의 차이
3. 구현 방법
상태 공간 트리에 dfs실행
노드가 유망한지 점검
노드가 유망하지 않으면, 부모 노드로 돌아가 탐색을 진행
4. N-Queen
queen을 배치하고
각 노드가 유망한지 점검
유망하지 않으면 가지치기 실행
5. powerset
공집합과 자기 자신을 포함한 모든 부분집합
원소갯수:n => powerset: 2^n