分枝限定法
【英】：branch and bound method
組合せ最適化問題を厳密に解くために開発された列挙法の一種. 実行可能領域を分割するという操作を反復することによって 部分問題を生成し(分枝操作), 最適値の上下界値の情報を用いて 最適解の出現する見込みのない部分問題を省く(限定操作)ことで, 組合せ的爆発を克服する. ナップサック問題や巡回セールスマン問題など多くの組合せ最適化問題に対し, 実用性の高い厳密解法として広く用いられている.
分枝限定法 (スケジューリングの)
分枝限定法
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/12/10 08:34 UTC 版)
分枝限定法（ぶんしげんていほう、英: branch and bound, BB）は、各種最適化問題（特に離散最適化と組合せ最適化）の最適解を求める汎用アルゴリズムである。分枝操作（英: branching operation）と限定操作（英: bounding operation）から構成される。全ての解候補を体系的に列挙するもので、最適化された量の上限と下限の概算を使って、最適でない候補は「ひとまとめに」捨てられる。
1960年、A. H. Land と A. G. Doig が線型計画法の手法として最初に提案した。
概要
関数 
| 一般 |
|
|---|---|
| 微分可能 |
|
| 凸縮小化 |
|
||||
|---|---|---|---|---|---|
| 線型 および 二次 |
|
| 系列範例 (Paradigms) |
|||||
|---|---|---|---|---|---|
| グラフ理論 |
|
分枝限定法
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/04/02 00:52 UTC 版)
詳細は「分枝限定法」を参照 タンパク質設計の立体配座空間は、タンパク質残基を任意の順序で並べ、残基内の各回転異性体で木が分岐するような木構造で表現することができる。分枝限定アルゴリズム（branch and bound algorithms）は、この表現を用いて立体配座木を効率的に探索する。各分岐で、分枝限定アルゴリズムは、立体配座空間を結合し、有望な分岐のみを探索する。 タンパク質設計のための一般的な探索アルゴリズムは、A*探索アルゴリズム（A* search algorithm）である。A*は、各部分木のパスに対して、展開された各回転異性体のエネルギーを（保証付きで）下限とする下限スコアを計算する。おのおのの部分立体配座は優先キューに追加され、各反復において、最も低い下限値を持つ部分的パスがキューから取り出されて展開される。このアルゴリズムは、完全な立体配座が列挙されると停止し、その立体配座が最適であることを保証する。 タンパク質設計のA*スコア f は、 f=g+h の2つの部分から構成される。g は、部分立体配座ですでに割り当てられている回転異性体の正確なエネルギーである。h は、まだ割り当てられていない回転異性体のエネルギーの下限値である。それぞれは、以下のように設計されている。ここで、d は部分立体配座の最後に割り当てられた残基のインデックスである。 g = ∑ i = 1 d ( E ( r i ) + ∑ j = i + 1 d E ( r i , r j ) ) {\displaystyle g=\sum _{i=1}^{d}(E(r_{i})+\sum _{j=i+1}^{d}E(r_{i},r_{j}))} h = ∑ j = d + 1 n [ min r j ( E ( r j ) + ∑ i = 1 d E ( r i , r j ) + ∑ k = j + 1 n min r k E ( r j , r k ) ) ] {\displaystyle h=\sum _{j=d+1}^{n}[\min _{r_{j}}(E(r_{j})+\sum _{i=1}^{d}E(r_{i},r_{j})+\sum _{k=j+1}^{n}\min _{r_{k}}E(r_{j},r_{k}))]}
※この「分枝限定法」の解説は、「タンパク質設計」の解説の一部です。
「分枝限定法」を含む「タンパク質設計」の記事については、「タンパク質設計」の概要を参照ください。
- 分枝限定法のページへのリンク
