「割当問題」の版間の差分
ナビゲーションに移動
検索に移動
Albeit-Kun (トーク | 投稿記録) |
|||
| (2人の利用者による、間の2版が非表示) | |||
| 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>\textstyle \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> を求める問題を割り当て問題と呼ぶ. 最大重み完全マッチング問題とも呼ばれるこの問題は, 最小費用フロー問題（最小費用流問題）の特殊ケースと見ることもできる. この問題に対し, 効率的な多項式時間解法が数多く提案されている. |
| + | |||
| + | [[Category:グラフ･ネットワーク|わりあてもんだい]] | ||
2008年11月14日 (金) 09:55時点における最新版
【わりあてもんだい (assignment problem)】
なる2部グラフ および各枝 の重み が与えられたときに, 枝の重みの和 を最大にする完全マッチング を求める問題を割り当て問題と呼ぶ. 最大重み完全マッチング問題とも呼ばれるこの問題は, 最小費用フロー問題（最小費用流問題）の特殊ケースと見ることもできる. この問題に対し, 効率的な多項式時間解法が数多く提案されている.
