제약조건만족문제1 Advanced Algorithm - Backtracking 1. 백트래킹이란? - 완전탐색 알고리즘의 하나다. - 완전탐색을 하는 도중, 현재의 탐색이 무의미하다고 판단이되면 되돌아가는 알고리즘이다. - 그래서 퇴각 검색이라 부르기도 한다. 2. 백트래킹의 로직 - 백트래킹은 제약조건 만족 문제(Constraint Satisfaction Problem)에서 해를 찾기 위한 전략이다. 해를 찾기위해서 어떤 후보군을 대상으로 제약조건을 체크하다가 해당 후보군이 제약조건을 만족할 수 없다고 판단되면, 그 즉시 backtrack(다시는 해당 후보군을 체크하지 않을 것을 표시)한 후, 다른 후보군으로 넘어가는 방식으로 최종적으로 최적의 해를 찾는 전략이다. 백트래킹 전략에 의해 연산의 대상이 되는 후보군이 적어지고, 그만큼 시간복잡도가 줄어드는 것이다. a) 어떻게 구현.. 2020. 10. 5. 이전 1 다음
