「分岐限定法」の版間の差分

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

2007年9月5日 (水) 13:33時点における最新版

【ぶんきげんていほう (branch and cut method)】

分枝限定法ともいう. 組合せ最適化問題を厳密に解くために開発された列挙法の一種. 実行可能領域を分割するという操作を反復することによって 部分問題を生成し(分枝操作), 最適値の上下界値の情報を用いて 最適解の出現する見込みのない部分問題を省く(限定操作)ことで, 組合せ的爆発を克服する. ナップサック問題や巡回セールスマン問題など多くの組合せ最適化問題に対し, 実用性の高い厳密解法として広く用いられている.