방법
하한 (Lower Bounds)
최적값의 하한을 계산해 정확 탐색을 가지치고 해의 품질을 보증하는 기법.
다른 이름: Lower Bounds · lower bound · 하한값 · Martello-Toth bounds
마지막 검증: 2026-05-27
정확 해법의 효율과 품질 보증을 떠받치는 바운딩 기법(v1에서는 method로 분류).
2D 절단·적재에서는 면적 하한(총 부품 면적 ÷ 빈 면적)부터 Martello–Toth 계열의
이산 하한까지 여러 하한이 쓰이며, 분기 한정에서 유망하지
않은 가지를 잘라내고 휴리스틱 해의 최적성 간극(optimality gap)을 보증한다. 2차원
패킹의 하한은 Lodi, Martello & Monaci(2002)의 서베이에 정리되어 있다.
주장 & 증거
모든 관계는 등가 수준과 증거 등급을 가진 하나의 주장입니다. 증거 정책을 참고하세요.
| 관계 | 주장 | 등가 | 증거 | 출처 |
|---|---|---|---|---|
| 방법 공유분기 한정 (Branch and Bound) | 하한 계산은 분기 한정의 가지치기를 이끄는 핵심 구성 요소다 — 강한 하한일수록 탐색 트리를 더 많이 잘라낸다. | E2 | A |
|
이웃 그래프
직접 연결된 그래프 이웃입니다. 깊이를 전환해 확장하세요.
노드를 클릭하면 열리고 · 엣지를 클릭하면 주장이 보입니다
그래프 불러오는 중…