翻訳と辞書 Words near each other ・ 分枝形成 ・ 分枝性 ・ 分枝根 ・ 分枝毛 ・ 分枝系 ・ 分枝系分離 ・ 分枝系選択 ・ 分枝腺 ・ 分枝酵素 ・ 分枝鎖アミノ酸 ・ 分枝限定法 ・ 分染 ・ 分染法 ・ 分柱 ・ 分校 ・ 分校の人たち ・ 分校村 ・ 分根 ・ 分椎目 ・ 分業 Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク 分枝限定法 ： ミニ英和和英辞書 分枝限定法[ぶんしげんていほう] ===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 分 ： [ぶん, ふん] 　 1. (n,n-suf,pref) (1) part　2. segment　3. share　4. ration　5. (2) rate　6. (3) degree　7. one's lot　8. one's status　9. relation　10. duty　1 1. kind　12. lot　13. (4) in proportion to　14. just as much as　1 ・ 限定 ： [げんてい] 　 1. (n,vs) limit　2. restriction　 ・ 定法 ： [じょうほう] 　【名詞】 1. established rule　2. usual method ・ 法 ： [ほう] 　 1. (n,n-suf) Act (law: the X Act)　 分枝限定法 ： ウィキペディア日本語版 分枝限定法[ぶんしげんていほう] 分枝限定法（ぶんしげんていほう、）は、各種最適化問題（特に離散最適化と組合せ最適化）の最適解を求める汎用アルゴリズムである。分枝操作（）と限定操作（）から構成される。全ての解候補を体系的に列挙するもので、最適化された量の上限と下限の概算を使って、最適でない候補は「ひとまとめに」捨てられる。 1960年、A. H. Land と A. G. Doig が線型計画法の手法として最初に提案した。 == 概要 == 関数 $f(x)$ の最小値を求める最適化問題を考える。 $x\; \backslash in\; S$ とする。 分枝限定法には2つの手続きが必要である。 ; 分枝 : 第一は分枝操作である。場合分けにより部分問題に分割する。つまり、与えられた集合 $S$ に対して、$S\_1\backslash cup\; S\_2\backslash cup\; \backslash ldots\; =S$ となるような複数の集合 $S\_1,\; S\_2,\; \backslash ldots$ に分割（分枝）する手続きである。$S\_i$ における $f(x)$ の最小値を $v\_i$ としたとき、$S$ における $f(x)$ の最小値は $\backslash min\backslash$ である。この手続きを再帰的に適用することは分枝法 (branching) と呼ばれ、各ノードが $S$ の部分集合となるような木（探索木）になる。なお $S\_i\; \backslash cap\; S\_j\; \backslash ne\; \backslash emptyset$ でも良い。 ; 限定 : 第二の手続きは、$S$ の1つの部分集合 $S\_i$ の $f(x)$ の最小値の上限と下限を計算する手続きである。これを限定法 (bounding) と呼ぶ。 : 分枝限定法の鍵となるのは、あるノード（候補集合） $A$ の下限が別のノード $B$ の上限より大きければ、A は探索するまでもなく捨ててよいという考え方である。この工程を刈り込み (pruning) と呼び、一般に大域変数 $m$ にそれまでに調べた部分の最小の上限値を保持するような実装で実現する。下限が $m$ より大きいノードは捨てることができる。 : 再帰は候補集合 $S$ が1つの元になった時点で停止するか、$S$ の上限が下限と一致した場合に停止する。どちらにしても、停止したときの $S$ のどの元も関数を最小値にする。 分枝限定法は、限定法の種類によって分類したり、探索木のノードの生成/検査方法で分類したりする。 分枝限定法の設計戦略は、状態空間木を問題を解くのに使うという点でバックトラッキングとよく似ている。これらの違いは、分枝限定法が木の走査順序を限定していないという点と、分枝限定法が最適化問題でしか使われないという点である。 動的計画法や貪欲法は部分問題の最適性が必要であるが、成立しない部分問題に対して、適切に場合分けして分枝することにより、分枝限定法でうまく行くこともある。 分枝が場合分けをするので並列実装や分散実装に適している。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「分枝限定法」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.