Informatikmaterialien 
von Tino Hempel

Startseite | Informatik | Physik | Mathematik | Sonstiges |


Richard-Wossidlo-Gymnasium Ribnitz-Damgarten
Fachbereich Informatik


Zuordnungsproblem "Tanzpaarung"
(nach Breier, N.: Grenzen des Computereinsatzes. Teil 1. In LogIn 10 (1990) Heft 1 und dem zugehörigen Materialien unter der  
URL: http://www.bildung-mv.de/download/fortbildungsmaterial/paket-theoretische-informatik.exe [02.02.2005])


Grundproblem

Vor einer Tanzparty mit n Jungen und gleich vielen Mädchen werden alle Teilnehmer befragt, wen sie von den anwesenden Gästen des anderen Geschlechts sympathisch finden. 
Gesucht ist eine Tanzpaarung, in der jeder Gast mit einem ihm sympathischen Partner tanzt.

Um dieses Problem zu lösen, muss man sich zunächst die Frage stellen, ob es überhaupt einen Algorithmus gibt, mit dessen Hilfe nach endlich vielen Schritten entschieden werden kann, ob es eine Tanzpaarung der gesuchten Art gibt oder nicht. 

Als Voraussetzung erfasst man dabei die Sympathien zwischen den Tänzern in Form einer Tabelle, wobei eine 0 genau dann notiert wird, wenn sich die beiden Parteien sympathisch sind, ansonsten wird eine 1 geschrieben.

Beispiele:

Beispiel 1   M1 M2 M3             Beispiel 2   M1 M2 M3
  J1 1 0 0     J1 1 0 1
  J2 1 0 1     J2 0 1 1
  J3 0 1 0     J3 1 0 1

Im Beispiel 1 findet man eine Lösung, in Beispiel 2 nicht.

Lösungsvariante I

Eine offensichtliche Lösung besteht darin, alle möglichen Tanzpaarungen zu erzeugen und dabei zu prüfen, ob jeder mit einem ihm sympathischen Partner tanzt. 

Besteht die Personengruppe aus 2x2 Personen, so sind 2 mögliche Paarungen denkbar  1. J1 mit M1 und J2 mit M2   
2. J1 mit M2 und J2 mit M1
Besteht die Personengruppe aus 3x3 Personen, so sind 6 mögliche Paarungen denkbar. 1. J1 mit M1 und J2 mit M2 und J3 mit M3
2. J1 mit M2 und J2 mit M1 und J3 mit M3
3. J1 mit M3 und J2 mit M1 und J3 mit M2
4. J1 mit M1 und J2 mit M3 und J3 mit M2
5. J1 mit M2 und J2 mit M3 und J3 mit M1
6. J1 mit M3 und J2 mit M2 und J3 mit M1
Besteht die Personengruppe aus 4x4 Personen, so sind 24 mögliche Paarungen denkbar. ...
Besteht die Personengruppe aus 5x5 Personen, so sind 120 mögliche Paarungen denkbar. ...

Im schlimmsten Fall sind dies n! Varianten, d. h. die Laufzeit des Algorithmus kann mit O(n!) abgeschätzt werden. 

Beispiele: Ein fiktiver Computer kann 106 Operationen pro Sekunde ausführen. Man berechne die Rechenzeit des Algorithmus für Eingaben der Länge n bei gegebener Komplexität O(n!).

Rechenzeit für n in Sekunden

n = 5 n = 10 n = 15 n = 20

0,00012 s

≈ 3,6 s ≈ 1,3·106
≈ 15 Tage
≈ 2,4·1012
≈ 77147 Jahre

Offensichtlich liegt ein ineffizienter Algorithmus vor, der für den praktischen Einsatz wohl kaum geeignet ist.

Lösungsvariante II

Das Problem kann auf effizientere Weise gelöst werden, indem auf die Graphentheorie zurückgegriffen wird. 

Der Algorithmus hat nun folgende Gestalt:

  1. Bilde einen Graphen, der aus 2n+2 Knotenpunkten besteht. 
    Knoten: Q, J1,..., Jn, M1,..., Mn und S
    gerichtete Kanten:  
    • von Q zu jedem Ji (i = 1,...,n)
    • von jedem Mi (i = 1,...,n) zu S eine gerichtete Kante verläuft
    • vom Knoten Ji zum Knoten Mj, falls sij = 0 ist (i,j = 1,...,n). 
  2. Falls ein gerichteten Weg von Q zu S existiert, dann gehe zu 6. 
  3. Bestimme die Anzahl Z der gerichteten Kanten, die von einem M-Knoten zu einem J-Knoten verlaufen. 
  4. Wenn Z = n ist, dann entspricht jede gerichtete Kante (Mi,Jk) einem Tanzpaar → ENDE 
  5. Wenn Z < n, dann existiert keine Tanzpaarung der gesuchten Art → ENDE 
  6. Drehe die Richtung aller Bögen des Weges von Q nach S um und gehe zu 2.

Visualisierung des Algorithmus (Powerpoint-Datei)

Es lässt sich zeigen, dass dieser Algorithmus eine Laufzeit der Ordnung O(n·m) hat, wobei m die Anzahl der Kanten im Graph ist.

Ein ähnliches Problem ist das sog. Heiratsproblem.

Auswertung

Das Problem der Tanzpaarung ist mit verschiedenen Algorithmen gelöst worden. Die Algorithmen haben ein unterschiedliches Laufzeitverhalten. Während der naive Algorithmus mit O(n!) praktisch nicht nutzbar ist, zeigt die Rückführung des Problems auf die Graphentheorie eine praktikable Lösung mit O(n·m). 

Bleibt nun die Frage: Ist es möglich zu allen Problemen Algorithmen zu finden, die maximal eine polynomiale Laufzeit haben?



zur Startseite
© Tino Hempel 1997 - 2005 Im Web vertreten seit 1994.
Eine Internet-Seite aus dem Angebot von Tino Hempel.

Für alle Seiten gilt der 
Haftungsausschluss/Disclaimer.