「分枝限定法」の版間の差分
削除された内容 追加された内容
m編集の要約なし |
|||
6行目:
例として、関数 <math>f(x)</math> の最小値を求める問題を考える。これは、たとえば、ある製品の製造コストを最小化する問題である。ここで <math>x</math> のとりうる範囲を集合 <math>S</math> で表すものとする。
分枝限定法には2つの手続きが必要である。
分枝限定法には2つの手続きが必要である。第一は「分割」手続きである。これは、与えられた集合 <math>S</math> に対して、<math>S_1\cup S_2\cup \ldots =S</math> となるような複数の集合 <math>S_1, S_2, \ldots</math> に分割する手続きである。<math>S_i</math> における <math>f(x)</math> の最小値を <math>v_i</math> としたとき、<math>S</math> における <math>f(x)</math> の最小値は <math>\min\{v_1, v_2, \ldots\}</math> である。この手続きを再帰的に適用することは'''分枝法''' (branching) と呼ばれ、各ノードが <math>S</math> の部分集合となるような[[木 (数学)|木]]（[[探索木]]）になる。▼
; 分枝
▲
; 限定
: 第二の手続きは、<math>S</math> の1つの部分集合の最小値の上限と下限を計算する手続きである。これを'''限定法''' (bounding) と呼ぶ。▼
: 分枝限定法の鍵となるのは、あるノード（候補集合） <math>A</math> の下限が別のノード <math>B</math> の上限より大きければ、A は探索するまでもなく捨ててよいという考え方である。この工程を'''刈り込み''' (pruning) と呼び、一般に大域変数 <math>m</math> にそれまでに調べた部分の最小の上限値を保持するような実装で実現する。下限が <math>m</math> より大きいノードは捨てることができる。▼
: 再帰は候補集合 <math>S</math> が1つの元になった時点で停止するか、<math>S</math> の上限が下限と一致した場合に停止する。どちらにしても、停止したときの <math>S</math> のどの元も関数を最小値にする。▼
分枝限定法は、限定法の種類によって分類したり、探索木のノードの生成/検査方法で分類したりする。▼
▲第二の手続きは、<math>S</math> の1つの部分集合の最小値の上限と下限を計算する手続きである。これを'''限定法''' (bounding) と呼ぶ。
分枝限定法の設計戦略は、状態空間木を問題を解くのに使うという点で[[バックトラッキング]]とよく似ている。これらの違いは、分枝限定法が木の走査順序を限定していないという点と、分枝限定法が最適化問題でしか使われないという点である。▼
▲分枝限定法の鍵となるのは、あるノード（候補集合） <math>A</math> の下限が別のノード <math>B</math> の上限より大きければ、A は探索するまでもなく捨ててよいという考え方である。この工程を'''刈り込み''' (pruning) と呼び、一般に大域変数 <math>m</math> にそれまでに調べた部分の最小の上限値を保持するような実装で実現する。下限が <math>m</math> より大きいノードは捨てることができる。
この手法は[[並列コンピューティング|並列]]実装や[[分散コンピューティング|分散]]実装に適している。▼
▲再帰は候補集合 <math>S</math> が1つの元になった時点で停止するか、<math>S</math> の上限が下限と一致した場合に停止する。どちらにしても、停止したときの <math>S</math> のどの元も関数を最小値にする。
この手法の効率は、ノード分割手続きと上限および下限を推定する手続きに強く依存する。他の全ての条件が同じなら、オーバーラップしない部分集合に分割するのが最もよい。
20 ⟶ 26行目:
この手法の効率は、分枝法と限定法に使われたアルゴリズムの有効性に強く依存する。間違った選択をすると分枝が繰り返され、全く刈り込みが行われず、あまりにも細かく分割されることになる。それは定義域を総当りするのと何ら変わりないことになり、多くの場合現実的でない。あらゆる問題でうまくいく限定法アルゴリズムは存在しないし、今後見つかるとも思えない。従って、分枝法と限定法のアルゴリズムは問題毎に設計する必要がある。
▲分枝限定法は、限定法の種類によって分類したり、探索木のノードの生成/検査方法で分類したりする。
▲分枝限定法の設計戦略は、状態空間木を問題を解くのに使うという点で[[バックトラッキング]]とよく似ている。これらの違いは、分枝限定法が木の走査順序を限定していないという点と、分枝限定法が最適化問題でしか使われないという点である。
▲この手法は[[並列コンピューティング|並列]]実装や[[分散コンピューティング|分散]]実装に適している。
== 応用 ==
| |||