Backtracking

🐤 되추적 기법

• 어떤 마디의 유망성을 점검한 후, 유망하지 않다고 판정 되면 그 마디의 부모 마디로 돌아가서 다음 후손 마디에 대한 검색을 계속 하는 절차
• 문제 풀이 과정을 트리로 나타낼 수 있음
• 유망성
  • 전혀 해답이 나올 가능성이 없음: 유망하지 않다 (non-promising)
  • 해답이 나올 가능성이 있음: 유망하다 (promising)

• 어떤 특정 집합에서 어떤 기준을 만족하도록 일련의 원소를 선택하는 문제를 해결할 때 사용
  • n-Queens 문제, 미로 문제 등
• 깊이 우선 검색 (depth-first search)을 변형한 기술
  • 루트부터 검색하여 그것의 자식 노드를 방문하면, 그 노드의 모든 후손 노드를 먼저 방문하여 검색하는 방법
  • 보통 왼쪽 자식부터 먼저 방문

🐤 트리 순회

• 트리 구조에서 각각의 노드를 정확히 한 번만, 체계적인 방법으로 방문하는 과정
• 노드를 방문하는 순서에 따라 분류

• 전위 순회 (preorder)
  • 루트 노드에서 시작
  • 노드 방문
  • 왼쪽 서브 트리 전위 순회
  • 오른쪽 서브트리 전위 순회
  • = 깊이 우선 순회

    preorder(node) {
      print node.value
      if node.left != null
      then preorder(node.left)
      if node.right != null
      then preorder(node.right)
    }
    

• 중위 순회 (inorder)
  • 왼쪽 서브 트리 중위 순회
  • 노드 방문
  • 오른쪽 서브 트리 중위 순회

    inorder(node) {
      if node.left != null
      then inorder(node.left)
      print node.value
      if node.right != null
      then inorder(node.right)
    }
    

• 후위 순회 (portorder)
  • 왼쪽 서브 트리 후위 순회
  • 오른쪽 서브 트리 후위 순회
  • 노드 방문

    postorder(node) {
      if node.left != null
      then postorder(node.left)
      if node.right != null
      then postorder(node.right)
      print node.value
    }
    

• 레벨 순서 순회
  • 모든 노드를 낮은 레벨부터 차례대로 순회
  • 인접한 노드부터 차례대로 순회
  • = 너비 우선 순회

🐤 깊이 우선 검색

void DepthFirstTreeSearch(node v) {
    node u;
    visit v;
    for(each child u of v)
        DepthFristTreeSearch(u);
}

일반 되추적 알고리즘

void checknode(node v) {
    if(promising(v)) {
        if(there is a solution at v)
            write the solution;
        else {
            for(each child u of v)
                checknode(u);
        }
    }
}

🐤 N-Queens 문제

• n*n 서양 장기판에서 배치한 Queen들이 서로 위협하지 않도록 n개의 Queen을 배치하는 문제
• 일련의 원소: Queen을 배치한 n개의 위치
• 기준: 어떤 두 Queen도 서로를 위협하지 않아야 함

상태 공간 트리 State Space Tree

• 해답의 후보들의 모임: 해 모임 (solution space)
• 문제 해결 과정의 중간 상태를 각각 한 노드로 나타낸 트리
• 루트 마디에서 리프 마디까지의 경로는 해답 후보가 됨
  • 깊이 우선 검색을 통해 그 해답 후보 중에서 해답을 찾을 수 있음
• 그러나, 이 방법을 사용하는 해답이 될 가능성이 전혀 없는 마디의 후손 마디들도 모두 검색해야 하므로 비효율적임

4-Queens 문제

• 4개의 Queen을 서로 상대방을 위협하지 않도록 4x4 체스 판에 위치시키는 문제
• 서로 상대방을 위협하지 않기 위해서는 같은 행이나, 같은 열이나, 같은 대각선 상에 위치하지 않아야 함
• 무작정 알고리즘
  • 각 Queen을 각각 다른 행에 할당한 후에, 어떤 열에 위치해야 해답을 얻을 수 있는지 차례대로 점검하는 방법
• 이 때, 각 Queen은 4개의 열 중에 한 열에 위치할 수 있기 때문에 점검해야 하는 경우의 수는 4 x 4 x 4 x 4 = 256가지

관찰

• 모든 후보를 검색하는 것은 비효율적
• 되추적 기법: 어떤 노드의 유망성을 점검한 후, 유망하지 않다고 결정되면 그 노드의 부모로 되돌아가 (backtracking) 다음 자식 노드를 이용하여 문제의 답을 찾는 기법
• 어떤 노드를 방문했을 때 그 노드를 포함한 경로가 해답의 가능성이 있으면 유망하다고 함
• 유망하지 않는 노드가 포함되는 경로는 더이상 고려하지 않으며, 이 과정을 가지치기(pruning)라고 함
• 방문한 노드만을 나타낸 상태 공간 트리: 가지친 상태 공간 트리

일반 되추적 알고리즘

void checknode(node v) {
    node u;
    if(promising(v)) {
        if(there is a solution at v)
            write the solution;
        else
            for(each child u of v)
                checknode(u);
    }
}

