algo_lec15

Lecture 15: Backtracking and Branch-and-Bound (Part 1)

 

NP-hard 문제 해결 방식

• 모든 가능한 해를 확인하는 Backtracking 또는 Branch-and-Bound 사용
• 혹은 근사 해법(Approximation Algorithm) 설계
• 대표적인 NP-hard 문제: TSP, N-Queens, Subset Sum 등

 

Backtracking이란?

• 모든 가능한 조합을 시도하되, 해가 될 수 없는 경로는 사전에 탐색 중단 (pruning)
• 어떤 문제의 해를 구하기 위해서 모든 가능성을 조사하지 않고는 해를 구할 수 없는 경우가 있음
• 퍼즐, 게임, NP-hard 문제에 적합 (예: 8-queen, 스도쿠, 크로스워드)
• 모든 경우에서 효율적인 건 아니지만, 좋은 전략과 좋은 한계 함수(promising function)를 사용하면 큰 입력에서도 해를 효율적으로 찾을 수 있음

직관적 설명:

• 갈림길에 'X' 표시를 하면서 돌아오는 탐색
• 해가 불가능한 경로를 빨리 포기함으로써 탐색 공간을 줄임

 

Example: n-queens problem (slide 7)

문제 개요

• n × n 체스판 위에 n개의 퀸을 서로 공격하지 않도록 배치하는 문제
• 서로 공격하지 않기 위해서는 같은 행, 열, 대각선에 두 퀸이 위치하면 안 됨

해의 표현 방식

• 각 열에 하나씩 퀸을 배치한다고 가정
• 열 인덱스를 1부터 n까지 두고, 각 열에 대해 행 번호를 지정하면 n길이의 벡터로 표현 가능
• 예: (2, 4, 1, 3)은 첫 번째 열에 2행, 두 번째 열에 4행, ... 방식으로 퀸을 배치한 상태

해의 후보 개수

• 열마다 퀸을 하나씩 배치하므로, 가능한 모든 배치는 n개의 수에 대한 순열
• 총 후보 수는 n! (팩토리얼)
  • 예: n = 4일 때, 후보 벡터는 4! = 24개

백트래킹이 필요한 이유

• 모든 후보를 완전탐색으로 확인하는 것은 비효율적 (특히 n이 클수록)
• 따라서 해가 될 가능성이 없는 경로를 사전에 제거하여 탐색 공간을 줄이는 것이 핵심
• 백트래킹은 탐색 시간을 줄이는 전략이지, 후보 수 자체를 줄이는 방법은 아님
  • 백트래킹의 기본 아이디어는 검사 대상이 되는 해의 후보 개수를 대폭 줄여 수행 시간을 절약해보고자 하는 것

Q1: How many possible candidates for the solution?
A1: n개의 퀸을 배치하는 모든 후보는 n! 개

Q2: If we have n queens, how to place 1~n numbers in n-length vector?
n개의 퀸이 있을 때, 1부터 n까지의 숫자를 n개의 길이를 가진 벡터에 어떻게 배치할 수 있는가?
1부터 n까지의 숫자(즉, 각 행 번호)를 중복 없이 n개의 열(벡터 인덱스)에 어떻게 배치할 수 있는가?
A2: 각 해는 n길이 순열 벡터로 표현됨. "순열(permutation)"

 

State Space Tree (Slide 8)

•  State space tree(상태 공간 트리): 백트래킹 알고리즘에서 해를 탐색하기 위한 구조적 표현 도구
  •  각 노드는 현재까지의 선택 상태를 나타내며, 트리를 따라가면서 가능한 해를 순차적으로 탐색

1. 노드의 의미:
   • 하나의 노드는 탐색 과정 중 현재까지의 선택 상태를 나타냄
   • 예: N-Queens 문제에서 (1,2)는 "1열에 1행, 2열에 2행에 퀸을 배치했다"는 뜻
2. 트리 구조의 성질:
   • 루트 노드: 초기 상태 (아직 아무것도 선택하지 않은 상태)
   • 각 자식 노드: 하나의 추가 선택 (예: 다음 열에 퀸을 배치)
3. 탐색 방법:
   • DFS(Depth-First Search) 방식으로 트리를 탐색
   • 가능한 해를 하나씩 구성하며 내려감
4. 예시 흐름:
   • 첫 번째 퀸 배치 (열 1 → 행 1~n 중 선택)
   • 두 번째 퀸 배치 (열 2 → 행 1~n 중 선택)
   • …
   • n번째 퀸까지 배치한 후 조건을 만족하면 해로 간주

 

Example 1: 4-Queens 문제

 

문제 정의:

