「割当問題」の版間の差分

提供: ORWiki
ナビゲーションに移動 検索に移動
1行目: 1行目:
 
'''【わりあてもんだい (assignment problem)】'''
 
'''【わりあてもんだい (assignment problem)】'''
  
<math>|V^+| = |V^-|\,</math> なる2部グラフ  <math>G = (V^+, V^-; A)\,</math> および各枝 <math>a \in A\,</math> の重み <math>w(a) \in {\mathbf R}\,</math>が与えられたときに, 枝の重みの和 <math>\sum_{a \in M}w(a)\,</math> を最大にする完全マッチング <math>M \subseteq A\,</math> を求める問題を割り当て問題と呼ぶ.  最大重み完全マッチング問題とも呼ばれるこの問題は, 最小費用流問題の特殊ケースと見ることもできる. この問題に対し, 効率的な多項式時間解法が数多く提案されている.
+
<math>|V^+| = |V^-|\,</math> なる2部グラフ  <math>G = (V^+, V^-; A)\,</math> および各枝 <math>a \in A\,</math> の重み <math>w(a) \in {\mathbf R}\,</math>が与えられたときに, 枝の重みの和 <math>\textstyle \sum_{a \in M}w(a)\,</math> を最大にする完全マッチング <math>M \subseteq A\,</math> を求める問題を割り当て問題と呼ぶ.  最大重み完全マッチング問題とも呼ばれるこの問題は, 最小費用流問題の特殊ケースと見ることもできる. この問題に対し, 効率的な多項式時間解法が数多く提案されている.

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

【わりあてもんだい (assignment problem)】

なる2部グラフ および各枝 の重み が与えられたときに, 枝の重みの和 を最大にする完全マッチング を求める問題を割り当て問題と呼ぶ. 最大重み完全マッチング問題とも呼ばれるこの問題は, 最小費用流問題の特殊ケースと見ることもできる. この問題に対し, 効率的な多項式時間解法が数多く提案されている.