ユーザ用ツール

サイト用ツール


分岐限定法

branch and bound method

 組合せ最適問題の有力な解法の一つ.与えられた問題の実行可能解の領域を適切な部分領域に分割し,各部分領域を解領域とする部分問題(子問題)を生成する(分岐操作).生成された部分問題が原問題の最適解を与えない場合には,そのことを容易にチェックする方法を工夫し,その部分領域を以降の考慮の対象から除外する(限定操作).これらの操作を順に繰返すことにより,最適解あるいは目的関数値が最適値のある近傍に入る解を見つけることができる.解の列挙法の一つであるが,見込みのない部分領域を早めに切捨てる工夫をしている.