백트래킹 기법 (Backtracking)

백트래킹 기법 (Backtracking)

해를 찾는 도중에 막히면(해가 아니면) 되돌아가서 다시 해를 찾아가는 기법

깊이 우선 탐색을 통해 해를 찾음

TSP(Traveling Salesman Problem)를 위한 백트래킹 알고리즘

tour = [] : 방문한 지점(방문 순서)

bestSolution = (tour, tour의 거리) : 현재까지 찾은 가장 거리가 짧은 해

 

BacktrackTSP(tour) 함수

① tour가 완전한 해일 때 (모든 지점을 다 방문했을 때)

② tour가 완전하지 않을 때 (모든 지점을 방문하지 않았을 때)

 

① tour가 완전한 해일 때 (모든 지점을 다 방문했을 때)

만약 tour의 거리가 bestSolution의 거리보다 작으면 bestSolution = (tour, tour의 거리)

 

② tour가 완전하지 않을 때 (모든 지점을 방문하지 않았을 때)

tour에서 확장 가능한 각각의 점 v에 대해서 아래의 반복문 수행

newTour = tour + v  // 기존 tour의 뒤에 점 v 추가

만약 newTour의 거리가 bestSolution의 거리보다 작으면 BackTrackTSP(newTour) 수행

 

참고) 알기 쉬운 알고리즘

 

시작점 : A

tour = [A], bestSolution = ([A], ∞)  // 초기에 tour는 시작점만 가지고 있으므로 거리는 가장 큰 상수로 초기화

 

BacktrackTSP(tour) 호출

tour가 완전하지 않음 → A에서 확장 가능한 점은 B, C, D, E

네 점에 대해 각각 아래의 반복문 수행

먼저 B일 때,

newTour = [A, B], newTour의 거리 = 2

newTour의 거리(2)가 bestSolution의 거리(∞)보다 작으므로 BacktrackTSP([A, B]) 수행

참고) 알기 쉬운 알고리즘

 

 

tour가 완전하지 않음 → [A, B]에서 확장 가능한 점은 C, D, E

세 점에 대해 각각 아래의 반복문 수행

먼저 C일 때,

newTour = [A, B, C], newTour의 거리 = 5

newTour의 거리(5)가 bestSolution의 거리(∞)보다 작으므로 BacktrackTSP([A, B, C]) 수행

참고) 알기 쉬운 알고리즘

 

 

계속 탐색을 하다보면 tour가 완전해짐(모든 점들을 방문)

처음에 bestSolution의 거리를 무한대로 초기화했으므로 30으로 update

bestSolution = ([A, B, C, D, E, A], 30)

참고) 알기 쉬운 알고리즘

 

 

이런 식으로 완전하지 않은 tour에 대해서 점점 확장해 가면서 더 짧은 bestSolution의 거리를 찾아감

만약 tour가 완전하지 않아서 확장가능한 점이 남았는데 bestSolution보다 그 tour의 거리가 더 길다면 그 아래로 탐색할 필요 X (가지치기)