Ungarischer Algorithmus: Ich habe Probleme mit der Zuweisung von so vielen Jobs an Mitarbeiter wie möglich

Question

Ich habe eine Implementierung des ungarischen Algorithmus in C++ erstellt. Diese Implementierung funktioniert sehr gut für viele Fälle. Es gibt jedoch einige Fälle, in denen mein Algorithmus überhaupt nicht funktioniert, weil ich glaube (und das stimmt), dass meine Implementierung eines Schrittes des Algorithmus falsch ist.

Meine Implementierung nimmt als Eingabe das Array X, führt die Schritte des Algorithmus und erzeugt die endgültige Zuordnung. Hungarian Algorithm

In Schritt 3 hat die folgende Reihe von Kosten (Arbeitnehmer, die von Reihen und Arbeitsplätzen durch Spalten dargestellt werden)

:

Die Schritte des Algorithmus können auf dem Wiki zu finden und dann heißt es

Initially assign as many tasks as possible then do the following 

Allerdings verstehe ich nicht, was ein richtig Umsetzung wäre dies. Wie können Sie so viele Aufgaben wie möglich zuweisen? Wäre die Wahl zufällig? Wenn dann die Wahl zufällig wäre, könnte ich den ersten Arbeiter wählen, der den ersten Job übernimmt, den zweiten, der den vierten Job übernimmt, und den vierten, der den zweiten Job übernimmt. Also wird der zweite Arbeiter ausgelassen. In Wikipedia verfolgten die Autoren jedoch einen anderen Ansatz. Der dritte Arbeiter muss den ersten Job übernehmen, der zweite muss den zweiten Job annehmen und der vierte muss den zweiten Job annehmen. Also wird der erste Arbeiter ausgelassen.

Das Problem bei solchen zufälligen Aktionen tun, ist der folgende Fall:

Angenommen, während wir den Algorithmus und tun unser arithmetische Operationen an den Eingang laufen, bevor so viele Aufgaben für die Arbeitnehmer wie möglich messen wir die folgende Kostenmatrix haben :

2 2 0 3 
6 1 6 0 
0 0 6 1 
0 3 5 3 

Wenn ich die Wahl gelassen zufällig den dritten Auftrag an den ersten Arbeiter zuweisen, der vierte Auftrag an den zweiten Arbeiter und dann wird der erste Auftrag an den dritten Arbeiter, ich werde die vierte Arbeiter haben. Damit der Algorithmus korrekt funktioniert, müssen wir as many jobs to workers as possible zuweisen. Ist das hier der Fall? Nein, denn wenn ich statt des ersten Jobs dem dritten Worker den ersten Job dem vierten Worker zuweisen würde, könnte ich den zweiten Job dem dritten Worker zuweisen, und der Algorithmus würde also nicht nur so vielen Jobs wie möglich zuweisen aber es würde das optimale Ergebnis finden.

Fazit: Doing zufällige Zuweisungen ist kein guter Ansatz.

ich über diese ein wenig gesucht und ich die folgende Vorlesung gefunden:

http://www.youtube.com/watch?v=BUGIhEecipE

In diesem Vortrag der Professor für das Problem der Zuordnung so viele Aufgaben wie möglich einen anderen Ansatz vermuten läßt. Nach ihm, wenn eine Zeile oder Spalte genau eine Null hat, werden wir eine Aufgabe machen. Also, beginnend mit der ersten Zeile, die Sie überprüfen, ob die erste Zeile nur eine Null hat, wenn das der Fall ist, machen Sie eine Zuweisung. Andernfalls ignorieren Sie diese Zeile und gehen Sie in die zweite Zeile, machen Sie dasselbe wiederholt durch erneutes Scannen der Tabelle, bis alle Nullen aufgrund von Zuordnungen abgedeckt sind.

