Hi, ich hab mal ne kleine Frage:
ich habe ein Zuordnungsproblem mit n Jungs zu m Maedels. Ungewichtet. Ausserdem hab ich einen Algorithmus von J.E.Hopcroft und R.M.Karp, welcher in O((m+n)sqrt(n)) fertig wird.
Dieser Algorithmus ist aus den 70gern.
Meine Frage, gibt es einen schnelleren ?
Hi Christian 
Was für ein Zuordnungsproblem hast du? Könntest du das etwas genauer beschreiben?
Bei n Jungs und m Mädels bleiben entweder n-m Jungs oder (m-n) Mädels übrig, je nach dem, was größer ist
cu Stefan.
Na es bleiben bestimmt noch mehr uebrig, da ja nicht jeder junge auf ein maedle passt:
Bsp:
G=(
V={J1,J2,J3,M1,M2}, [Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
Hi Christian
Ich verstehe jetzt dein Problem. Allerdings kenne ich mich in Graphenalgorithmen zu wenig aus, um dir jetzt spontan sagen zu können, wie du dein Problem am besten löst.
Da ich mit der Omega-Notation nicht so
vertraut bin …
Na, das kriegen wir schnell hin. Wenn man untersucht, wie schnell ein Algorithmus arbeitet, dann bestimmt man zunächst seine Laufzeit für N Eingabewerte. Dann versucht man anzugeben, um welchen Faktor sich die Laufzeit in etwa ändert, wenn man N mit einem Faktor multipliziert, z.B. verdoppelt. Dazu untersucht man, welcher Term in der Laufzeit für sehr große N dominiert!
Ein Beispiel. Beim klassischen Bubble-Sort werden N Zahlen sortiert, indem man die erste mit den übrigen N-1 Zahlen vergleicht, dann die zweite mit den verbliebenen N-2 Zahlen, dann die dritte mit den restlichen N-3 Zahlen, usw. Insgesamt hast du also
1+2+3+…+(N-1) = (N^2-N)/2
Vergleiche. Für große N dominiert der Term (N^2)/2. Der Faktor 1/2 interessiert uns hier nicht, da wir ja nur wissen wollen, um welchen Faktor sich die Laufzeit ändert, wenn wir N mit einem Faktor, z.B 2, multiplizieren. Daher sagen wir, Bubble-Sort hat eine Laufzeit von O(N^2). Das bedeutet, bei einer Verdopplung von N wird das Verfahren etwa 4-mal so lange arbeiten!
Du musst dir aber klar machen, dass die O-Notation nur relative Vergleiche von Laufzeiten zulässt, weil ja konstante Faktoren einfach weggelassen werden. Außerdem ist sie nur für große N richtig, für kleine N kann es Abweichungen geben, auf Grund der Terme, die wir ignoriert haben.
… kann ich nicht einschätzen,
ob O((m+n)*sqrt(n))
nun besser oder schlechte ist als z.B.
O(V^3) oder O(V*(E+V)*log(V)),
was bei einem Ford-Fulkerson-Verfahren
der Fall ist.
Tja, da musst du dir jetzt deine Werte für V,E,m und n anschauen! O(V^3) z.B. hört sich schlecht an, weil sich die Laufzeit bei einer Verdopplung der Knotenmenge um den Faktor 8 erhöhen wird! Auch O(V*(E+V)*log(V)) ist schlecht, allein schon bei einer Verdopplung von V bekommst du eine erhebliche Laufzeitzunahme. Für konstantes E ist nämlich O(V*(E+V)*log(V)=O(V^2*log V), so dass deine Laufzeit bei Verdopplung von V um
4V^2*(1+log V) / [V^2*log V] =
4/log V + 4 =
4*(1+1/log V),
also etwa um das 4-fache ansteigt! Das beste Laufzeitverhalten scheint mir noch der Algorithmus mit O((m+n)*sqrt(n)) zu haben.
Aber wie gesagt, die O-Notation ignoriert Konstanten in der Laufzeit. Daher ist es manchmal schwer, Algorithmen mit ihrer Hilfe miteinander zu vergleichen!
cu Stefan.
Hi Stefan,
cool, echt vielen Dank, das hab ich kapiert.
Das mit dem Faktor interessiert mich fast garnicht, da ich versuche herauszukriegen, wie gross mein Problem so in etwa werden darf um so in etwa zwei bis drei stunden lösbar zu sein (ich hoffe mal so auf ca 20000 Jungs und 20000 Maedels bei etwa 10 Kanten je Knoten). Eigentlich sollen die Kanten aber auch gewichtet sein, aber zum Einstieg halt erstmal der ungewichtete Fall… Wenn ich fertig bin, und dieser Artikel ist noch im Forum, werd ich mich nochmal melden.
ciao, Christian
Hi Christian
Ich hab mal in meinen alten Studienunterlagen gewühlt. Da steht eine klare Definition von O(…) drin:
Sei f:N->N eine Funktion, dann bezeichnet man mit O(f) die Menge aller Funktionen g:N->N, für die gilt: Es gibt ein reelles c>0 und ein n0 aus N, so dass für alle n>n0 gilt: g(n)