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

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

2007年7月17日 (火) 14:03時点における版

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

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