반응형
백트래킹 기법의 이해
백트래킹
- 백트래킹 또는 퇴각 검색이라 부른다.
- 제약조건 만족문제에서 해를 찾기 위한 전략이다.
- 해를 찾기 위해 후보군에 제약 조건을 점진적으로 체크하다가 해당 후보군이 제약 조건을 만족할 수 없다고 판단되는 즉시 백트랙(다시는 이 후보군을 체크하지 않게 표기) 하고, 바로 다른 후보군으로 넘어간다. 최적의 해를 찾는 방법
- 실제 구현시, 고려할 수 있는 모든 경우의 수(후보군)를 상태 공간 트리( state space tree )를 통해 표현
- 각 후보군을 DFS 방식으로 확인
- 상태 공간 트리를 탐색하면서 제약에 맞지 않으면 해의 후보가 될 만한 곳으로 넘어가서 탐색
- promising: 해당 루트가 조건에 맞는 지 검사하는 기법
- pruning( 가지치기 ): 조건에 맞지 않으면 포기하고, 다른 루트로 돌아가 탐색의 시간을 절약하는 기법
- 해를 찾기 위해 후보군에 제약 조건을 점진적으로 체크하다가 해당 후보군이 제약 조건을 만족할 수 없다고 판단되는 즉시 백트랙(다시는 이 후보군을 체크하지 않게 표기) 하고, 바로 다른 후보군으로 넘어간다. 최적의 해를 찾는 방법
참고 문헌
반응형
'알고리즘' 카테고리의 다른 글
| 백준 15652번 N과 M (4) (0) | 2020.12.02 |
|---|---|
| 백준 15650번 N과 M (2) 파이썬 ( 백트래킹 기초) (0) | 2020.12.02 |
| 백준 1011번 Fly me to the Alpha Centauri 파이썬 (0) | 2020.12.01 |
| 백준 20299번 3대 측정 (0) | 2020.12.01 |
| 백준 10870번 피보나치 수 5 (0) | 2020.11.30 |