( ु ´͈ ᵕ `͈ )ु JS:: 백트래킹(Backtracking) 알고리즘과 완전탐색 알고리즘

백트래킹(Backtracking) 개념

가능한 모든 해결책을 탐색하면서 조건에 맞지 않으면 돌아가 다시 시도한다.
문제 해결을 위한 모든 경우의 수를 고려하는 동시에,
조건에 맞지 않는 경로라면 더 이상 진행하지 않는 방식을 채택해 효율성을 높인다.

미로에서 출구를 찾는 과정을 상상해보자.
갈림길에서 길을 선택하다가 막다른 길에 도달하면 되돌아와 다른 길을 시도한다.

 

※ Backtrack은 '되돌아'라는 의미이다.

동작방식

1. 하나를 선택한다.
2. 선택한 길이 유효한지 검사한다.
3. 유효하다면 다음 결정 지점으로 이동한다.
4. 유효하지 않다면, 이전 결정 지점으로 돌아가 다른 선택을 한다.

 

사용하는 경우

 

모든 경우의 수를 고려하면서도 불필요한 경로를 배제하기 때문에 문제를 효율적으로 해결할 수 있다.
가능한 해결책의 수가 많을 때 유용하다.

 

백트래킹(Backtracking)과 완전탐색

두 알고리즘 모두 가능한 모든 경우의 수를 탐색하는 것은 동일하지만,
완전탐색은 제약조건이 없는 반면 백트래킹은 조건에 맞지 않는 경로는 중간에 포기하고
이전 단계로 돌아가는 점에서 차이가 있다.