効率的な分枝
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/12/10 08:34 UTC 版)
この手法の効率は、ノード分割手続きと上限および下限を推定する手続きに強く依存する。他の全ての条件が同じなら、オーバーラップしない部分集合に分割するのが最もよい。 理想的には、この手続きは探索木の全てのノードが刈りこまれるか解かれたときに停止する。その時点で刈りこまれていない部分は、上限と下限が関数の大域的最小値と等しくなっている。実際には、ある所定の時間が経過すると手続きを停止することが多く、その時点では刈りこまれていない部分の最大下限値と最小上限値が大域的最小値の区間を定義している。これとは別に時間制限ではなく、アルゴリズムを何らかの誤差基準で停止させる方法もある。例えば （最大 - 最小）/（最大 ＋ 最小）がある特定値以下になった時点で停止させる。 この手法の効率は、分枝法と限定法に使われたアルゴリズムの有効性に強く依存する。間違った選択をすると分枝が繰り返され、全く刈り込みが行われず、あまりにも細かく分割されることになる。それは定義域を総当りするのと何ら変わりないことになり、多くの場合現実的でない。あらゆる問題でうまくいく限定法アルゴリズムは存在しないし、今後見つかるとも思えない。従って、分枝法と限定法のアルゴリズムは問題毎に設計する必要がある。
※この「効率的な分枝」の解説は、「分枝限定法」の解説の一部です。
「効率的な分枝」を含む「分枝限定法」の記事については、「分枝限定法」の概要を参照ください。
ウィキペディア小見出し辞書の「効率的な分枝」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 効率的な分枝のページへのリンク
