Die Mathe-Redaktion - 20.04.2019 12:54 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
ListenpunktSchwätz / Top 15
ListenpunktWerde Mathe-Millionär!
ListenpunktAnmeldung MPCT Sept.
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 401 Gäste und 22 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von matroid
Mathematik » Kombinatorik & Graphentheorie » Finde die besten und meisten Paar-Kombinationen
Druckversion
Druckversion
Antworten
Antworten
Autor
Beruf Finde die besten und meisten Paar-Kombinationen
rambo3
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 14.11.2008
Mitteilungen: 1172
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2019-01-19


Hallo Leute

Ich habe eine Tabelle mit Paar-Kombinationen. Jedes Pärchen ist mit einem Score bewertet, welcher Aussagt, wie gut beide Personen zusammenpassen.





Mein Problem ist, dass die Tabelle nicht eindeutig ist. Z.B. matched Allen mit Jolly (Score=1.8), jedoch matched Jolly noch besser mit Jacob (Score=3.4). Mir wurde gesagt, dass es sehr schwierig ist, die maximale Anzahl der besten Kombinationen zu finden. Daher würde ich mich schon damit begügen, einen Algorithmus zu finden, welcher für möglichst viele Personen einen Match findet. Dabei muss es sich nicht um den besten Match handeln, sondern es sollen möglichst viele Personen mit aufgenommen werden. Jeder soll das Glück haben zumindest irgendeinen Partner zu finden :-)

Das ist leider nicht so leicht wie man denkt, da es viele doppelte Namen gibt.

1) Wie würdet ihr an dieses Problem gehen? Wie sollte der Algorithmus funktionieren?
2) Ich versuche es mit Python zu lösen. Vielleicht habt ihr Tipps für mich. Mathematica wäre ebenfalls Möglich. Jedoch brauche ich zuerst einen guten und konreten Ansatz.

Ich hoffe ihr könnt mir helfen.

Vielen Dank




  Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2009
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2019-01-19


Das Problem ist Perfect Matching in einem bipartiten Graph.
Das geht bspw. mit der ungarischen Methode, die sich in diversen Algorithmenbibliotheken finden sollte.



-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



  Profil  Quote  Link auf diesen Beitrag Link
rambo3
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 14.11.2008
Mitteilungen: 1172
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2019-01-19


Vielen Dank. Das ist schon mal gut zu wissen. Leider weiß ich nicht, wie ich dieses Problem in Python löse. Aber ich kann mich jetzt mal gezielter informieren.

Vielleicht hat noch jemand ein paar Tipps, ansonsten werde ich diesen Post in ca. 24h schließen

Vielen Dank



  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 4853
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2019-01-19


2019-01-19 10:54 - DerEinfaeltige in Beitrag No. 1 schreibt:
Das Problem ist Perfect Matching in einem bipartiten Graph.

Wieso bipartit? Je zwei von Allen, Jolly und Christina haben einen Score.

Was bedeutet eigentlich die erste Spalte?

[Die Antwort wurde nach Beitrag No.1 begonnen.]



  Profil  Quote  Link auf diesen Beitrag Link
rambo3
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 14.11.2008
Mitteilungen: 1172
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2019-01-19


Die erste Spalte ist der Index. Er hat keine Bedeutung. Ich hätte ihn auch entfernen können für meine Frage



  Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2009
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2019-01-19


2019-01-19 11:22 - StrgAltEntf in Beitrag No. 3 schreibt:
2019-01-19 10:54 - DerEinfaeltige in Beitrag No. 1 schreibt:
Das Problem ist Perfect Matching in einem bipartiten Graph.

Wieso bipartit? Je zwei von Allen, Jolly und Christina haben einen Score.


Stimmt, da habe ich nicht aufgepasst.
Dann ist es eben ein allgemeines Perfect Matching Problem.
Blossom Algorithmus kann das lösen.
Sollte man ebenfalls in diversen Bibliotheken finden.
Für Python finden sich im Netz auch Musterimplementierungen. (nicht ganz trivial selbst zu implementieren)


-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 5759
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2019-01-21


