- 해를 찾는 도중에 '막히면' 되돌아가서 다시 해를 찾아가는 기법
- 최적화 문제와 결정 문제를 해결할 수 있음
- 결정문제: 문제의 조건을 만족하는 해가 존재하는지의 여부를 예/아니오로 답하는 문제.
- 경로가 해결책으로 이어질 것 같지 않으면 가지치기. 불필요한 경로 조기 차단
- 깊이 우선 탐색은 모든 경로를 추적하므로 경우의 수가 너무 많으면 처리 불가능.당첨 단말 노드 찾기
- 루트에서 갈 수 있는 노드 선택
- 꽝 노드까지 도달하면 최근의 선택으로 되돌아와서 다시 시작
- 더 이상의 선택지가 없다면 이전의 선택지로 돌아가서 다른 선택
8 queen problem
- 퀸 8개를 8x8크기의 체스판 안에 서로를 공격할 수 없도록 배치하는 모든 경우 구하기.
후보해: 64C8
- 4queen 문제로 축소.
- 일단 각 행에 하나씩 배치. 열 위치만 구하면 됨.
- 모든 후보해를 검사하지 않음. 어떤 노드가 유망하지 않으면 backtrack하여 다음 자식 노드로 감.
1) 상태 공간트리에 대한 깊이 우선 탐색 실시
2) 방문하는 노드가 유망한지 여부 점검
3) 선택노드가 유망하지 않으면 돌아가서 부모노드부터 다시 점검
- 깊이우선탐색 155개, 백트래킹 27개. 경제적.
부분집합
- Power set: 어떤 집합의 공집합과 자기 자신을 포함한 모든 부분집합
: 구하고자 하는 어떤 집합의 원소개수가 n일 경우 부분집합의 개수는 2^n
백트래킹 기법으로 power set 구하기
- 일반적인 백트래킹 기법 이용
순열
- 원소 개수 n
동전 거스름돈 문제
- coinchange 재귀 호출.
microCT_applications