Back Tracking vs. Branch and Bound

백트래킹(Backtracking)과 분기한정법(Branch and Bound)은 조합 최적화 문제를 해결하기 위한 두 가지 중요한 알고리즘 설계 패러다임이다.
두 기법 모두 모든 가능한 해결책을 체계적으로 탐색하지만, 그 접근 방식과 최적화 전략에는 중요한 차이가 있다.

백트래킹과 분기한정법은 조합 최적화 문제를 해결하기 위한 강력한 도구이다.
백트래킹은 제약 충족 문제에 더 적합하며, 가능한 모든 해결책이나 첫 번째 유효한 해결책을 찾는 데 중점을 둔다. 반면 분기한정법은 최적화 문제에 더 적합하며, 경계값을 사용하여 최적해를 효율적으로 찾는 데 중점을 둔다.

문제의 특성, 해의 요구사항, 가용 자원에 따라 적절한 기법을 선택하거나 두 기법의 장점을 결합한 하이브리드 접근법을 고려할 수 있다. 최근 연구에서는 이러한 알고리즘의 효율성을 더욱 향상시키기 위한 다양한 휴리스틱과 최적화 기법이 개발되고 있다.

궁극적으로, 이러한 체계적인 문제 해결 기법들은 컴퓨터 과학의 핵심 도구로서, NP-하드 문제와 같은 계산적으로 어려운 문제들을 실용적으로 접근할 수 있게 해준다.

백트래킹(Backtracking)

백트래킹은 가능한 모든 해결책을 탐색하는 체계적인 방법으로, 후보 해결책을 점진적으로 구축하다가 더 이상 진행할 수 없을 때 이전 단계로 돌아가(backtrack) 다른 대안을 시도하는 기법.
이는 특히 제약 충족 문제(Constraint Satisfaction Problems)를 해결하는 데 효과적.

작동 원리:

  1. 상태 공간 트리(State Space Tree): 가능한 모든 해결책을 트리 형태로 표현.
  2. 깊이 우선 탐색(DFS): 특정 경로를 따라 가능한 한 깊이 탐색.
  3. 제약 조건 검사: 현재 부분 해결책이 제약 조건을 만족하는지 확인.
  4. 가지치기(Pruning): 제약 조건을 위반하면 해당 경로를 더 이상 탐색하지 않는다.
  5. 되돌아가기(Backtracking): 막다른 길이나 유효하지 않은 경로에 도달하면 이전 결정 지점으로 돌아간다.

복잡도

  1. 시간 복잡도

    • 백트래킹: 최악의 경우 지수 시간(O(b^d)), 여기서 b는 분기 팩터, d는 최대 깊이

  2. 공간 복잡도

    • 백트래킹: O(d), 재귀 호출 스택의 깊이에 비례

백트래킹 구현 시 고려사항

  1. 상태 표현: 부분 해결책을 효율적으로 표현하는 방법
  2. 제약 조건 검사: 가능한 한 빨리 유효하지 않은 경로를 식별
  3. 재귀 함수 설계: 스택 오버플로우를 방지하기 위한 적절한 재귀 깊이 관리
  4. 상태 복원: 백트래킹 후 이전 상태로 정확히 복원하는 메커니즘

백트래킹 최적화

  1. 전방 검사(Forward Checking): 현재 할당의 영향을 미리 확인
  2. 가장 제약이 많은 변수 선택(MRV): 가장 선택지가 적은 변수부터 처리
  3. 가장 제약이 적은 값 선택(LCV): 다른 변수에 가장 적은 제약을 가하는 값 선택
  4. 아크 일관성(Arc Consistency): 변수 쌍 간의 일관성 유지

백트래킹 적용 사례

  1. N-Queens 문제: N×N 체스판에 N개의 퀸을 배치하는 문제
  2. 스도쿠 퍼즐: 9×9 그리드에 1-9의 숫자를 채우는 퍼즐
  3. 그래프 컬러링: 인접한 정점이 같은 색상을 갖지 않도록 그래프의 각 정점에 색상을 할당
  4. 부분집합 합 문제: 주어진 집합에서 합이 특정 값이 되는 부분집합 찾기
  5. 해밀턴 경로: 그래프의 모든 정점을 정확히 한 번씩 방문하는 경로 찾기

알고리즘 템플릿

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def backtrack(candidate):
    if is_complete(candidate):
        output(candidate)  # 완전한 해결책 발견
        return
    
    for next_candidate in get_candidates(candidate):
        if is_valid(next_candidate):  # 제약 조건 검사
            place(next_candidate)  # 후보 배치
            backtrack(next_candidate)  # 재귀적으로 다음 단계 탐색
            remove(next_candidate)  # 백트래킹 (후보 제거)

예시: N-Queens 문제

