백트래킹이란?

백트래킹, DFS/BFS, 브루트 포스간의 개념이 너무 헷갈렸다. 처음에는 백트래킹의 의미를 브루트 포스와 유사한 것으로 잘못 알고 있었다.

 

백트래킹(역주척)은 어떤 노드의 유망성을 점검하고 유망하지 않으면 그 노드의 부모 노드로 돌아가, 다른 자식 노드를 탐색하는 것이다. 백트래킹은 가지치기를 통해 많은 루트들을 배제하기 때문에 DFS에 비해 풀이 시간이 단축된다는 장점이 있다.  이는 스택에 자식 노드를 넣기 전에 유망한지 확인하고 스택에 넣는다는 것을 의미한다. 

 

그에 비해 DFS는 좀 더 원시적인 방법으로, 모든 경우의 수를 확인하는 완전 탐색 방법이다. DFS는 재귀 호출을 통해서 깊은 곳으로 계속 방문해 나가는 방식이다. 모든 경우를 방문하는 만큼, 유망하지 않은 루트로도 가서 비효율적인 결과가 나올 수도 있다. 

 

즉, 백트래킹은 대표적인 완전 탐색 방법인 DFS에 가지치기를 이용해 시간복잡도를 줄이는 방법이라고 할 수 있겠다. BFS로도 구현할 수는 있지만, 구조상 DFS와 연관이 깊다. 

 

백트래킹 기법들 - 최적해보다 나빠지면 그만두기. 간단한 휴리스틱을 이용한 가지치기

 

낙관적인 휴리스틱, 문제를 과소평가하는 휴리스틱 - 항상 실제 답 이하이면서도 가능한 한 큰 값을 구해야 한다. 

 

EX) TSP(외판원 문제) - 여러 도시들이 있고 한 도시에서 다른 도시로 이동하는 비용이 모두 주어졌을 때, 모든 도시들을 단 한 번만 방문하고 원래 시작점으로 돌아오는 최소 비용의 이동 순서를 구하는 문제

=> 남은 도시를 모두 방문할 필요 없이, 가장 멀리 있는 도시 하나만 방문했다가 시작점으로

=> 남은 도시들을 방문하는 방법이 꼭 일렬로 연결된 형태가 아니어도 됨 

 

 아직 방문하지 않은 도시들에 대해 인접한 간선 중 가장 짧은 간선의 길이를 더하기, 아직 방문하지 않은 도시를 방문하려면 인접한 간선 중 하나를 타고 가야 하므로, 이들 중 가장 짧은 간선의 길이만을 실제 최단 경로 이하의 값이 된다. 

solve()에서 각 도시마다 가장 가까운 도시까지의 거리를 미리 계산해 둔 뒤, simpleHeuristic()에서 방문하지 않은 도시들마다 이 값을 더해 반환하기 

 

//각 도시의 인접한 간선 중 가장 짧은 것을 미리 찾아둔다.
double minEdge(MAX);
//가장 단순한 형태의 휴리스틱
double simpleHeuristic(vector<bool>& visited) {
    double ret = minEdge[0];
    //마지막에 시작점으로 돌아갈 때 사용할 간선
    for (int i = 0; i < n; i++) {
        if (!visited[i]) ret += minEdge[i];
    }
    return ret; 
}
//path: 지금까지 만든 경로, visited: 각 도시의 방문 여부, currentLength: 지금까지 만든 경로의 길이 
void search(vector<in>& path, vector<bool>& visited, double currentLength) {
    //단순한 휴리스틱을 이용한 가지치기 
    if (best <= currentLength + simpleHeuristic(visited)) return;
    //나머지 부분은 생략... 
}
 
double solve() {
    //simpleHeuristic을 이용한 초기화
    for (int i = 0; i < n; i++) {
        minEdge[i] = INF;
        for (int j = 0; j < n; j++) {
            if (i != j) minEdge[i] = min(minEdge[i], dist[i][j]);
        }
    }
}