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:00] – [Idee] hof | talit:kombinatorik [2024-10-08 06:53] (aktuell) – [Vorteile] hof | ||
|---|---|---|---|
| Zeile 1: | Zeile 1: | ||
| # Kombinatorik | # Kombinatorik | ||
| ## Idee | ## Idee | ||
| - | * Komplexitätsrechnung an einem einfachen Beispiel einführen | + | |
| - | * Wieviele Kombinationen gibt es? | + | Einführung in Komplexitätsrechnung an einem Spiel ohne hidden state. Wie berechnet sich die Anzahl Kombinationen? |
| - | * Upper Bound: $7!\cdot8^3 = 2580480$ Kombinationen | + | ## 2x2x2 Rubik |
| - | - 8 Steine ohne Zurücklegen, | + | |
| - | - jeder Stein kann in 3 verschiedenen Lagen sein, also $8^3$ Möglichkeiten für jede Kombination | + | {{: |
| - | * Aber nicht alle Kombinationen sind möglich, und andere sind äquivalent unter einer Farb-Permutation. | + | ### Vorteile |
| - | * Wie lässt sich ein Würfel darstellen / codieren? | + | * Beschränkte Komplexität |
| - | * Buchstabe für jede Farbe (Red, Green, Blue, Yellow, White, Orange) oder Seite (Up, Down, Front, Back, Left, Right) | + | * Alle Cublets sind gleich (keine Unterscheidung Edge vs. Corner vs. Middle wie beim 3er Rubik) |
| - | * Koordinatennetz mit planarer Sicht | + | |
| - | * String oder Array mit Länge $6*4 = 24$ | + | |
| - | * Brute-Force-Ansätze | + | ### |
| + | | ||
| + | * Upper Bound: $7!\cdot3^7 = 11022480$ Kombinationen | ||
| + | - Einen Stein betrachten wir als fix und orientieren uns dran. | ||
| + | - Die 7 restlichen | ||
| + | - jeder der 7 restlichen Steine | ||
| + | * Aber nicht alle Kombinationen sind möglich, und andere sind äquivalent unter einer Farb-Permutation. | ||
| + | |||
| + | ### Codierung | ||
| + | | ||
| + | * Buchstabe für jede Farbe (Red, Green, Blue, Yellow, White, Orange) oder Seite (Up, Down, Front, Back, Left, Right) | ||
| + | * Koordinatennetz mit planarer Sicht | ||
| + | * String oder Array mit Länge $6*4 = 24$ | ||
| + | * 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 | ||
| * Tiefensuche (DFS) | * Tiefensuche (DFS) | ||
| * Breitensuche (BFS) (s.a. [[talit: | * Breitensuche (BFS) (s.a. [[talit: | ||
| + | * Iteratives DFS mit inkrementell steigendem Tiefenhorizont. | ||
| * 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