Das beste Matching im Beispiel ist übrigens
emely		rock		3.7
jacob		jolly		3.4
sabastein	anna		2.8
rick		allen		1.5
mary		christina	1.3

Es gibt weitere Matchings mit dem gleichen Gesamtscore.

In bestimmten Zusammenhang ist der Begriff des stabilen Matching interessant. In einem stabilen Matching gibt es kein ungematchtes Knotenpaar (A,B), bei dem das Paar (A,B) einen höheren Score hat als die Paare, die A und B enthalten (so vorhanden).

Die obere Lösung ist instabil, das das Paar rick-christina (2.1) einen höheren Score hat, als die Paare rick-allen und mary-christina.
Es gibt im Beispiel kein stabiles Matching mit 5 Paaren.

Wären alle Scores verschieden, so könnte man stabile Matchings durch ein Greedy-Verfahren bestimmen. Man wählt dazu jeweils aus den noch freien Knoten das Paar mit dem höchsten Score.



  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 4853
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2019-01-21


2019-01-21 12:47 - Kitaktus in Beitrag No. 6 schreibt:
Das beste Matching im Beispiel ist übrigens
emely		rock		3.7
jacob		jolly		3.4
sabastein	anna		2.8
rick		allen		1.5
mary		christina	1.3


@Kitaktus: Ich nehme an, du hast hier das Matching mit dem höchsten Gesamtscore (= Summe der einzelnen Scores) bestimmt. Was "das beste" bedeutet, kann man natürlich auch unter anderen Gesichtspunkten betrachten.

Nehmen wir an, die zehn aufgeführten Personen sind Mitglieder eines Tennisclubs, und der Club hat vor, ein Doppelturnier auszurichten. Hierzu sind die zehn Personen in fünf Mannschaften aufzuteilen; am besten so, dass das Turnier möglichst spannend wird.

Bei der angegebenen Aufteilung hätte das Doppel Mary+Christina vermutlich keine große Chance, ins Geschehen einzugreifen.

Stattdessen könnte man versuchen, das Matching so zu wählen, dass

1) \(\max_{i=1,...,5}s_i-\min_{i=1,...,5}s_i\) minimal wird oder

2) \(\sum_{i=1}^5(s_i-s)^2\) minimal wird, wobei \(s=\frac15\sum_{i=1}^5s_i\).

\(s_1,...,s_5\) sollen hier die Scores der ausgewählten Paarungen sein.

Für 1 hätte ich wohl einen effizienten Algorithmus. Für 2 habe ich noch keine Idee.




  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 5759
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, eingetragen 2019-01-22


@StrgAltEntf: Ja, Du hast recht, es gibt noch viele andere Zielfunktionen, die z.T. unterschiedliche Schwierigkeiten mit sich bringen.
Kannst Du einen Algorithmus, der die Differenz aus Max und Min minimiert kurz skizzieren?



  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 4853
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2019-01-22


2019-01-22 08:48 - Kitaktus in Beitrag No. 8 schreibt:
Kannst Du einen Algorithmus, der die Differenz aus Max und Min minimiert kurz skizzieren?

Mach ich gerne. "Effizient" bedeutet polynomiell.

Sei \(G=(V,E)\) mit \(E=\{e_1,...,e_n\}\). \(s_i\) sei der Score von \(e_i\) und es gelte oBdA \(s_1\leq...\leq s_n\).

\(A\) sei die Menge aller Paare \((i,j)\) mit \(i<j\), sodass \((V,\{e_i,e_{i+1},...,e_j\})\) ein Matching \(M_{i,j}\) besitzt und jedes solche Matching die Kanten \(e_i\) und \(e_j\) enthält.

Bestimme dann \((i,j)\in A\), für das \(s_j-s_i\) minimal. \(M_{i,j}\) ist dann das gesuchte Matching.

(Details führe ich bei Bedarf gerne noch aus.)




  Profil  Quote  Link auf diesen Beitrag Link
rambo3 hat die Antworten auf ihre/seine Frage gesehen.
rambo3 hatte hier bereits selbst das Ok-Häkchen gesetzt.
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-2019 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. 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]