tech.log tech.log

Backtracking - 문제의 해결 방법을 탐색하다 가능성이 없다고 판단되는 후보를 즉시 가지치기(Pruning)하는 방식 - bfs 와 같은 방식으로 탐색하는 모든 방법으로, bfs는 backtracking의 골격을 이루는 알고리즘 - bfs 와 같은 재귀 방식으로 구현 - 운이 좋으면 시행착오를 거치지 않고 해답을 얻을 수 있지만, 최악의 경우 모든 경로를 거쳐야 함 - backtracking 에서 사용되는 가지치기(Pruning) 는 트리의 탐색 최적화 문제(제약 충족 문제(constraint satifaction problems))와도 연관 * 제약 충족 문제 : 수많은 제약 조건(constraint)을 충족하는 상태(States)를 찾아내는 수학 문제 : ex) 스토쿠, 8퀸 문제, 4색 문..