Hallo Leute,
ich möchte den Rechenaufwand für einen bestimmten Algorithmus abschätzen, und hoffe daß ihr mir dabei helfen könnt.
Zunächst mal ein vereinfachtes Beispiel:
Wenn ich wissen möchte wie viele Möglichkeiten es gibt um n Objekte in einer Reihe anzuordnen, so errechne ich das ja mit n!, richtig?
also bei 5 Objekten gäbe es dann 5! = 120 Möglichkeiten
Wenn man eine Liste mit n Objekten hätte geht es also im wesentlichen darum, daß nach dem platzieren eines Objektes noch n-1 Objekte übrig sind. Die Länge der Liste verringert sich also nach jedem Schritt um 1.
soweit so gut...
mein Problem ist leider etwas komplizierter
ich habe n Muster, die in einer Reihe angeordnet werden sollen, wobei es für jedes Muster aber nicht n-1 sondern m mögliche Nachfolger gibt. Außerdem verringert sich die Länge der Liste nicht um 1, sondern um k.
n ist festgelegt, m und k sind aber von Muster zu Muster unterschiedlich, so daß nur Durchschnittswerte bekannt sind.
Wie kann ich die Anzahl der möglichen Kombinationen anhand dieser Werte abschätzen?
Falls euch das zu theoretisch ist, dürft ihr natürlich auch gerne irgendein Zahlenbeispiel nutzen, z.B. 100 Muster mit jeweils durchschnittlich 125 möglichen Nachfolgern (ja, m kann größer sein als n, muss aber nicht), wobei in jedem Schritt vielleicht ca. 3 Muster wegfallen.
Irgendwelche Ideen?
PS:
nein, es ist definitiv nicht möglich einfach alle Kombinationen zu berechnen und diese dann zu zählen, denn selbst 100 Muster (im "einfachen" Fall also 9*10^157 Kombinationen!!) sind noch ein sehr harmloses Beispiel, es können genausogut auch 1000 oder sogar 10000 Muster sein.
So viele Treppen und so wenig Zeit!
Hi,
JoWenn ich wissen möchte wie viele Möglichkeiten es gibt um n Objekte in einer Reihe anzuordnen, so errechne ich das ja mit n!, richtig?
So jetzt zu deinem Problem:
Ich würde sagen n*m^(n/k-1)
MfG Jeffrey
edit: ich hoff ich hab die Aufgabe richtig verstanden. Für was brauchst du das denn? Vielleicht versteht man es dann besser
Naja, um Muster in einer bestimmten Art anzuordnen...ich hoff ich hab die Aufgabe richtig verstanden. Für was brauchst du das denn? Vielleicht versteht man es dann besser
Ich versuche mal es etwas anschaulicher zu erklären...
Nehmen wir mal folgende Situation:
Es gibt 5 (Spiel-)Würfel in verschiedenen Farben, die in eine Reihe gelegt werden sollen.
Berücksichtigt man dabei nur die Farbe, so gibt es dafür 5! = 120 verschiedene Möglichkeiten.
Und jetzt stelle man sich 5 Listen vor, eine für jeden Würfel...
und auf jeder Liste steht jeweils welche Würfel man rechts neben den Würfel legen darf zu dem die Liste gehört.
Und als wenn das noch nicht kompliziert genug wäre, stehen nicht nur die Farben der "erlaubten" Nachbarn auf diesen Listen, sondern jeweils auch noch welche Zahl oben liegen muss.
so könnte auf einer Liste für einen grünen Würfel z.B. stehen
rot 1
rot 3
rot 4
blau 6
gelb 5
gelb 6
Und jetzt ist die Frage eben, wieviele mögliche Kombinationen es gibt, wenn man diese Randbedingungen berücksichtigt.
Bekannt sind, wenn wir mal beim Würfelbeispiel bleiben, die Anzahl der Würfel (n), die durchschnittliche Gesamtlänge einer Liste (m), und wie oft eine Farbe durchschnittlich auf so einer Liste vorkommt (k).
Natürlich sind die Listen selbst auch alle bekannt, aber ich wüsste nicht was man außer m und k davon noch benötigen könnte, um die Anzahl der möglichen Kombinationen zu berechnen.
Sowohl m als auch k bewegen sich übrigens bei allen Listen etwa in der gleichen Größenordnung, die Verwendung der Mittelwerte sollte also eine ganz ordentliche Schätzung ermöglichen.
Ich hoffe mal, daß diese Beschreibung mein Problem etwas verständlicher darstellt.
Wäre diese Formel unter Berücksichtigung meiner verbesserten Problembeschreibung noch korrekt?n*m^(n/k-1)
So viele Treppen und so wenig Zeit!
Mal ne dumme Frage ist das jetzt ein Urnenproblem mit Zurücklegen oder ohne? Oben sprichst du von 5 verschieden Farbige Würfel, die nacheinander hingelegt werden. Bei deiner Liste, legst du dann manche dreimal hin. Hast du jetzt die Würfel beliebig oft zur Hand (mit zurücklegen) oder nicht?
und das durschnittliche Vorkommen einer Farbe ist ein bisschen komisch. Dann gehst du ja von einem Erwartungswert aus.
Ich überleg mirs mal genauer aber vielleicht wählst du noch ein anderes beispiel bzw. präzisierst dein genanntes.
Danke ich freu mich schon auf die Aufgabe!
Martin
Es gibt in meinem Beispiel nur die 5 genannten Würfel, diese dürfen allerdings nicht beliebig aneinandergereiht werden...
(die Listen geben nicht an was hingelegt wurde, sondern was neben einen bestimmten Würfel gelegt werden darf, und wie)
Wenn man also den grünen Würfel aus dem Beispiel betrachtet, so darf man daneben entweder den roten, den blauen oder den gelben legen...
aber nicht irgendwie, sondern nur in einer bestimmten Ausrichtung...
wählt man den roten aus, so muss entweder die 1, die 3 oder die 4 oben liegen, alles andere ist nicht erlaubt.
Mit dem durchschnittlichen Vorkommen einer Farbe meine ich einfach nur, daß wenn man die Listen betrachtet, jeder Würfel (also jede Farbe) durchschnittlich k mal vorkommt.
bei der Beispielliste gibt es rot dreimal, blau einmal und gelb zweimal... Mittelwert davon ist 2, also wäre k für diese Liste 2. Allerdings ist das oben erwähnte k wiederum der Mittelwert für alle Listen... das stellt aber kein Problem dar, da k bei allen Listen ungefähr gleich groß ist
So viele Treppen und so wenig Zeit!
Hi,
ich blick jetzt leider net, wirklich, was k ist. Du hast doch gemeint, dass k die Zahl ist, um die sich die Listenlänge reduziert.
Bei deinem Würfelbeispiel stimmt das mit den Nachfolgern ja nicht ganz. bei deinem Beispiel hast du weiterhin nach dem ersten zug noch 4 weitere würfel. Also bleibt die anzahl an möglichkeiten weiter 120. du kannst dann halt die würfel nur in einer bestimmten art anordenen.
mfg jeffrey
Ok, da habe ich mich etwas unklar ausgedrückt...Zitat von jeffrey
ich denke mein neues Beispiel ist etwas eindeutiger
Stimmt, es bleiben 4 Würfel übrig, aber es müssen trotzdem mehr Möglichkeiten sein als 120.Bei deinem Würfelbeispiel stimmt das mit den Nachfolgern ja nicht ganz. bei deinem Beispiel hast du weiterhin nach dem ersten zug noch 4 weitere würfel. Also bleibt die anzahl an möglichkeiten weiter 120. du kannst dann halt die würfel nur in einer bestimmten art anordenen.
Warum das so ist, versuche ich mit einem neuen Beispiel zu erklären.
====================
Also ich gehe das mal konkret für ein paar Würfel durch, in der Hoffnung daß ich es schaffe es verständlich zu erklären...
Vorbedingungen:
- Es sind 5 (Spiel-)Würfel in 5 verschiedenen Farben vorhanden, z.B. rot, grün, blau, gelb und weiß
- Es gibt für jeden Würfel eine Liste, also eine rote, eine grüne, eine blaue etc.
Die Würfel sollen jetzt in eine Reihe gelegt werden, wobei der Ablauf wie folgt aussehen könnte:
1. Ich nehme einen der Würfel, z.B. den blauen, und lege ihn irgendwie hin. (welche Zahl nach oben zeigt spielt keine Rolle)
2. Ich schaue auf die blaue Liste, denn dort steht welche Würfel ich rechts neben den blauen legen darf, z.B. rot, grün und weiß.
3. Ich nehme einen der "erlaubten" Würfel, vielleicht den weißen, und schaue ein weiteres mal auf die blaue Liste, um festzustellen welche Zahlen beim weißen Würfel oben liegen dürfen wenn man ihn rechts neben den blauen Würfel legt. Also angenommen auf der blauen Liste steht zweimal "weiß", und zwar einmal mit einer 3 und einmal mit einer 5, dann darf ich den weißen Würfel entweder mit der 3 oder mit der 5 nach oben neben den blauen Würfel legen.
4. Es liegen jetzt 2 Würfel auf dem Tisch, der blaue in irgendeiner beliebigen Orientierung, und der weiße rechts daneben, z.B. mit der Zahl 3 nach oben (aber nicht etwa mit der 4 oder der 1, denn diese standen nicht zur Verfügung)
5. Ich nehme die weiße Liste zur Hand, und sehe nach welche Würfel ich rechts neben den weißen Würfel legen darf, vielleicht blau und gelb. Da der blaue bereits auf dem Tisch liegt muss ich den gelben wählen.
6. Ich sehe nochmal auf der weißen Liste nach, welche Zahlen beim gelben Würfel oben liegen dürfen, wenn er rechts neben dem weißen Würfel liegt, vielleicht die 1, 2, 5 und 6, und lege den Würfel mit einer dieser Zahlen nach oben rechts neben den weißen Würfel.
etc. etc. etc.
also nochmal zusammengefasst:
Zu jedem Würfel existiert eine Liste, und auf dieser Liste steht drauf, welche anderen Würfel rechts neben den zur Liste gehörenden Würfel gelegt werden dürfen, und welche der 6 theoretisch möglichen Orientierungen jeweils erlaubt sind.
Und gesucht ist wie gesagt die Anzahl aller möglichen Kombinationen, die aber mit Sicherheit deutlich über 120 liegen wird, da ja bei jedem Schritt unter Umständen mehr Varianten zur Auswahl stehen können, als noch Würfel übrig sind.
Nehmen wir dazu nur mal den grünen Würfel vom letzten Beispiel...
dessen Liste hatte 6 Einträge, obwohl es neben dem grünen nur 4 weitere Würfel gibt.
Bei den Listen ist es dabei wie gesagt so, daß alle ungefähr gleich lang sind, und auch eine ähnliche Anzahl an Farben (also anderen Würfeln) enthalten. Die Listen enthalten vielleicht durchschnittlich 6 Einträge (das ist m), und es stehen durchschnittlich 3 verschiedene Würfel drin. Die in einer Liste vorhandenen Würfel wären also im Schnitt mit jeweils 2 Einträgen vertreten (das ist k).
edit:
falls m und k zur Berechnung der möglichen Kombinationen ungeeignet sind, können natürlich auch irgendwelche anderen Größen verwendet werden, die sich aus den Listen gewinnen lassen.
(die Listen selbst sind ja alle vorhanden)
Oder wenn ihr mögt stellt euch keine Würfel vor, sondern vielleicht Pokerchips oder sowas...
in diesem Fall gäbe es dann jeweils 6 Chips von einer Farbe, die eben mit unterschiedlichen Nummern beschriftet sind.
(wobei dann aber jede Farbe nur einmal verwendet werden dürfte)
So viele Treppen und so wenig Zeit!
hi,
ich glaube, jetzt blick ich es mehr, ein würfel hat jetzt also nicht mehr nur noch eine eigenschaft, sondern 6 + farbe.
jetzt ist nur noch die frage, wieviele würel es insgesammt gibt. n? und jedes mal wird es einer weniger? also sind insgesamt n durchgänge zu machen?
wieviele möglichkeiten gibt es beim ersten mal hinlegen? beim würfelbeispiel n*6, nennen wir es mal r.
aus der liste fliegen also immer die möglichkeiten raus, welche farben schon gezogen sind.
dann müsste als formel folgendes gelten:
r*m*(m-k)*(m-2k)*(m-3k)*...*(m-(n-3)k)*(m-(n-2)k)
wie das jetzt als formel mit hochzahlen und fakultät aussieht weiß ich nicht, ka, ob das überhaupt geht, aber rekursiv sollte sich das ganz berechnen lassen.
so, hoffe dir damit geholfen zu haben, und dass das stimmt.
mfg jeffrey
genau
ok, soweit klar...wieviele möglichkeiten gibt es beim ersten mal hinlegen? beim würfelbeispiel n*6, nennen wir es mal r.
bei 5 Würfeln wäre das also 30
(bei meiner Eigentlichen Anwendung läge dieser Wert irgendwo zwischen 144 und 14400)
seh ich auch so, allerdings fällt mir dabei gerade auf, daß k vielleicht doch etwas ungeschickt gewählt ist...aus der liste fliegen also immer die möglichkeiten raus, welche farben schon gezogen sind.
Es steht ja nicht jeder Würfel in jeder Liste, wenn man einen Würfel ablegt fällt bei manchen Listen also garnichts weg, und bei anderen vielleicht 2 oder 3 Einträge. Ich vermute da wäre es wohl besser k so zu definieren, daß es die Häufigkeit jedes Würfels in jeder Liste angibt... ok, schlecht erklärt... also bei der Liste vom grünen Würfel war rot 3x, blau 1x und gelb 2x drin. Addiert wären das 6, und es stehen 3 Würfel in der Liste, also wäre k dann 2, aber es ist wohl sinnvoller auch die nicht vorhandenen Würfel zu berücksichtigen also statt 6/3 eben 6/4 = 1,5 zu nehmen, weil der 4. verbleibende Würfel eben 0x in der Liste steht...
danke für die Formel,r*m*(m-k)*(m-2k)*(m-3k)*...*(m-(n-3)k)*(m-(n-2)k)
ich gehe das mal Schritt für Schritt durch...
- Am Anfang gibt es r Möglichkeiten
- Beim zweiten Schritt gibt es dann für jeden "Anfangswürfel" nochmal m Mögliche Nachfolger
- Beim dritten Schritt fallen durchschnittlich etwa k Einträge aus allen Listen weg, es bleiben also dann nurnoch m-k mögliche Nachfolger
und das geht dann so weiter, aber nur bis (n-2)*k, weil k ja bei den ersten beiden Schritten noch nicht beachtet wurde.
habe ich das so richtig verstanden?
So viele Treppen und so wenig Zeit!
hi
genau, es gibt ja n ziehungen, deswegen nur bis n-2. m ist ja (n-1)*k, zumindest bei dem neuen k. ich denke, dass sollte so einigermaßen hin kommen.und das geht dann so weiter, aber nur bis (n-2)*k, weil k ja bei den ersten beiden Schritten noch nicht beachtet wurde.
mfg jeffrey
Berechtigungen
Zitieren
Lesezeichen