되추적 ( Backtracking)

완전탐색 - 브루토포스 (exhaustive/brute-force search)을 개선한 기법이다. 

후보해 들을 단계적으로 만들어가는 과정에서 후보해들을 평가한다. 만약 한 후보해가 최종해가 될 수 없다고 판단되면 탐색을 멈추고 다른 후보해를 탐색한다. -> 최적화문제와 결정문제 해결이 가능하다

 

DFS(Depth First Search) 또는 그와 같은 스타일의 탐색을 총칭한다.

 

되추적(Backtracking) 이란?

-어떤 노드의 유망성을 점검한 후, 유망하지 않다고 판정이 되면 그 노드의 부모 노드로 돌아가서 다음 자식 노드에 대한 탐색을 계속한다.

 

 

이렇게 가능성을 보고 가지치기를 하며 가능한 것들을 판단한다.

 

 

다음 예시로는 순열 생성 되추적이 있다. 이것의 알고리즘은 다음과 같고 Java로는 다음과 같다. 

 

 

 

public class Main {
    static int count =0;
    // 순열을 생성하는 함수
    public static void permute(int[] A, int k, int N) {
        // 순열이 완성된 경우 출력
        if (k == N) {
            for (int i = 0; i < N; i++) {
                System.out.print(A[i] + " ");
            }
            System.out.println();
            return;
        }

        // A[k]에 들어갈 값을 결정
        for (int i = 1; i <= N; i++) {
            if (promising(A, k, i)) {
                A[k] = i; // A[k]를 i로 설정
                System.out.println("A[k]= "+A[k]+ " k = "+k);
                System.out.println("i= "+i);
                permute(A, k + 1, N); // 다음 단계 재귀 호출
            }
        }
        count++;
        System.out.println("count= "+count);
    }

    // A[k]에 값 i를 넣을 수 있는지 확인
    public static boolean promising(int[] A, int k, int i) {
        for (int j = 0; j < k; j++) {
            if (A[j] == i) {
                return false; // 이미 사용된 값
            }
        }
        return true;
    }

    // 메인 함수
    public static void main(String[] args) {
        int N = 3; // N개의 숫자로 순열 생성
        int[] A = new int[3]; // 순열을 저장할 배열
        permute(A, 0, 3); // 초기 호출
    }
}

 

 

 

다음은 해밀토니안 회로찾기를 되추적으로 하는 예시이다.

 

 

 

public class Main {
    static int n; // 그래프 정점의 개수
    static int[][] G; // 그래프의 인접 행렬
    static int[] path; // 현재까지의 경로

    public static void main(String[] args) {
        // 그래프 초기화 예제
        n = 4; // 정점 개수
        G = new int[][] {
                {0, 1, 1, 0},
                {1, 0, 1, 1},
                {1, 1, 0, 1},
                {0, 1, 1, 0}
        };
        path = new int[n];
        path[0] = 0; // 시작 정점 설정
        hamiltonian(1); // 탐색 시작
    }

    static void hamiltonian(int i) {
        if (i == n) {
            // 경로가 완성되었고, 마지막 정점이 시작 정점으로 돌아올 수 있는 경우
            if (G[path[i - 1]][path[0]] == 1) {
                printPath();
            }
            return;
        }
        // 다음 정점을 시도
        for (int j = 1; j < n; j++) {
            path[i] = j;
            if (valid(i)) {
                hamiltonian(i + 1);
            }
        }
    }

    static boolean valid(int i) {
        // 경로의 마지막 정점이 첫 정점과 연결되지 않는 경우
        if (i == n && G[path[i - 1]][path[0]] == 0) {
            return false;
        }
        // 현재 정점과 이전 정점이 연결되지 않은 경우
        if (i > 0 && G[path[i - 1]][path[i]] == 0) {
            return false;
        }
        // 이미 방문한 정점인지 확인
        for (int j = 0; j < i; j++) {
            if (path[j] == path[i]) {
                return false;
            }
        }
        return true;
    }

    static void printPath() {
        for (int i = 0; i < n; i++) {
            System.out.print(path[i] + " ");
        }
        System.out.println(path[0]); // 마지막에 시작 정점으로 돌아오는 경로 추가
    }
}

 

 

외판원 문제도 되추적알고리즘으로 풀 수 있다.