Mit diesem Ansatz kann man sehen, dass der vorherige Fall gelöst ist. Was wir tun, ist, dass wir dem ersten Arbeiter den dritten, dem zweiten Arbeiter den vierten Job zuweisen, dann sehen wir, dass der dritte Arbeiter 2 Jobs annehmen kann, also ignorieren wir ihn für eine Weile, wir ordnen den ersten Job dem vierten zu Arbeiter und dann zurück, um den zweiten Job dem dritten Arbeiter zuzuweisen.

Meine Implementierung folgt dieser Logik, aber auch hier löst sie nicht alle Fälle.

Lassen Sie uns zum Beispiel nehmen Sie den folgenden Fall:

0 0 0 0 
0 0 0 0 
0 0 4 9 
0 0 2 3 

Der erste Arbeiter 4 Jobs nehmen, die zweite 4, der dritte 2 und die vierte 2. Das Gleiche gilt für meine Implementierung keine Zuweisungen, weil ich brauchen würde, mindestens ein Arbeiter, der nur einen Job annehmen kann, um eine Aufgabe zu erledigen, und dann weiter, indem er den Tisch scannt. Was mache ich in diesem Fall? Willkürliche Aufträge wären schlecht, leider wird in diesem Vortrag nichts vorgeschlagen. Ich konnte nur an folgendes denken:

Für jeden Arbeiter haben einen Zähler, dessen Wert die Menge der Aufgaben angibt, die ihm zugewiesen werden können, also wie viele Nullen haben wir in dieser Reihe? das ist der Wert des Zählers. Dann beginnen Sie, dem Arbeiter mit dem kleinsten Zähler beliebige Aufgaben zuzuweisen. Also in diesem Fall würde die Anordnung der Zähler für die einzelnen Arbeitnehmer gehört die folgenden Werte:

4 
4 
2 
2 

ich zum Beispiel an ihn die erste Aufgabe, den dritten Arbeiter und willkürliche assign wählen würde. Die neuen Zähler wären:

3 
3 
0 
1 

Ich würde dann die vierten Arbeiter wählen und tue die einzige Aufgabe für ihn zur Verfügung (das ist der zweite Job ist). Die neuen Zähler wären:

2 
2 
0 
0 

Dann könnte ich entweder den ersten Arbeiter oder den zweiten wählen. Ich würde einen willkürlichen Auftrag für den ersten Arbeiter machen und ihm den dritten Job geben. Die Zähler wären

1 
0 
0 
0 

Schließlich würde ich die vierte Aufgabe auf den ersten Job geben.

So ist die Abschlussarbeiten:

0 0 0 * 
0 0 * 0 
* 0 4 9 
0 * 2 3 

Es scheint wie ein guter Ansatz, aber ich fürchte, es könnte ein Sonderfall sein, dass diese Methode nicht funktionieren würde. Wie kann ich überprüfen, ob dieser Ansatz für alle Fälle funktioniert und wenn nicht, welcher Ansatz würde mein Problem vollständig lösen?

Vielen Dank im Voraus

Answer 1

Ihr aktueller Ansatz funktioniert nicht Arbeit.

0 2 0 
3 0 0 
4 0 0 

Ihre Methode: „Starten Sie dann mit dem kleinsten Zähler beliebige Aufgaben der Arbeiter zuweisen“ Alle Arbeitnehmer haben den gleichen Zähler, so sagen Sie wählen Arbeiter 1 und ordnen ihn 3 Aufgabe, können Sie nur eines Spiel von den restlichen Arbeitern, während mit dieser Matrix Sie natürlich alle drei zusammenbringen konnten.

Was Sie brauchen, ist eine maximale zweiteilige übereinstimmung zwischen diesen Arbeitnehmern und Aufgaben, wo ein Paar zusammenpassbar ist, wenn es eine 0 in der relevanten Position ist. Solch ein Abgleich kann gefunden werden, indem man manuell durch die Erweiterung von Pfaden geht oder schneller durch Verwendung des Hopcroft-Karp-Algorithmus.