Thema:
Re:Threadnapping: Programmierfrage (Logik) flat
Autor: _bla_
Datum:06.02.20 18:05
Antwort auf:Re:Threadnapping: Programmierfrage (Logik) von Alopex

>Hi,
>
>danke. Da muss ich mich erstmal nochmal schlau machen was deinen Lösunsgvorschlag angeht. Hab ich nicht auf Anhieb verstanden.


Bei meinem Lösungsvorschlag bildest du dein Matching Problem auf ein anderes Problem ab.
Du findest die maximal mögliche Durchflußmenge und die dazu genutzten Verbindungen.
Hier gibt es eine ganz gute grundsätzliche Erklärung:
[https://www.geeksforgeeks.org/maximum-bipartite-matching/]
Dort werden Jobs mit Bewerbern gemacht. In deinem Fall sind es stattdessen eben Bewerber mit Gutachtern. Du hast links je einen Knoten pro Bewerber und rechts je ein Knoten pro Gutachter. Du fügst dann überall dort Verbindungen zwischen Bewerbern und Gutachtern ein, wo deine Regeln erfüllt werden. Also eine Verbindung für jedes potentielle Gutachten. Diese Verbindungen haben jeweils eine Kapazität von 1. Dann fügst du einen Quellknoten ganz links ein und von dort jeweils eine Verbindung zu jedem Bewerber. Die Kapazität dieser Verbindungen entspricht jeweils der Anzahl der Reviews pro Bewerber. Fast das gleiche machst du ganz rechts, dort kommt eine einzelne Senke hin, sie wird jeweils mit allen Gutachtern verbunden, wobei die Kapazität dieser einzelnen Verbindungen jeweils der maximalen Anzahl an Reviews pro Gutachter entspricht. Der Maxflow Algorithmus rechnet dann aus wie viel maximal von Quelle nach Senke fließen kann und auf welchen Wegen. In deinem Fall entspricht dieser Fluß, der Gesamtanzahl der Gutachten, die geschrieben werden können, ohne das ein Gutachter mehr Gutachten als das Maximum erstellt und ohne das für einen Bewerber mehr Gutachten als nötig erstellt werden. Wenn der maximale Fluß also genau der Anzahl der Bewerber Mal der Anzahl der Gutachten pro Bewerber entspricht, dann hast du eine gültige Lösung gefunden, ansonsten muss die maximale Anzahl der Gutachten pro Gutachter erhöht werden, weil es keine Möglichkeit gibt mit diesem Maximum alle nötigen Gutachten zu erstellen.


>Aber du hast recht, die Lösung ist bei mir in der realen Welt vglw. einfach, weil die Zahl der Gutachten in gewissem Umfang variabel ist.
>Wenn es mit "jeder genau 40 Gutachten" nicht aufgeht, kann ich immer einen oder mehrere umverteilen, und dann gibt es eben ein paar mit 39 und ein paar mit 41 Gutachten. No big deal, solange das nicht zu sehr ausufert.
>
>Weiterhin finde ich das Problem aber auch in der Theorie sehr spannend, auch mit Blick auf die Ideal-Lösung. Da bin ich ein bisschen Ästhet/Perfektionist: Ich will möglichst nah an das Idealergebnis herankommen.
>
>Grüße,
>Wolfgang



----------------------
Gesendet mit M! v.2.7.0


< antworten >