私は割り当て問題を効率的に解決する必要があります（完全な加重二部グラフが与えられた場合、最大総加重で完全に一致するものを選択します）。ここからO（n ^ 3）バージョンを使用していますhttp://community.topcoder.com /tc?module=静的&d1=チュートリアル&d2=ハンガリー語アルゴリズム. しかし、私が読んだ論文では、「密および疎の線形代入問題に対する最短増強経路アルゴリズム」で「より効率的な方法」について言及されていましたが、これは悲しいことにペイウォールの背後にあります。私が知っておくべきより高速なアルゴリズムはありますか (漸近的に、またはより小さな定数/より均一なメモリアクセスなどを使用して)? 整数の重みではなく浮動小数点の重みを使用しています。ハンガリーの方法では問題にならないようですが、より高速な整数の実装では問題になる可能性があります。関連するリンクは大歓迎です。
質問する
2813 次