「割当問題」の版間の差分
ナビゲーションに移動
検索に移動
(新しいページ: ''''【わりあてもんだい (assignment problem)】''' $|V^+| = |V^-|$ なる2部グラフ $G = (V^+, V^-; A)$ および各枝 $a \in A$ の重み $w(a) \in {\bf R}$が与...') |
(相違点なし)
|
2007年7月9日 (月) 15:03時点における版
【わりあてもんだい (assignment problem)】
$|V^+| = |V^-|$ なる2部グラフ $G = (V^+, V^-; A)$ および各枝 $a \in A$ の重み $w(a) \in {\bf R}$が与えられたときに, 枝の重みの和 $\sum_{a \in M}w(a)$ を最大にする完全マッチング $M \subseteq A$ を求める問題を割り当て問題と呼ぶ. 最大重み完全マッチング問題とも呼ばれるこの問題は, 最小費用流問題の特殊ケースと見ることもできる. この問題に対し, 効率的な多項式時間解法が数多く提案されている.