Backtracking 이란 ? #

Backtracking(백트래킹, 퇴각검색, 전수조사)은 문제 해결을 위한 알고리즘(Algorithm) 중 하나로 "모든 경우의 수"를 따지면서 문제를 해결해 나가는 방법이다.

Back tracking 알고리즘은 모든 경우의 수를 따지기 때문에 "전수 조사"라고도 불리며, 일반적으로 문제를 해결하기 위한 적절한 알고리즘이 없는 경우에 많이 쓰인다.

Backtracking을 이용한 문제 해결 방법 #

기본 해결방법 #

Backtracking은 기본적으로 문제를 해결하기 위해 모든 경우의 수를 찾아다니며 조사하는 방법으로 주로 재귀적 알고리즘이나, Stack을 이용하여 구현한다. 마방진의 해를 구하는 방법을 backtracking으로 해결한다고 가정해보자.

위 그림을 보면 1을 놓는 위치부터 9를 놓는 위치까지 진행 규칙을 정하여 모든 경우의 수에 대해 작업을 수행한다. 맨 처음 나온 경우의 수에서 만약 작업이 완료되지 않을 경우 한 단계 위로 올라가서(7의 위치가 정해짐) 다음 경우의 수를 다시 계산한다. 만약에 바로 이전 단계로 가서도 해결되지 않는 경우 다시 한 단계 더 이전 단계로 이동하여 경우의 수를 계산한다.

이와 같은 방법으로 모든 경우의 수를 고려하여 정답을 찾는다. 다만 이러한 방법으로 위치를 계산할 경우 최악의 경우에는 9!의 시도가 필요하다

Branch and bound #

기존의 backtracking 방법의 경우 한정된 집단에서 무조건 해를 구할 수는 있으나, 이미 정답이 아님에도 불구하고 과정을 끝까지 수행하므로 답을 구하는 과정의 효율이 매우 떨어진다. 그러한 점을 방지하고자 각 단계에서 검증을 거쳐 "답이 아니다"라고 결론이 나는 경우, 이후의 과정을 수행하지 않음으로써 정답을 구하는 과정의 비효율을 줄일 수 있다. 마방진을 구하는 backtracking 중간과정에서 조금 더 자세히 알아보자.

두 번째 줄 맨 왼쪽 매트릭스를 보면 6이 나올 때 이미 2줄이 완성된다. 마방진은 모든 가로/세로/대각선의 합이 동일해야 하므로 이미 해당 위치에 6이 들어가면 정답이 아니게 된다.

그러므로 더 이상 아래 단계를 진행하지 않고 바로 윗 단계로 올라가서 다음 경우의 수를 조사하며 이 과정을 반복한다.

Branch and bound 알고리즘은 위와 같이 검증 과정을 통해 이후 불필요한 계산을 줄여 나가는 방법을 계산한다. worst case의 Complexity 상으로는 비슷한 값을 지니지만 평균 Complexiry로 볼 때 상당량의 복잡도를 줄일 수 있다.

Heuristric(휴리스틱) #

Suggested Pages #

• 0.897 삭제요청
• 0.033 객체클레스
• 0.024 SASS
• 0.017 바이오잉크
• 0.008 Chained exceptions
• 0.008 오픈 테스트
• 0.008 Q&A
• 0.004 지침
• 0.002 DEG를 구하는 방법에 대한 질문
• More suggestions...