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:07] – [Idee] hof | talit:kombinatorik [2024-10-08 06:53] (aktuell) – [Vorteile] hof | ||
|---|---|---|---|
| Zeile 1: | Zeile 1: | ||
| # Kombinatorik | # Kombinatorik | ||
| ## Idee | ## Idee | ||
| - | * Gute Quelle / JS Implementierung | + | |
| - | * Komplexitätsrechnung an einem einfachen Beispiel einführen | + | Einführung in Komplexitätsrechnung an einem Spiel ohne hidden state. Wie berechnet sich die Anzahl Kombinationen? |
| - | * Wieviele Kombinationen gibt es? | + | ## 2x2x2 Rubik |
| - | * Upper Bound: $7!\cdot7^3 = 1728720$ Kombinationen | + | |
| - | - Einen Stein betrachten wir als fix und orientieren uns dran. | + | {{: |
| - | - Die 7 restlichen Steine können frei permutiert werden, ohne Zurücklegen, | + | ### Vorteile |
| - | - jeder der 7 restlichen Steine kann in 3 verschiedenen Lagen sein, also $7^3$ Möglichkeiten für jede Kombination | + | * Beschränkte Komplexität |
| - | * Aber nicht alle Kombinationen sind möglich, und andere sind äquivalent unter einer Farb-Permutation. | + | * Alle Cublets sind gleich |
| + | |||
| + | |||
| + | ### | ||
| + | | ||
| + | * Upper Bound: $7!\cdot3^7 = 11022480$ Kombinationen | ||
| + | - Einen Stein betrachten wir als fix und orientieren uns dran. | ||
| + | - 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 21: | 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 | ||
| + | |||
| + | * Gute Quelle / JS Implementierung (für 3x3 Rubik): https:// | ||
| + | |||
| + | ## Weiterführende Themen | ||
| * Grenzen von Brute-Force | * Grenzen von Brute-Force | ||
| * Transfer zu Passwort-Attacke: | * Transfer zu Passwort-Attacke: | ||
| - | | + | * Schach: Abschätzung der möglichen Zustände |
| - | | + | |
| * Probleme mit unbekanntem Zustand (Markov-Probleme) | * Probleme mit unbekanntem Zustand (Markov-Probleme) | ||
| + | |||
hof