Kann ich den ungarischen Algorithmus verwenden, um die maximalen Kosten zu finden?

Question

Der ungarische Algorithmus löst das Zuweisungsproblem in Polynomialzeit. Angesichts von Arbeitern und Aufgaben und einer n × n-Matrix, die die Kosten für die Zuordnung eines jeden Arbeiters zu einer Aufgabe enthält, kann er die kostenminimierende Zuweisung finden.

Ich möchte die Wahl treffen für welche Kosten maximal ist? Kann ich das mit ungarischer oder ähnlicher Methode machen? Oder kann das nur exponentiell gemacht werden?

Answer 1

Wie David sagte in dem Kommentar:

Multiply the cost matrix by -1 for maximization. 

Answer 2

Wikipedia sagt:

Wenn das Ziel die Zuordnung zu finden ist, der die maximal Kosten ergibt, das Problem verändert werden kann, um die Einstellung zu passen durch jeden durch die Kosten abgezogen mit den maximal Kosten Kosten ersetzen .

Also wenn ich richtig verstehe: unter all den Kosten, die Sie als Eingabe haben, finden Sie den maximalen Wert. Dann ersetzen Sie jede Kosten x durch max - x. Auf diese Weise haben Sie immer noch positive Kosten und Sie können den ungarischen Algorithmus ausführen.

Anders gesagt: Ungarisch versucht, die Zuweisungskosten zu minimieren. Wenn Sie also nach dem Maximum suchen, können Sie die Kosten umkehren: x -> -x. Einige Implementierungen (wissen nicht, ob alle oder irgendwelche) erfordern jedoch positive Zahlen. Die Idee ist also, jeder Kosten einen konstanten Wert hinzuzufügen, um positive Zahlen zu haben. Dieser konstante Wert ändert die resultierende Affektation nicht.