• 각 응용마다 promising 함수는 다름

4-Queen 상태 공간 트리

• 검색하는 마디의 개수
  • 순수한 깊이 우선 검색: 155마디
    • 1 root + 1 (1,1) + 4 (1,1) 자식노드 + 16 그 자식노드 + 64 그 자식노드 (1,1)로부터 내려오는 모든 노드 + 1 (1,2) + 3 (2,1)-(2,3) + 12 그 세 개의 노드의 자식노드 + 48 그 자식노드들 (1,3)까지 합한 것 + 1 (2,4) + 1 (3,1) + 3 (4,1)(4,2)(4,3)
  • 되추적 기법: 27마디

🐤 n-Queens 문제

• 4-Queens 문제를 확장
• promising 함수
  • 같은 열에 있으면 안됨
  • 대각선에 있는 경우
    • col[i] : i번째 행에 있는 Queen의 열 위치 (이미 놓여짐)
    • col[6] - col[3] = 4 - 1 = 3 = 6 - 3

    • col[6] - col[2]

      =

      4 - 8

      =

      -4

      = 6-2

promising 함수

bool promising(index i) {
    index k = 1;
    bool p = true;
    while(k < i && p) {
        if(col[i] == col[k] || abs(col[i] - col[k]) == i-k)   // 같은 열인지 or 대각선인지 : 열의 차이 = 행의 차이
            p = false;
        k++;
    }
    return p;
}

n-Queens 알고리즘

void queens(index i) {
    index j;
    if(promising(j)) {
        if(i == n) 
            print col[1] through col[n];
        else {
            for(j = 1; j <= n; j++) {
                col[i+1] = j;
                queens(i+1);
            }
        }
    }
}

• j는 각 행의 열
• i = 0, 1 : 무조건 true

문제 분석

• n-Queens 문제의 모든 노드의 수
  $1 + n + n^2 + … + n^n = \frac{n^{n+1}-1}{n-1}$
  • ex) n = 8 -> 19,173,961 개의 노드
  • 실제로 모든 노드를 검사하지 않음
• 유망한 노드의 수
  • 두 개의 queen은 같은 열에 위치할 수 없음
    $1 + n + n(n-1) + n(n-1)(n-2) + … + n!$
  • ex) n = 8 -> 46,233 개의 노드

정리

• 위 두가지 분석 방법(되추적)은 알고리즘의 복잡도를 정확히 표현해주지 못함
• 왜냐하면
  • 대각선을 점검하는 경우를 고려하지 않음
    • 실제 유망한 마디의 수는 더 적을 수 있음
  • 유망하지 않은 마디를 포함하고 있는데, 실제로 해석의 결과에 포함된 마디 중 유망하지 않은 마디가 훨씬 더 많을 수 있음

🐤 부분집합의 합 구하기 문제

• 문제: n개의 양의 정수 wi가 있을 때, 부분집합의 원소들의 합이 W가 되는 모든 부분집합을 찾는 문제

• ex) n = 5, W = 21, w1 = 5, w2 = 6, w3 = 10, w4 = 11, w5 = 16

  • w1 + w2 + w3 = 21
  • w1 + w5 = 21
  • w3 + w4 = 21
  • 답: {w1, w2, w3}, {w1, w5}, {w3, w4}

• 상태 공간 트리는 위 그림과 같음
• 이때 무게를 오름차순으로 정렬하여 접근하면 유망하지 않은 노드를 쉽게 식별할 수 있음

• ex) n = 4, W = 13, w1 = 3, w2 = 4, w3 = 5, w4 = 6

의사코드

void SumOfSubsets(index i, int weight, int total) {
    if(promising(i)) {
        if(weight == W) 결과 출력;
        else {
            include[i+1] = true;   // 왼쪽 자식노드: 다음 숫자 포함
            SumOfSubset(i+1, weight+w[i+1], total-w[i+1]);
            include[i+1] = false;  // 오른쪽 자식노드: 다음 숫자 포함X
            SumOfSubset(i+1, weight, total-w[i+1]);
        }
    }
}

• include[i]: 어느 item을 방문했는지 true / false로 저장

bool promising(index i) {
    return (weight+total >= W) && (weight==W || weight+w[i+1] <= W);
}

• weight: 지금까지 포함한 wi 들의 합
• total: 아직 고려하지 않은 wi 들의 합

문제 분석

• 상태 공간 트리의 최대 노드 개수
  $1 + 2 + 2^2 + … + 2^n = 2^{n+1} -1$

🐤 그래프 색칠하기 문제

• m-색칠하기 문제
  • 인접한 노드는 같은 색으로 칠할 수 없다는 제약 조건 하에 무방향 그래프의 노드를 최대한 m개의 색으로 색칠하는 문제
• 응용: 평면 그래프
  • 임의의 두 간선이 서로 교차되지 않도록 그래프를 평면에 그릴 수 있는 경우

• 그래프 색칠하기 문제의 상태 공간 트리

알고리즘

