알고리즘_백 트래킹 (해 탐색)

1. 백 트래킹

해를 찾는 도중에 해가 아닐 경우 되돌아간다.
깊이 우선 탐색
최적화 문제와 결정문제를 해결 가능.

1.2. 여행자 문제를 위한 백 트래킹 알고리즘

Bestsolution = 현재까지 찾은 가장 우수한 해
tour = 거리

backtrackTSP()
{
	if(tour가 완전한 해이면)
		if(tour의 거리 < bestsolution의 거리)
   	 		bestsolution - (tour, tour의 거리)
	else
    {
		for(tour를 확장 가능한 각 점v에 대해서)
        {
    		newTour = [tour, c]
        	if(newTour의 거리 < bestsolution의 거리) //백트래킹 V이후의 내용은 버림
        		backtrackTSP(newTour)
    	}
	}
}

1.2.1 여행자 문제 백트래킹 예제

데이터의 갯수 n
시간복잡도 = O(n^2)
완결탐색과 시간복잡도는 같으나 가지치기를 하기 때문에 좀 더 빠를 수 있다.