algo_lec16

 

백트래킹 효율 분석 (n-Queens 기준)

Q: How to measure the efficiency of backtracking algorithm?
A: measure the amount of reduction on the number of nodes by a backtracking algorithm
(note that we only visit promising nodes when using a backtracking algorithm)
promising 노드만 방문한다는 전제 하에, 탐색 노드 수의 감소량을 측정하는 것

Q: What could be a good way to count how many checked nodes can be reduced?
(얼마나 많은 노드의 탐색을 줄일 수 있는지를 측정하는 좋은 방법은 무엇인가?)

"How to get # of nodes to be visited"

 

1) 상태 공간 트리 전체 노드 수 (최악의 경우)

• 깊이 i에서 n^i개의 노드 → 총 노드 수: 1 + n + n² + ... + nⁿ ≈ 20,000,000 (n=8)

2) 개선된 promising 노드 수 추정

: The upper bound on the number of promising nodes by ignoring same colu mn-positioned nodes

• 중복 열 배치만 제거해도: 1 + n + n(n-1) + ... + n! ≈ 110,000 (n=8)
• 하지만 대각선까지 고려해야 하므로 더 적음

The above analysis is not a good idea
because (1) The first approach only considers the upper bound (so what?)
and (2) The second approach does not consider the diagonal check

 

Monte Carlo Simulation (탐색 노드 수 추정 방법)

• 실제로 알고리즘을 실행하지 않고, 무작위 탐색 경로를 통해 평균적인 탐색 노드 수를 추정하는 방법
• 각 레벨에서 유망한 노드를 랜덤으로 선택하고 그 자식 수를 측정해 곱셈 누적
• 평균값을 여러 번 반복하여 추정치를 얻음

조건

• 같은 깊이의 노드들은 같은 수의 자식 노드를 가져야 함
• 같은 기준으로 promising 여부를 판단해야 함
  → N-Queens 문제는 이 조건을 만족

목적

• 실제로 알고리즘을 전부 실행하지 않고, 평균적으로 백트래킹이 탐색하는 노드 수를 추정하는 것이 목적

방법

1. 루트 노드의 자식 수: t₀ (보통 n개)
2. promising한 자식 노드 수: m₀ (대개 t₀와 같음, 처음엔 모두 유망하므로)
3. Level 1: m₀개의 promising 자식 중 하나를 무작위로 선택
   • 그 선택된 노드의 promising 자식 수를 m₁이라 둠
4. Level 2: 선택된 m₁ 중 무작위 선택 → 다음 레벨 자식 수를 m₂로 측정
5. 이 과정을 더 이상 promising 노드가 없어질 때까지 반복

탐색 노드 수 추정 공식

• 추정 탐색 노드 수 = 1 + m₀ × t₁ + m₀ × m₁ × t₂ + m₀ × m₁ × m₂ × t₃ + ...
  • mᵢ: 각 레벨에서 promising 자식 노드 수
  • tᵢ: 각 노드가 실제 가질 수 있는 자식 노드 수 (보통 n)

예시) n = 4인 경우

단계별로 추정

1. m₀ × t₁ = 4 × 4
   • 루트에서 4개의 promising 자식을 가정, 각 자식이 다시 4개의 자식을 가짐
2. m₀ × m₁ × t₂ = 4 × 1 × 4
3. m₀ × m₁ × m₂ × t₃ = 4 × 1 × 1 × 4

예시 시나리오

• (1,2) 선택 후 (2,4) 선택
• 또는 (1,3)만 선택
• 또는 (1,4) 후 (2,1) 선택 등

이러한 경로들을 각각 손으로 추정해서 탐색된 노드 수를 계산할 수 있음

 

실제 측정값 예시

• 손계산 결과: 탐색된 노드 수 61

 

슈도코드

estimate() {
    node v;
    int m, mprod, t, numnodes;
    v = root;
    numnodes = 1; // 루트 노드 포함
    m = 1;
    mprod = 1;

    while (m != 0) {
        t = number of child nodes of v;
        mprod = mprod * m;
        numnodes = numnodes + mprod * t;

        m = number of promising child nodes of v;
        if (m != 0)
            v = randomly select promising child of v;
    }

    return numnodes;
}

 

Code) Monte Carlo Estimation for n-queens problem

int estimate_n_queens(int n) {
    index i, j, col[1..n];
    int m, mprod, numnodes;
    set_of_index prom_children;

    i = 0;
    numnodes = m = mprod = 1;

    while (m != 0 && i != n) {
        mprod = mprod * m;
        numnodes = numnodes + mprod * n;

        i++;
        m = 0;
        prom_children = empty;

        for (j = 1; j <= n; j++) {
            col[i] = j;
            if (promising(i)) {
                m++;
                prom_children = prom_children ∪ {j};
            }
        }

        if (m != 0)
            j = randomly pick from prom_children;
            col[i] = j;
    }

    return numnodes;
}

 

Subset Sum 문제 예시

문제 설명

• 양의 정수 n개가 주어졌을 때, 합이 M이 되는 부분집합을 찾는 문제 (NP-Hard)

백트래킹 조건

• 현재 부분합 wsum이 M이면 해
• wsum + w[i+1] > M이면 더 이상 탐색하지 않음
• wsum + rsum < M이어도 pruning

슈도코드

def sum_of_subsets(i, wsum, rsum):
    if is_expand(i):
        if wsum == M:
            print_solution()
        else:
            sum_of_subsets(i+1, wsum + w[i+1], rsum - w[i+1]) # include
            sum_of_subsets(i+1, wsum, rsum - w[i+1])         # exclude

 

Example3: 0-1 Knapsack problem

문제 설명

• n objects: S={1,2, ... ,n}
• weight of each object: W = {w₁, ... , wₙ}
• profit of each object: P = {p₁, ... , pₙ}
• knapsack capacity = M
• 목표) 총 무게가 M을 넘지 않으면서 총 가치를 최대화

 

가지치기 기준 (Bound 사용)

• psum: 현재까지 선택한 이익
• wsum: 현재까지 선택한 무게
• M: 배낭 총 용량
• k: 앞으로 고를 수 있는 아이템 중 처음으로 초과되는 아이템의 인덱스

1. wtotal = wsum + ∑(i+1 to k-1) wi
   → 아이템을 최대한 넣되, k번째에서 초과 발생
2. bound = psum + ∑(i+1 to k-1) pi + (M - wtotal) * pk / wk
   → 초과되는 아이템은 fractional하게 더하기

• 앞으로 선택 가능한 최대 이익을 bound로 추정
• bound ≤ 현재까지 얻은 최대 이익 current → pruning