Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- talit:kombinatorik [2023-02-20 13:19] – [Idee] hof
+++ talit:kombinatorik [2024-10-08 06:53] (aktuell) – [Vorteile] hof
@@ Zeile 1: / Zeile 1: @@
 # Kombinatorik
 ## 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? Wie zählt man sie systematisch durch? Zustand (State) und Zustandsübergang (Transition / Move).
-      * Upper Bound: $7!\cdot8^3 = 2580480$ Kombinationen
+## 2x2x2 Rubik
-        - 8 Steine ohne Zurücklegen, also $(8-1)!$ Kombinationen
-        - jeder Stein kann in 3 verschiedenen Lagen sein, also $8^3$ Möglichkeiten für jede Kombination
+{{:talit:pasted:20230220-154900.png?200}}
-      * Aber nicht alle Kombinationen sind möglich, und andere sind äquivalent unter einer Farb-Permutation.
+### Vorteile
-  * Brute-Force-Ansätze
+  * Beschränkte Komplexität
+  * Alle Cublets sind gleich (keine Unterscheidung Edge vs. Corner vs. Middle wie beim 3er Rubik)
+### Komplexitätsrechnung
+  * Wieviele Kombinationen gibt es?
+    * 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, also $(8-1)!$ Kombinationen
+      - 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?
       * Suchbaum
       * Tiefensuche (DFS)
       * Breitensuche (BFS) (s.a. [[talit:algorithmen]])
+      * Iteratives DFS mit inkrementell steigendem Tiefenhorizont.
       * Pruning (wenn der Zustand bereits auf anderem Weg erreicht wurde - Speicherbedarf?)
     * Wie lange dauert es?
+## 3er Rubik
+  * Gute Quelle / JS Implementierung (für 3x3 Rubik): https://observablehq.com/@onionhoney/how-to-model-a-rubiks-cube
+## Weiterführende Themen
   * Grenzen von Brute-Force
     * Transfer zu Passwort-Attacke: 8 vs. 12 Zeichen
-    * 3x3x3-Rubik
+    * Schach: Abschätzung der möglichen Zustände
-    * Schach
   * Probleme mit unbekanntem Zustand (Markov-Probleme)