Matroids Matheplanet Forum Index
Moderiert von matroid
Kombinatorik & Graphentheorie » Graphentheorie » Zuordnungsproblem
Druckversion
Druckversion
Antworten
Antworten
Autor
Beruf Zuordnungsproblem
werz
Neu Letzter Besuch: im letzten Quartal
Dabei seit: 06.08.2020
Mitteilungen: 2
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-08-06


Hallo
Ich versuche ein Zuordnungsproblem (Personen zu Aufgaben) zu lösen, so dass eine maximale Zuordnung (matching) entsteht.

Ausgangslage:
Jede Person kann eine oder mehrere Aufgaben bearbeiten und umgekehrt kann jede Aufgabe durch eine oder mehrere Personen bearbeitet werden. Das Ganze kann als bipartiter Graph dargestellt werden.

Gesuchte Lösung:
eine maximale Zuordnung, d.h. jeder Person ist eine oder keine Aufgabe zugeordnet und jeder Aufgabe eine oder keine Person und es gibt keine andere Lösung mit mehr Zuordnungen.

Ich habe dazu den Algorithmus von Dinic nach der Vorlage des Buchs "Algorithmische Graphentheorie" von Volker Turau implementiert.
Turau schreibt: "Für einen bipartiten Graphen kann eine maximale Zuordnung ... mittels des Algorithmus von Dinic bestimmt werden."

Leider sind in den Lösungen, die ich damit erhalte, mehrere Peronen mit eine Aufgabe verknüpft und umgekehrt. Es gibt als kein matching.

Übersehe ich da etwas?
Kennt sich jemand mit dem Algorithmus von Dinic aus?




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 1509
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-08-07


Hallo werz!

Willommen auf dem Matheplaneten!

Ich kenne ein Zuordnungsproblem der Linearen Optimierung.
Dies läßt sich gut in O(n^3) lösen.
Dazu benutzt man die Ungarische Methode oder einen LP-Solver
(der benötigt für eine LU-Faktorisierung auch n^3 Zeiteinheiten).

Recht ähnlich dazu ist auch das Transportproblem der Linearen Optimierung.

Falls dies nicht zielführend ist, könnest Du Dein Problem eventuell noch einmal ausführlicher darstellen. Den Algorithmus von Dinic kenne ich bisher nicht - da kann ich eventuell später mal draufschauen!

Viele Grüße
Ronald



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6551
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2020-08-08


Hallo und Herzlich Willkommen auf dem Matheplaneten,

auf den ersten Blick habe ich mich gefragt, wie man aus diesen Angaben herausfinden soll, wo der Fehler steckt.
Auf den zweiten Blick habe ich aber einen Verdacht.
Außer den beiden Knotenmengen A und B benötigt man zusätzliche Knoten s und t.
s verbindet man mit jedem Knoten in A und jeden Knoten in B verbindet man mit t. Die Kapazität aller Kanten ist 1.
Das sorgt dafür, dass jeder Knoten aus A und B an höchstens einer Matching-Kante beteiligt ist.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
werz
Neu Letzter Besuch: im letzten Quartal
Dabei seit: 06.08.2020
Mitteilungen: 2
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, vom Themenstarter, eingetragen 2020-08-11


Dank an Delastelle und Kitaktus für die Rückmeldungen.

Inzwischen denke ich, dass ich kein Mathe-Problem, sondern ein Programmier-Problem habe, d.h. es hapert an der Umsetzung. Trotzdem möchte ich die Ausgangslage nochmal kurz beschreiben.

Der Algorithmus von Dinic findet einen maximalen Fluss in einem q-s-Netzwerk. Das ist ein kantenbewerteter gerichteter Graph mit 2 besonderen Ecken q (Quelle) und s (Senke). Alle anderen Ecken liegen zwischen q und s, d.h. alle Wege beginnen bei q und enden bei s.

Wie löst man damit ein Zordnungsproblem?
1. Die Menge aller zulässigen einzelnen Zuordnungen wird als bipartiter Graph dargestellt. Man hat also 2 Eckenmengen A und B und alle Kanten verlaufen von einer Ecke aus A zu einer Ecke aus B. Die Kanten sind bewertet und diese Bewertung wird als Kapazität interpretiert.
2. Man fügt 2 Ecken q und s dazu und Kanten von q zu jeder Ecke aus A und Kanten von jeder Ecke aus B zu s. Diese Kanten haben die Kapazität 1. Damit entsteht ein q-s-Netzwerk, wobei alle Wege von q nach s aus genau 3 Kanten bestehen und die ersten und dritten Kanten haben alle Kapazität 1.

Wie Kitaktus schon bemerkt hat, führt die Tatsache, dass die neuen Kanten alle Kapazität 1 haben, dazu, dass ein maximaler Fluss jede Ecke aus A und jede Ecke aus B höchstens einmal enthält. Damit ergibt sich ein matching.

Zur Programmierung:
Ich habe den Algorithmus von Dinic in Java programmiert und meine kleinen Testfälle funktionieren. Aber bei mehr als 5 plus 5 Ecken erhalte ich nicht immer ein matching, sondern mehrfache Ecken aus A und/oder B.
Deswegen wende ich mich wieder der Programmierung bzw. dem Test zu.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 1509
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2020-08-12


Hallo werz!

Wenn es bis n=5 funktioniert und bei n=6 nicht mehr, kannst Du eventuell ein 6er Beispiel posten und was dein Algorithmus damit macht!

Ich hatte früher mal als Test für ein Zuordnungsproblem der linearen Optimierung einen Typ verwendet mit quadratischer Matrix A (nicht die Matrix von Ax=b) und 1en auf der Diagonalen. Die optimale Zuordnung liegt dann auf der Diagonalen. Diese Testbeispiele funktinierten bei mir auch bei Dimension 1000 oder noch mehr.
Bsp. (1 2 3;
      8 1 4;
      5 6 1)

Eventuell kannst Du Dir für deinen Algorithmus ein paar schlaue Beispiele basteln (zu testzwecken).

Viele Grüße
Ronald



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
werz hat die Antworten auf ihre/seine Frage gesehen.
werz hatte hier bereits selbst das Ok-Häkchen gesetzt.
werz wird per Mail über neue Antworten informiert.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]