📍Back Tracking 백트래킹, 퇴각검색 이란?
: 탐색 알고리즘 중 하나로,
문제의 해답을 찾는 동안 모든 가능한 경로를 탐색하면서 해답에 도달하는 과정을 나타낸다.
어떤 경로가 해답이 될 가능성이 없다고 판단되면 되돌아가서 다른 경로를 탐색하는 방식으로 작동한다.
주로 재귀적 접근 방식으로 해결하며 가능한 모든 경우의 수를 탐색한다.
1. 동작 방식
(1) 시작점 : 문제의 초기 상태에서 출발한다.
(2) 선택 : 각 단계에서 가능한 선택지 중 하나를 선택한다.
(3) 유효성 검사: 현재 선택이 문제의 제약 조건을 만족하는지 확인한다. 만족하지 않는다면, 해당 선택을 취소(되돌아가기)하고 다른 선택지를 시도한다. (2)번으로 돌아간다는 의미이다.
(4) 종료 조건 확인: 문제의 해답을 찾았는지 확인한다. 해답을 찾으면 탐색을 종료한다.
(5) 백트래킹: 더 이상 진행할 수 없거나, 유효하지 않은 상태가 발견되면 마지막 선택으로 돌아가 다른 선택지를 시도한다. (2)번으로 돌아간다.
2. 구현
모든 가능한 경우의 수를 고려하기 때문에 경우에 따라 수행시간이 길어질 수 있다.
-> 효율적인 구현과 pruning 기법을 통해 탐색 범위를 줄이는 것이 중요한다.
- Pruning 기법이란 ?
가지치기로, 불필요한 경로를 미리 차단하여 탐색 공간을 줄이는 기법이다. 이 기법을 사용하면 알고리즘의 효율성을 크게 향상시킬 수 있다.
DFS 방식으로 구현하는 것이 더 편리하다. 따라서 재귀함수로 구현한다.
3. DFS VS Back Tracking
(공통점) 둘 다 재귀적으로 해결한다.
(차이점)
- DFS는 모든 경로를 탐색한다. (완전 탐색)
- Back Trackting은 조건이 제시되기 때문에 모든 경로를 탐색하지 않고 경우의 수를 줄일 수 있다.
4. 문제
- N-Queens 문제
