Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
| Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung Nächste Überarbeitung | Vorherige Überarbeitung | ||
| talit:kombinatorik [2023-02-20 14:26] – [Idee] hof | talit:kombinatorik [2024-10-08 06:53] (aktuell) – [Vorteile] hof | ||
|---|---|---|---|
| Zeile 3: | Zeile 3: | ||
| Einführung in Komplexitätsrechnung an einem Spiel ohne hidden state. Wie berechnet sich die Anzahl Kombinationen? | Einführung in Komplexitätsrechnung an einem Spiel ohne hidden state. Wie berechnet sich die Anzahl Kombinationen? | ||
| - | |||
| ## 2x2x2 Rubik | ## 2x2x2 Rubik | ||
| + | {{: | ||
| + | ### Vorteile | ||
| * Beschränkte Komplexität | * Beschränkte Komplexität | ||
| * Alle Cublets sind gleich (keine Unterscheidung Edge vs. Corner vs. Middle wie beim 3er Rubik) | * Alle Cublets sind gleich (keine Unterscheidung Edge vs. Corner vs. Middle wie beim 3er Rubik) | ||
| - | * Komplexitätsrechnung | + | |
| - | * Wieviele Kombinationen gibt es? | + | |
| - | * Upper Bound: $7!\cdot7^3 = 1728720$ Kombinationen | + | ### Komplexitätsrechnung |
| - | - Einen Stein betrachten wir als fix und orientieren uns dran. | + | * Wieviele Kombinationen gibt es? |
| - | - Die 7 restlichen Steine können frei permutiert werden, ohne Zurücklegen, | + | * Upper Bound: $7!\cdot3^7 = 11022480$ Kombinationen |
| - | - jeder der 7 restlichen Steine kann in 3 verschiedenen Lagen sein, also $7^3$ Möglichkeiten für jede Kombination | + | - Einen Stein betrachten wir als fix und orientieren uns dran. |
| - | * Aber nicht alle Kombinationen sind möglich, und andere sind äquivalent unter einer Farb-Permutation. | + | - Die 7 restlichen Steine können frei permutiert werden, ohne Zurücklegen, |
| + | - jeder der 7 restlichen Steine kann in 3 verschiedenen Lagen sein, also $3^7$ Möglichkeiten für jede Kombination | ||
| + | * Aber nicht alle Kombinationen sind möglich, und andere sind äquivalent unter einer Farb-Permutation. | ||
| + | |||
| + | ### Codierung | ||
| * Wie lässt sich ein Würfel darstellen / codieren? | * Wie lässt sich ein Würfel darstellen / codieren? | ||
| * Buchstabe für jede Farbe (Red, Green, Blue, Yellow, White, Orange) oder Seite (Up, Down, Front, Back, Left, Right) | * Buchstabe für jede Farbe (Red, Green, Blue, Yellow, White, Orange) oder Seite (Up, Down, Front, Back, Left, Right) | ||
| * Koordinatennetz mit planarer Sicht | * Koordinatennetz mit planarer Sicht | ||
| - | * String oder Array mit Länge $6*4 = 24$ | + | * String oder Array mit Länge $6*4 = 24$ |
| - | * Brute-Force-Ansätze | + | * andere Ansätze (Bitfield...) |
| + | * Objektorientierter Ansatz: | ||
| + | * Codierung ist interne Angelegenheit des Würfels | ||
| + | |||
| + | ### Lösungsansätze | ||
| + | * Brute-Force | ||
| * Wie kann ich alle systematisch durchprobieren? | * Wie kann ich alle systematisch durchprobieren? | ||
| * Suchbaum | * Suchbaum | ||
| Zeile 27: | Zeile 37: | ||
| * Pruning (wenn der Zustand bereits auf anderem Weg erreicht wurde - Speicherbedarf? | * Pruning (wenn der Zustand bereits auf anderem Weg erreicht wurde - Speicherbedarf? | ||
| * Wie lange dauert es? | * Wie lange dauert es? | ||
| + | |||
| ## 3er Rubik | ## 3er Rubik | ||
hof