Index
割当・マッチング問題 / Assignment・Matching
離散最適化の問題のひとつ.
- 数理最適化 #まとめ編
割当・マッチング問題とは、ある集合の各要素について、 それぞれ別の集合のどの要素に割り当てると、様々な制約条件を満たしつつ、 最もよい割当を行うことができるのかを決定する問題のこと.
2次割当問題
2次割当問題は、対象物と配置場所などの同数の割当先が与えられているとき、 割当先間の輸送量と距離の積の総和を最小化する問題.
2部マッチング
問題をグラフ理論の観点から見たとき、2部グラフになっている場合の割当問題.
応用アルゴリズム
参考
- 組合せ最適化
Web サイト
- 実世界で超頻出!二部マッチング (輸送問題、ネットワークフロー問題)の解法を総整理!