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

提供: ORWiki
ナビゲーションに移動 検索に移動
(新しいページ: '【ぶんしげんていほう (branch and bound method)】 組合せ最適化問題を厳密に解くために開発された列挙法の一種. 実行可能領域を分割...')
 
 
(2人の利用者による、間の2版が非表示)
1行目: 1行目:
【ぶんしげんていほう (branch and bound method)】
+
'''【ぶんしげんていほう (branch and bound method)】'''
  
 
組合せ最適化問題を厳密に解くために開発された列挙法の一種. 実行可能領域を分割するという操作を反復することによって 部分問題を生成し(分枝操作), 最適値の上下界値の情報を用いて  最適解の出現する見込みのない部分問題を省く(限定操作)ことで, 組合せ的爆発を克服する. ナップサック問題や巡回セールスマン問題など多くの組合せ最適化問題に対し, 実用性の高い厳密解法として広く用いられている.
 
組合せ最適化問題を厳密に解くために開発された列挙法の一種. 実行可能領域を分割するという操作を反復することによって 部分問題を生成し(分枝操作), 最適値の上下界値の情報を用いて  最適解の出現する見込みのない部分問題を省く(限定操作)ことで, 組合せ的爆発を克服する. ナップサック問題や巡回セールスマン問題など多くの組合せ最適化問題に対し, 実用性の高い厳密解法として広く用いられている.
 +
 +
[[Category:組合せ最適化|ぶんしげんていほう]]
 +
 +
[[Category:非線形計画|ぶんしげんていほう]]
 +
 +
[[Category:スケジューリング|ぶんしげんていほう]]

2008年11月13日 (木) 15:54時点における最新版

【ぶんしげんていほう (branch and bound method)】

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