목록backtracking (1)

포시코딩

백트래킹(backtracking)

백트래킹이란? 백트래킹 또는 퇴각검색이라고 불린다. 기법의 한 종류 제약 조건 만족 문제(Constraint Satisfaction Problem)에서 해를 찾기 위한 전략 해를 찾기 위해, 후보군에 제약 조건을 점진적으로 체크하다가, 해당 후보군이 제약 조건을 만족할 수 없다고 판단되는 즉시 backtrack하고, 바로 다른 후보군으로 넘어가며 결국 최적의 해를 찾는 방법 실제 구현 시, 고려할 수 있는 모든 경우의 수(후보군)를 상태 공간 트리(State Space Tree)를 통해 표현한다. 각 후보군을 DFS 방식으로 확인 상태 공간 트리를 탐색하면서, 제약이 맞지 않으면 해의 후보가 될만한 곳으로 바로 넘어가서 다시 탐색 Promising: 해당 루트가 조건에 맞는지 검사하는 기법 Pruning..
자료구조알고리즘/이론 2023. 4. 16. 18:21
이전 Prev 1 Next 다음