algorithm - ハンガリーのアルゴリズムを使用して最大コストを見つけることはできますか?

Question

ハンガリーのアルゴリズムは、代入問題を多項式時間で解きます。ワーカーとタスク、および各ワーカーをタスクに割り当てるコストを含む n×n 行列が与えられると、コストを最小化する割り当てを見つけることができます。

コストが最大になる選択肢を見つけたいですか? ハンガリー語または同様の方法を使用してそれを行うことはできますか? それとも、これは指数関数的にのみ行うことができますか?

Answer 1

ウィキペディアは次のように述べています。

目標が最大コストを生み出す割り当てを見つけることである場合、各コストを最大コストからコストを引いたものに置き換えることで、設定に合うように問題を変更できます。

したがって、私の理解が正しければ、入力として持っているすべてのコストの中で、最大値を見つけることができます。x次に、各コストを で置き換えますmax - x。このように、まだ正のコストがあり、ハンガリーのアルゴリズムを実行できます。

別の言い方をすれば、ハンガリー人は割り当てコストを最小限に抑えようとします。したがって、最大を探している場合は、コストを逆にすることができます: x -> -x. ただし、一部の実装 (全部か一部かは不明) では、正の数が必要です。したがって、正の数を得るために、各コストに一定の値を追加するという考え方です。この定数値は、結果として生じる影響を変更しません。