「割当問題」の版間の差分
ナビゲーションに移動
検索に移動
| 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部グラフ および各枝 の重み が与えられたときに, 枝の重みの和 を最大にする完全マッチング を求める問題を割り当て問題と呼ぶ. 最大重み完全マッチング問題とも呼ばれるこの問題は, 最小費用流問題の特殊ケースと見ることもできる. この問題に対し, 効率的な多項式時間解法が数多く提案されている.
