だから、これは私には非常に奇妙に思えます。最初にハンガリー語アルゴリズム ( munkres python package ) を使用して 174x174 行列の割り当て問題を解決し、次に Google OR ツールの最小コスト フロー ソルバーを使用して解決しました。かかった時間をベンチマークしたところ、Munkres は非常に遅くなりました (ほぼ 12 倍遅くなりました!)。
ムンクレス: 48.2650001049s
GoogleOR: 4.4240000248s
これらは最適化アルゴリズムであるため、結果の選択は同じでしたが、なぜ GoogleOR はそれほど高速なのですか? 誰でも説明できますか？
編集：これがさらに驚くべき理由は、Munkresアルゴリズムが割り当て問題を解決するために特別に設計されたのに対し、min-cost-flowははるかに一般的なアルゴリズムであるためです。
ありがとう。