백트래킹 기법

‘백트래킹(Backtracking) 기법’은 해를 찾는 도중에 ‘막히면’ 되돌아가서 다시 해를 찾아가는 기법이다.
백트래킹 기법은 최적화(optimization) 문제와 결정(decision) 문제를 해결할 수 있다.
결정 문제란 문제의 조건을 만족하는 해가 존재하는지의 여부를 yes or no로 답하는 문제이다.
예시로 미로 찾기, 해밀토니안 사이클, 서양 장기 여왕 말, 부분 집합의 합 문제 등이 있다.

이전 포스팅에서 근사 알고리즘으로 해결한, NP-완전 문제인 여행자 문제 (TSP)를 백 트래킹 기법으로 해결하는 과정을 살펴본다.

TSP를 위한 백트래킹 알고리즘은 다음과 같다.
단, bestSolution은 현재까지 찾은 가장 우수한 해이며, (tour,tour의 거리)로 나타낸다.
이 때, tour는 점의 순서이다.

tour = [시작점] // tour는 점의 순서(sequence)
bestSolution = (tour, ∞) // tour는 시작점만 가지므로 거리는 가장 큰 상수로 일단 초기화한다.
BacktrackTSP(tour)

TSP를 위한 백트래킹 알고리즘은 다음과 같다.
단, bestSolution은 현재까지 찾은 가장 우수한 해이며, (tour,tour의 거리)로 나타낸다.
이 때, tour는 점의 순서이다.

tour = [시작점] // tour는 점의 순서(sequence)
bestSolution = (tour, ∞) // tour는 시작점만 가지므로 거리는 가장 큰 상수로 일단 초기화한다.
BacktrackTSP(tour)

 

if (tour가 완전한 해이면)
  if (tour의 거리 < bestSolution의 거리) // 더 짧은 해를 찾았으면
     bestSolution = (tour, tour의 거리)
else {
  for (tour를 확장 가능한 각 점 v에 대해서){
    newTour = tour + v 		// 기존 tour의 뒤에 점 v를 추가한다.
    if (newTour의 거리 < bestSolution의 거리)
    BacktrackTSP(newTour)
  }
}

• • 시작점이 A이므로 tour=[A], bestSolution = ([A], ∞)이다.
    BacktrackTSP(tour)를 호출한다.
  • line 1 : [A]가 완전한 해가 아니므로, line 5의 for-루프가 수행
  • line 5 : tour=[A]를 확장할 수 있는 점은 B, C, D, E이다.
    각 점에 대해서 for-루프가 수행된다.
  • 점 B에 대해서 수행되는 경우를 가정한다.
    line 6 : newTour = [A,B], newTour의 거리는 2가 된다.
    line 7~8 : newTour의 거리 2가 bestSolution ∞보다 짧으므로, BacktrackTSP([A,B])를 재귀 호출한다.
    • line 1 : [A,B]가 완전한 해가 아니므로, line 5의 for-루프가 수행
    • line 5 : tour=[A,B]를 확장할 수 있는 점은 C, D, E이다.
      각 점에 대해서 for-루프가 수행된다.
    • 점 C에 대해서 수행되는 경우를 가정한다.
      line 6 : newTour = [A,B,C], newTour의 거리는 5가 된다.
      line 7~8 : newTour의 거리 5가 bestSolution ∞보다 짧으므로, BackTrackTSP([A,B,C])를 재귀 호출한다.
      …
      이와 같이 계속 탐색을 진행하면 다음과 같은 첫 번째 완전한 해를 찾는다.
      이 때, bestSolution=([A,B,C,D,E,A],30)이다.

이는 모든 경우를 다 검사하여 해를 찾는 완결탐새의 시간복잡도와 같다.
그러나 일반적으로 백트래킹 기법은 ‘가지치기’를 하므로 완결탐색보다 훨씬 효율적이다.