알고리즘 이론/백트래킹 기법1 백트래킹(backtracking) 기법의 이해 1. 백트래킹(Backtracking) 기법 - 제약 조건 만족 문제에서 해를 찾기 위한 전략 - 후보군에 제약조건을 체크하고 조건이 맞지 않으면, 그 다음 후보군으로 바로 이동하는 과정을 통해 해를 찾는 전략 (일일이 모든 경우를 체크하지 않고, 조건에 맞지 않으면 세부검증 없이 backtracking 과정을 수행 이해가 간다해도 말로 표현하기가 어렵다..) - 모든 경우의 수(후보군)는 상태공간트리(State Space Tree)로 표현한다 - 각 후보군을 DFS 방식으로 확인 - SST를 탐색하며, 제약조건을 체크하고 이를 만족하지 못할 경우, 다음 후보군으로 이동 - Promising(조건체크): 해당하는 경우가 제약 조건을 만족하는지 검사하는 기법 - Pruning(가지치기): 조건과 맞지 않으.. 2020. 10. 13. 이전 1 다음