[알고리즘] 백트래킹 알고리즘

네이버 어학 사전

"오던 길을 따라 되돌아 나오다"라는 뜻

 

 

여러 후보해 중에서 특정 조건을 충족시키는 모든 해를 찾는 알고리즘.

 

 

후보해 속에서 해를 찾아가는 과정

1. 루트에서부터 출발

 

2. 현재 위치한 부분해에서 선택이 가능한 다음 부분해의 목록을 얻습니다.

 

3. 2번에서 얻은 목록의 부분해들을 하나씩 방문합니다.

 

4. 방문한 부분해가 해가 요구하는 조건을 만족시키면 그 자리에서 2번 3번 과정을 수행, 그렇지 않으면 그 이전 부분해로 돌아 나와 다른 부분해를 시도

 

5. 최종해를 얻을 때까지, 또는 모든 경우의 수를 확인해도 해가 없을음 확인했을 때까지 2~4번 과정을 반복