分枝限界法

ウィキペディア

分枝限定法

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/08/28 09:41 UTC 版)

分枝限定法（ぶんしげんていほう、英: branch and bound, BB）は、各種最適化問題（特に離散最適化と組合せ最適化）の最適解を求める汎用アルゴリズムである。分枝操作（英: branching operation）と限定操作（英: bounding operation）から構成される。全ての解候補を体系的に列挙するもので、最適化された量の上限と下限の概算を使って、最適でない候補は「ひとまとめに」捨てられる。

1960年、A. H. Land と A. G. Doig が線形計画法の手法として最初に提案した。

概要

関数 $f(x)$

最適化問題では極大・極小値をとる解を求める。

非線形（制約付き）

凸最適化

組合せ最適化

メタヒューリスティクス

• 進化的アルゴリズム（進化戦略・遺伝的アルゴリズム）
• 山登り法
• 局所探索法
• 焼きなまし法
• タブーサーチ
• 群知能（ACO・PSO）
• ベイスンホッピング法
• 量子焼きなまし法

• カテゴリ（最適化 • アルゴリズム） • ソフトウェア （一覧）