割当問題
【英】:assignment problem
なる2部グラフ
および各枝
の重み
が与えられたときに, 枝の重みの和
を最大にする完全マッチング
を求める問題を割り当て問題と呼ぶ. 最大重み完全マッチング問題とも呼ばれるこの問題は, 最小費用フロー問題(最小費用流問題)の特殊ケースと見ることもできる. この問題に対し, 効率的な多項式時間解法が数多く提案されている.
グラフ・ネットワーク: | 付値マトロイド 共通マトロイド問題 分枝カット法 割当問題 劣モジュラシステム 劣モジュラフロー問題 劣モジュラ最適化 |
「assignment problem」の例文・使い方・用例・文例
- assignment problemのページへのリンク