• 문제: 비방향 그래프에서 m개의 색만 사용하여 인접한 정점이 같은 색이 되지 않게 정점을 색칠하는 모든 방법을 구하라.
• 입력: 정점 n, 색 m, 인접행렬 W[i][j]
• 결과: 최대로 m개의 색을 가지고, 인접한 정점이 같은 색이 되지 않게 그래프에 색칠하는 가능한 모든 경우

의사코드

void m_coloring(index i) {
    int color;
    if(promising(i)) {
        if(i == n)
            print output;
        else {
            for(color = 1; color <= m; color++) {   // 다음 정점에 가능한 모든 색 시도
                vcolor[i+1] = color;
                m_coloring(i+1);
            }
        }
    }
}

• 0번, 1번 노드: true
• vcolor: 색의 종류

bool promising(index i) {
    index j;
    bool switch;
    switch = true;
    j = 1;
    while(j < i && switch) {   // 이미 칠해진 노드 확인
        if(W[i][j] && vcolor[i] == vcolor[j])
            switch = false;    // 인접한 노드가 같은 색일 경우
        j++;
    }
    return switch;
}

• j: 이미 칠해진 노드
• switch: promising 여부

문제 분석

• 상태 공간 트리 상의 마디의 총 수 (색의 수)
  $1 + m + m^2 + … + m^n = \frac{m^{n+1}-1}{m-1}$

🐤 해밀토니안 순환경로 문제

• 연결된 무방향 그래프에서 주어진 정점에서 출발하여 모든 정점을 정확하게 한 번 방문하고 출발한 정점으로 되돌아오는 경로

• 상태 공간 트리에서 노드의 유망 여부
  • 경로에 있는 i번째 정점은 i-1번 정점과 인접해야 함
  • n-1번째 정점은 0번째 정점(출발 정점)과 인접해야 함
  • i번째 정점은 그 앞에 오는 i-1개의 정점들 중 하나가 될 수 없음
• Vindex[n] : 방문한 정점 리스트

알고리즘

• 문제: 연결된 비방향 그래프에서 해밀턴 회로를 모두 구하라.
• 입력: 정점 수 n, 정점이 n개인 비방향 그래프 W[i][j];
• 결과: 해밀턴 회로를 이루는 모든 경로

의사코드

void hamiltonian(index i) {
    index j;
    if(promising(i)) {
        if(i == n-1)
            print output;
        else {
            for(j = 2; j <= n; j++) {      // 다음에 오는 모든 정점들 시도
                vindex[i+1] = j;
                hamiltonian(i+1);   // promising 여부 확인
            }
        }
    }
}

bool promising(index i) {
    index j;
    bool switch;
    if(i == n-1 && !W[vindex[n-1]][vindex[0]])  
        switch = false;      // n-1번째 정점과 0번째 정점 인접해야 함
    else if(i > 0 && !W[vindex[i-1]][vinde[i]])
        switch = false;      // root가 아닌 i번째 정점과 i-1번째 정점은 인접해야 함
    else {
        switch = true;
        j = 1;
        while(j < i && switch) {        // 이미 선택된 정점인지 확인
            if(vindex[i] == vindex[j])    
                switch = false;
            j++;
        }
    }
    return switch;
}

문제 분석

• 상태 공간 트리의 최대 노드 수
  $1 + (n-1) + (n-1)^2 + … + (n-1)^{(n-1)} = \frac{(n-1)^n -1}{n-2}$

🐤 몬테카를로 기법

• 되추적 알고리즘의 수행시간 추정
• 어떤 입력이 주어졌을 때 점검하게 되는 상태 공간 트리의 “전형적인” 경로를 무작위로 생성하여 그 경로 상에 있는 마디의 수를 셈

• 이 과정을 여러 번 반복하여 나오는 결과의 평균치를 추정치로 함

• 다음 두 조건을 반드시 만족해야 함
  • 상태 공간 트리의 같은 레벨에 있는 모든 마디의 유망성 여부를 점검하는 절차는 같아야 함
  • 상태 공간 트리의 같은 레벨에 있는 모든 마디는 반드시 같은 수의 자식 마디를 가지고 있어야 함
• n-Queens 문제는 이 두 조건 만족

• 무작위로 경로 생성
  • 루트(레벨 0)의 유망한 자식 마디의 개수를 $m_0$라고 함
  • 상태 공간 트리의 레벨 1에서 유망한 마디를 하나 랜덤하게 정하고, 이 마디의 유망한 자식 마디의 개수를 $m_1$이라고 함
  • 위에서 정한 마디의 유망한 마디를 하나 랜덤하게 정하고, 이 마디의 유망한 자식 마디의 개수를 $m_2$라고 함
  • …
  • 더이상 유망한 자식 마디가 없을 때까지 이 과정 반복
• 여기서 $m_i$는 수준 i에 있는 마디의 유망한 자식 마디 개수의 평균의 추정치
• 수준 i에 있는 한 마디의 자식 마디의 총 개수를 $t_i$라고 하면 (유망하지 않은 마디 포함), 되추적 기법에 의해 점검한 마디의 총 개수의 추정치는
  $1 + t_0 + m_0t_1 + m_0m_1t_2 + … + m_0m_1…m_{i-1}t_i + …$

• ex) n-Queens 문제에 적용