Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
| Nächste Überarbeitung | Vorherige Überarbeitung | ||
| talit:kombinatorik [2023-02-20 08:11] – angelegt 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 (z.B. 2x2x2 Rubik) | + | |
| - | * Wieviele Kombinationen gibt es? | + | Einführung in Komplexitätsrechnung an einem Spiel ohne hidden state. Wie berechnet sich die Anzahl Kombinationen? |
| - | * Brute-Force-Ansätze | + | ## 2x2x2 Rubik |
| + | |||
| + | {{: | ||
| + | ### Vorteile | ||
| + | * Beschränkte Komplexität | ||
| + | * Alle Cublets sind gleich (keine Unterscheidung Edge vs. Corner vs. Middle wie beim 3er Rubik) | ||
| + | |||
| + | |||
| + | ### | ||
| + | | ||
| + | * 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? | ||
| + | * 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