「分岐限定法」の版間の差分
ナビゲーションに移動
検索に移動
細 ("分岐限定法" を保護しました。 [edit=sysop:move=sysop]) |
Sakasegawa (トーク | 投稿記録) |
||
| 1行目: | 1行目: | ||
'''【ぶんきげんていほう (branch and cut method)】''' | '''【ぶんきげんていほう (branch and cut method)】''' | ||
| − | + | 分枝限定法ともいう. | |
| + | 組合せ最適化問題を厳密に解くために開発された列挙法の一種. 実行可能領域を分割するという操作を反復することによって 部分問題を生成し(分枝操作), 最適値の上下界値の情報を用いて 最適解の出現する見込みのない部分問題を省く(限定操作)ことで, 組合せ的爆発を克服する. ナップサック問題や巡回セールスマン問題など多くの組合せ最適化問題に対し, 実用性の高い厳密解法として広く用いられている. | ||
2007年9月5日 (水) 13:33時点における最新版
【ぶんきげんていほう (branch and cut method)】
分枝限定法ともいう. 組合せ最適化問題を厳密に解くために開発された列挙法の一種. 実行可能領域を分割するという操作を反復することによって 部分問題を生成し(分枝操作), 最適値の上下界値の情報を用いて 最適解の出現する見込みのない部分問題を省く(限定操作)ことで, 組合せ的爆発を克服する. ナップサック問題や巡回セールスマン問題など多くの組合せ最適化問題に対し, 実用性の高い厳密解法として広く用いられている.