| Re:Threadnapping: Programmierfrage (Logik) |  |
Ich könnte mir folgenden Algorithmus mit einer Graphenabbildung vorstellen:
Erst einmal eine Datenstruktur anlegen, die (für Dein Beispiel) den folgenden Graphen abbildet (erst mal nur die Knotenpunkte und die grünen Linien, denn das sind Deine Vorgaben):
[https://i.imgur.com/8kCvh4x.png]
Dann ermittelst Du die rot gestrichelten Linien. Dazu legst Du immer genau dann eine rot gestrichelte Linie von einem Bewerber zu einem Gutachter an, wenn es nicht schon einen "grünen Weg" zu diesem Gutachter (über irgendwelche anderen Zwischenknoten) gibt.
Dann zählst Du für jeden Bewerber, wie viele rot gestrichelte Linien von ihm ausgehen.
Falls welche mit 0 dabei sind, kannst Du aufhören, denn dann gibt es keine Lösung.
Dann nimmst Du Dir der Reihe nach alle Bewerber mit einer 1 vor und machst aus der jeweils einen vorhandenen gestrichelten Linie eine durchgezogene. Bei jedem Gutachter führst Du einen Zähler mit, wieviele durchgezogene rote Linien bei ihm enden.
Jetzt kommen die Bewerber mit einer 2 dran. Hier hast Du ja immer zwei gestrichelte Linien zur Auswahl, Du nimmst die, die bei dem Gutachter endet, bei dem bisher die wenigsten durchgezogenen roten Linien enden (bei Gleichstand nimmst Du irgendeinen von den beiden).
Das ganze immer so weiter mit 3, 4 etc., bis alle Bewerber versorgt sind.
Ich hoffe, das passt. Oder habe ich was übersehen?