백트래킹 및 분기 한정법

백트래킹(backtracking)과 분기 한정법(branch and bound)은 후보 해 공간을 트리 형태로 탐색하는 체계적인 탐색 패러다임입니다. 이 방법들은 유효하거나 최적의 해로 이어질 수 없는 서브트리(subtree)를 가지치기(pruning)하여, 실질적으로는 지수적인 탐색을 다룰 수 있게 만듭니다.

Definition

백트래킹은 부분 후보 해 트리에 대한 깊이 우선 탐색(depth-first search)으로, 부분 후보가 유효한 해로 완성될 수 없는 순간 해당 가지를 가지치기합니다. 분기 한정법은 여기에 목표 함수에 대한 수치적 경계를 추가하여, 최적의 가능한 값이 현재까지 찾은 최적해(incumbent)를 능가할 수 없는 가지들을 버립니다.

Scope

이 주제는 탐색 트리를 중심으로 구성된 완전 탐색 기법을 다룹니다. 여기에는 부분 후보가 제약 조건을 위반하는 즉시 해당 후보를 포기하는 백트래킹과, 최적화에서 달성 가능한 최적 목표에 대한 경계(bounds)를 사용하여 서브트리를 가지치기하는 분기 한정법이 포함됩니다. 제약 만족 문제(N-queens, 그래프 색칠, 스도쿠)와 조합 최적화 문제(외판원 문제, 정수 계획법)의 예시를 포함하며, 최악의 경우 지수적인 비용에도 불구하고 이러한 방법들이 NP-난해 문제에 대해 여전히 유용한 이유를 논의합니다.

Core questions

• 문제의 해 공간은 부분 할당의 탐색 트리로 어떻게 모델링됩니까?
• 백트래킹이 실현 불가능한 가지를 조기에 가지치기할 수 있도록 하는 제약 조건 검사는 무엇입니까?
• 최적화에서 가지를 가지치기하기 위해 하한(lower bound)과 상한(upper bound)은 어떻게 계산됩니까?
• 분기(branching) 및 한정(bounding) 순서는 실제 성능에 어떤 영향을 미칩니까?
• 최악의 경우 지수적인 복잡성에도 불구하고 이러한 방법들이 NP-난해 문제에 사용되는 이유는 무엇입니까?

Key concepts

• 탐색 트리
• 깊이 우선 탐색
• 제약 조건 전파
• 가지치기
• 한정 함수
• 현재 최적해
• N-queens 문제
• 정수 계획법 완화

Key theories

탐색 트리의 가지치기

두 패러다임 모두 후보 해를 깊이 우선으로 탐색되는 트리로 구성합니다. 정확성은 완전성에서 오고, 효율성은 유효하거나 개선된 해를 포함할 수 없다고 증명된 서브트리를 가지치기하는 데서 옵니다.

분기 한정법의 한정 함수

분기 한정법은 지금까지 발견된 최적해와 각 서브트리에서 달성 가능한 최적 값에 대한 경계(예: LP 완화)를 유지합니다. 서브트리의 경계가 현재 최적해를 개선할 수 없을 때 해당 서브트리는 버려집니다.

Clinical relevance

분기 한정법은 운영 연구(operations research)에서 정수 및 혼합 정수 계획법 솔버(solver)를 포함한 정확한 조합 최적화의 핵심이며, 이는 스케줄링, 경로 설정 및 계획에 사용됩니다. 백트래킹은 제약 조건 솔버, SAT(충족 가능성 문제) 스타일 탐색, 퍼즐 솔버 및 파서(parser)의 기반이 되며, 여기서는 가지치기를 통한 체계적인 탐색이 정확한 해를 찾는 실용적인 방법입니다.

History

백트래킹은 1950년대와 1960년대에 일반적인 기법으로 체계화되었으며, 특히 Golomb와 Baumert에 의해 기술되었습니다. 분기 한정법은 1960년 Ailsa Land와 Alison Doig에 의해 정수 선형 계획법(integer linear programming)을 위해 도입되었고, 이후 조합 최적화의 핵심이 되어 현대 혼합 정수 계획법 솔버의 기반이 되었습니다.

Key figures

• Ailsa Land
• Alison Doig
• Solomon Golomb
• Robert Bixby

Seminal works

• landdoig1960
• cormen2009

Frequently asked questions

백트래킹과 분기 한정법의 차이점은 무엇입습니까?

백트래킹은 일반적으로 실현 가능성 및 제약 만족 문제에 사용되며 제약 조건을 위반하는 가지를 가지치기합니다. 분기 한정법은 최적화를 목표로 하며, 추가적으로 수치적 경계를 사용하여 가지치기하고, 최적의 가능한 목표가 이미 발견된 최적해를 능가할 수 없는 모든 서브트리를 버립니다.

이러한 방법들이 최악의 경우 지수적이라면 왜 사용합니까?

NP-난해 문제에 대해서는 다항 시간의 정확한 알고리즘이 알려져 있지 않지만, 효과적인 가지치기는 실제 사례에서 탐색 트리의 대부분을 제거하는 경우가 많습니다. 따라서 분기 한정법 및 백트래킹 솔버는 최악의 경우 예상되는 시간보다 훨씬 빠르게 증명 가능한 최적해를 찾는 경우가 많습니다.