• 4x4 체스판에 퀸 4개를 배치하되, 서로 공격하지 않도록 배치
• 행은 다르게 배치하므로, 각 열에 1개의 퀸만 배치 (벡터로 표현 가능)
• 가능한 모든 벡터 조합 수: 4! = 24

Brute Force Algorithm:

• 모든 위치에서 놓을 수 있는 경우를 시도
• 각 열마다 4개의 후보 → 총 4⁴ = 256개 후보 노드

State space tree

• Use DFS to find the solution among candidates
• 이 방법을 사용하면 해답이 될 가능성이 전혀 없는 노드의 후손노드들도 모두 탐색해야하므로 비효율적

Pruned state space tree

• 유망하지 않다고 판단되면, 그 노드의 후손 노드(서브 트리)들에 대한 탐색을 중지하고
• 그 노드의 부모 노드(parent)로 돌아감 "backtrack"
• 그런 다음, 다시 후손 노드에 대한 탐색을 계속 하게 되는 절차

pruning 이라고 부름.

 

• 상태 공간 트리에서 어떤 노드가 해가 될 수 없다고 판단되면, 그 노드를 “non-promising”
  반대로, 해로 이어질 가능성이 있다면 "promising"
• 가지치기(pruning)
  • 노드가 non-promising하다면, 그 노드의 부모 노드로 되돌아간다 "backtrack"
• 백트래킹 알고리즘의 핵심 원칙:
  • non-promising 노드는 가지쳐서(pruning) 더 이상 탐색하지 않고, promising 노드에 대해서만 자식 노드를 탐색

Staeps in backtracking problem:

• Do DFS
• Check if the node is promising
• If yes, keep searching. If no, do pruning (stop and backtrack)

알고리즘 흐름 (checknode 방식):

• promising 노드: 해가 될 수 있는 가능성이 있음 → 탐색 계속
• non-promising 노드: 해가 될 수 없음 → 탐색 중단(backtrack)
• promising 판단 기준:
  • 이전 퀸들과 같은 열, 같은 대각선에 있는지 확인

def checknode(v):
    if promising(v):
        if is_solution(v):
            write_solution(v)
        else:
            for each child u of v:
                checknode(u)

 

Q. If v=(1,1), is checknode(2,1) called?
A: Yes. checknode 호출하고 promising 검사

v = (1,1)은 상태 공간 트리에서 "1열에 퀸을 1행에 배치한 상태"를 의미

chehcknode(2,1)은 "2열에 퀸을 1행에 놓은 상태"
(1,1)에서 출발해 다음 열(2열)에 가능한 모든 행(1~n)을 놓는 경우를 시도하는 것

checknode(v)는 일단 현재 노드가 promising이면 모든 자식 노드에 대해 checknode(u)를 호출함.
따라서 (1,1)이 promising하면, 자식 노드 중 하나인 (2,1)에 대해서도 checknode(2,1)이 호출됨.

 

Improved backtracking (expand 방식):

• 처음부터 promising 여부를 검사한 자식 노드만 확장

expand(node v):
	node u;
    for (each child u of v)
        if (promising(u))
            if (there is a solution at u)
                write the solution;
            else
                expand(u);

Q. If v=(1,1), is expand(2,1) called?
A. NO. promising 경우만 expand 호출

 

 

성능 비교 (DFS vs Backtracking)

항목	DFS	Backtracking
탐색 방식	무조건 전 노드 방문	유망한 노드만 확장
pruning	X	O
성능	비효율적	효율적
방문 노드 수	155	27

• DFS 방식: 전체 노드 수 = 155개
• Backtracking 방식: pruning 후 노드 수 = 27개
• → 노드 수 5배 이상 감소, 탐색 효율 극대화

 

Example 1-2: N-Queens problem

• n개의 퀸을 n×n 체스판에 놓되,
• 같은 행, 열, 대각선에 놓이지 않아야 함

Promising function

• Let col[i] be the column where Qi is placed at i-th row
• Check if they are placed on the same column: col[i] = col[k]
• Check if they are placed on the diagonal: | col[i] - col[k] | = | i - k |

def promising(i, col):
	k = 1
    flag = True
    for (k<i and flag):
        if col[i] == col[k] or abs(col[i] - col[k]) == i - k:
            flag = False
        k += 1
    return flag

 

전체 알고리즘

def n_queens(i, col):
    n = len(col) - 1
    if promising(i, col):
        if i == n:
            print(col[1:])
        else:
            for j in range(1, n+1):
                col[i+1] = j
                n_queens(i+1, col)

# test code
n = 4
col = [0] * (n+1)
n_queens(0, col)