ここで問題があり、重み付けされた 2 部一致の問題に減らすことができました。基本的に、パーティション A と B を持つ 2 部グラフと、重みを持つ一連のエッジがあります。私の場合、|A|~=20 および |B| です。=300。
重みを最小化し、 「A」をカバーするエッジのセットを見つけたい(A の各エッジには、関連付けられたソリューション エッジがあります)
質問:
-この種の問題に特別な名前があるので、アルゴリズムと解決策を探すことができますか?
-無限の重みで A にダミーの頂点を追加することにより、重み付きの 2 部の完全な一致に減らすことができることを知っています。でも |B|>>|A| 以来、実用的なパフォーマンスが心配です。
-Java ライブラリに関する提案はありますか? これを見つけました: http://algs4.cs.princeton.edu/code/。「AssignmentProblem.java」はほとんど必要なものだと思います-（しかし、完全に一致することは保証されませんか？）
事前に感謝し、英語が下手で申し訳ありません。