Algorithm1 [Algorithm] 백트래킹(Backtracking)이란? Backtracking은 제약조건 만족문제에서 해를 찾는 방법이다. 개념 : 여러가지 경우의 수가 있는 문제에서 특정조건을 만족하는 찾는 데 있어, 조건을 탐색하다가 어느 순간 조건이 맞지 않는 것으로 판단되면 그 쪽의 경우의 수는 더이상 체크하지 않고 다른 경우의 수를 체크하는 것. 일종의 문제 푸는 전략으로, 알고리즘은 아니다. 고려할 수 있는 경우의 수를 상태공간트리로 표현 DFS 방식으로 후보군 확인 상태공간트리 탐색하며 제약조건을 만족하지 않으면 해당 부분에서 파생될 수 있는 모든 경우의 수를 더이상 보지 않는다. 이후 해의 후보가 될 만한 곳을 바로 넘어가서 탐색을 이어간다. 이를 통해 체크해야 하는 조건의 수를 확연히 줄이므로 계산량을 줄일 수 있는 기법이다. Promising : 조건 검사.. 2021. 3. 9. 이전 1 다음