N-Queens 문제는 N×N 체스판에 N개의 퀸을 서로 공격할 수 없도록 배치하는 문제.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

def solve_n_queens(n):
    def is_valid(board, row, col):
        # 같은 열에 퀸이 있는지 확인
        for i in range(row):
            if board[i] == col:
                return False
            
            # 대각선 확인
            if abs(board[i] - col) == row - i:
                return False
        
        return True
    
    def backtrack(board, row):
        if row == n:
            solutions.append(board[:])
            return
        
        for col in range(n):
            if is_valid(board, row, col):
                board[row] = col
                backtrack(board, row + 1)
                # 백트래킹 (명시적인 제거는 필요 없음, 다른 값으로 덮어씀)
    
    solutions = []
    backtrack([-1] * n, 0)
    return solutions

분기한정법(Branch And Bound)

분기한정법은 최적화 문제를 해결하기 위한 알고리즘으로, 해공간을 체계적으로 탐색하면서 가능한 해결책의 상한과 하한을 계산하여 최적해를 찾는 방법이다.
이 방법은 특히 최소화 또는 최대화 문제에 효과적.

작동 원리:

  1. 분기(Branching): 문제를 더 작은 하위 문제로 분할.
  2. 한정(Bounding): 각 하위 문제에 대한 상한과 하한을 계산.
  3. 가지치기(Pruning): 현재까지 발견된 최적해보다 나쁜 경계값을 가진 하위 문제는 제외.
  4. 탐색 전략: 일반적으로 최상 우선 탐색(Best-First Search) 또는 너비 우선 탐색(BFS)을 사용.

복잡도

  1. 시간 복잡도
    • 백트래킹: 최악의 경우 지수 시간(O(b^d)), 여기서 b는 분기 팩터, d는 최대 깊이
    • 분기한정법: 최악의 경우 지수 시간(O(b^d)), 그러나 효과적인 한정 함수를 사용하면 평균적으로 더 나은 성능
  2. 공간 복잡도
    • 백트래킹: O(d), 재귀 호출 스택의 깊이에 비례
    • 분기한정법: O(b^d), 최악의 경우 모든 노드를 저장해야 할 수 있음

분기한정법 구현 시 고려사항

  1. 경계 함수 설계: 정확하고 계산이 빠른 하한/상한 함수 개발
  2. 노드 표현: 상태, 비용, 경계값을 효율적으로 저장
  3. 우선순위 큐 관리: 큐의 크기가 지나치게 커지는 것을 방지
  4. 중복 상태 처리: 동일한 상태가 여러 번 탐색되는 것을 방지

분기한정법 최적화

  1. 더 나은 경계 함수: 더 정확한 하한/상한 계산
  2. 휴리스틱 함수 사용: 유망한 해결책으로 빠르게 유도
  3. 지배 관계(Dominance Relations): 더 나은 해결책이 보장된 상태 식별
  4. 병렬 처리: 독립적인 하위 문제를 병렬로 처리

분기한정법 적용 사례

  1. 외판원 문제(TSP): 모든 도시를 한 번씩 방문하고 출발점으로 돌아오는 최단 경로 찾기
  2. 0-1 배낭 문제: 제한된 무게 내에서 최대 가치를 갖는 아이템 선택
  3. 작업 할당 문제: n개의 작업을 n명의 작업자에게 최소 비용으로 할당
  4. 최단 경로 문제: 그래프에서 두 정점 사이의 최단 경로 찾기
  5. 정수 선형 계획법(ILP): 정수 변수를 사용하는 선형 최적화 문제

알고리즘 템플릿

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

def branch_and_bound(problem):
    queue = PriorityQueue()  # 우선순위 큐 (경계값 기준)
    queue.put(initial_node)
    best_solution = None
    best_value = float('inf')  # 최소화 문제 가정
    
    while not queue.empty():
        node = queue.get()
        
        if node.bound < best_value:  # 유망한 노드인지 확인
            if is_leaf(node):
                if node.value < best_value:
                    best_value = node.value
                    best_solution = node.solution
            else:
                for child in branch(node):
                    child.bound = compute_bound(child)
                    if child.bound < best_value:  # 유망한 자식만 추가
                        queue.put(child)
    
    return best_solution

예시: 외판원 문제(TSP)

외판원 문제는 모든 도시를 한 번씩 방문하고 출발 도시로 돌아오는 최단 경로를 찾는 문제.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

def solve_tsp(distance_matrix):
    n = len(distance_matrix)
    
    class Node:
        def __init__(self, path, cost, bound):
            self.path = path
            self.cost = cost
            self.bound = bound
        
        def __lt__(self, other):
            return self.bound < other.bound
    
    def compute_bound(node):
        # 하한값 계산 (각 미방문 도시에서 가장 짧은 간선들의 합)
        bound = node.cost
        visited = set(node.path)
        
        for i in range(n):
            if i not in visited:
                min_edge = float('inf')
                for j in range(n):
                    if j != i and (j not in visited or j == node.path[0]):
                        min_edge = min(min_edge, distance_matrix[i][j])
                bound += min_edge
        
        return bound
    
    # 시작 노드 (0번 도시부터 시작)
    start = Node([0], 0, 0)
    start.bound = compute_bound(start)
    
    queue = PriorityQueue()
    queue.put(start)
    
    best_tour = None
    best_cost = float('inf')
    
    while not queue.empty():
        node = queue.get()
        
        if node.bound < best_cost:
            if len(node.path) == n:
                # 마지막 도시에서 시작 도시로 돌아가는 비용 추가
                total_cost = node.cost + distance_matrix[node.path[-1]][node.path[0]]
                if total_cost < best_cost:
                    best_cost = total_cost
                    best_tour = node.path + [node.path[0]]
            else:
                for next_city in range(n):
                    if next_city not in node.path:
                        new_path = node.path + [next_city]
                        new_cost = node.cost + distance_matrix[node.path[-1]][next_city]
                        new_node = Node(new_path, new_cost, 0)
                        new_node.bound = compute_bound(new_node)
                        
                        if new_node.bound < best_cost:
                            queue.put(new_node)
    
    return best_tour, best_cost

두 기법의 핵심 차이점

  1. 목적:
    • 백트래킹: 모든 가능한 해결책을 찾거나 제약 조건을 만족하는 해결책을 찾는 데 중점을 둔다.
    • 분기한정법: 최적화 문제에서 최적해를 찾는 데 중점을 둔다.
  2. 탐색 전략:
    • 백트래킹: 일반적으로 깊이 우선 탐색(DFS)을 사용.
    • 분기한정법: 일반적으로 최상 우선 탐색(Best-First Search) 또는 너비 우선 탐색(BFS)을 사용.
  3. 가지치기 기준:
    • 백트래킹: 제약 조건 위반 여부에 따라 가지치기.
    • 분기한정법: 경계값(bound)과 현재 최적해 비교를 통해 가지치기.
  4. 상태 공간 탐색:
    • 백트래킹: 가능한 모든 조합을 체계적으로 생성하고 테스트.
    • 분기한정법: 유망한 부분 공간을 우선적으로 탐색.
  5. 메모리 사용:
    • 백트래킹: 재귀 호출 스택에 의존하므로 상대적으로 메모리 효율적.
    • 분기한정법: 우선순위 큐나 활성 노드 목록을 유지해야 하므로 더 많은 메모리가 필요할 수 있다.

하이브리드 접근법

최근에는 두 기법의 장점을 결합한 하이브리드 알고리즘이 개발되고 있다:

  1. 백트래킹 + 하한 계산: 백트래킹 알고리즘에 하한 계산을 추가하여 더 효과적인 가지치기
  2. 분기한정법 + 깊이 우선 탐색: 메모리 효율성을 위해 DFS 전략을 사용하는 분기한정법
  3. 제약 프로그래밍 + 분기한정법: 제약 프로그래밍의 유연성과 분기한정법의 최적화 능력 결합

비교 분석 표

특성백트래킹(Backtracking)분기한정법(Branch and Bound)
주요 목적모든 가능한 해결책 찾기 또는 제약 충족최적화 문제에서 최적해 찾기
탐색 전략깊이 우선 탐색(DFS)최상 우선 탐색 또는 너비 우선 탐색
가지치기 기준제약 조건 위반경계값과 현재 최적해 비교
공간 탐색 방식체계적 생성 및 테스트유망한 영역 우선 탐색
상태 유지현재 경로만 유지유망한 모든 부분 문제 유지
시간 복잡도O(b^d), 가지치기로 개선 가능O(b^d), 효과적인 한정으로 개선 가능
공간 복잡도O(d), 깊이에 비례O(b^d), 최악의 경우
적합한 문제 유형제약 충족 문제(CSP)조합 최적화 문제
대표적 알고리즘N-Queens, 스도쿠 솔버외판원 문제, 0-1 배낭 문제
해의 품질모든 해 또는 첫 번째 유효한 해최적해 보장
메모리 효율성높음 (재귀 스택만 사용)낮음 (활성 노드 목록 유지)
구현 난이도중간높음 (좋은 경계 함수 설계 필요)
병렬화 가능성제한적높음 (독립적 하위 문제)
조기 해 발견가능 (첫 번째 해가 중요한 경우)최적해 보장을 위해 계속 실행
휴리스틱 활용제한적광범위 (경계 함수, 탐색 전략)
변형/확장전방 검사, MRV, LCVA* 알고리즘, 휴리스틱 탐색

참고 및 출처