Thistlethwaite-algoritmus

• IPA:

Thistlethwaite-algoritmus

1. (matematika)

A Thistlethwaite-algoritmus egy csoportelméleti alapú megoldás a Rubik-kocka kirakására. Az algoritmust Morwen Thistlethwaite dolgozta ki 1981-ben, és az egyik első hatékony módszer volt a 3x3-as Rubik-kocka kirakására.

---

A Rubik-kockát egy sor alcsoportra bontjuk, amelyek egyre szűkebb megoldási teret jelentenek. Az algoritmus célja, hogy lépésről lépésre "leszűkítse" a Rubik-kocka állapotait addig, amíg el nem jutunk a végső megoldáshoz.

---

1. A Rubik-kocka forgatási műveletei egy csoportot alkotnak, amelynek állapottere 43 kvintillió lehetséges konfigurációt tartalmaz:

$${\displaystyle 4.3\times 10^{19}.}$$

1. Thistlethwaite az állapotteret alcsoportra bontja:

$${\displaystyle G_{0}\supseteq G_{1}\supseteq G_{2}\supseteq G_{3}\supseteq G_{4}=\{{\text{megoldott állapot}}\}.}$$

1. A kocka állapotát először a legnagyobb csoportból ( ${\displaystyle G_{0}}$ ) áthelyezzük egy kisebb csoportba ( ${\displaystyle G_{1}}$ ), majd lépésről lépésre egyre szűkebb alcsoportra korlátozzuk a forgatásokat.

---

• ${\displaystyle G_{0}}$: Az összes lehetséges állapot ${\displaystyle (4.3\times 10^{19})}$.
• ${\displaystyle G_{1}}$: Az állapotok, ahol az élkockák orientációja helyes.
• ${\displaystyle G_{2}}$: Az állapotok, ahol az élkockák orientációja helyes, és a sarokkockák orientációja is helyes.
• ${\displaystyle G_{3}}$: Az állapotok, ahol az élkockák és sarokkockák orientációja helyes, és az élek és sarkok permutációja részben helyes.
• ${\displaystyle G_{4}}$: A megoldott állapot.

---

1. Lépés 1: Az aktuális állapotból ${\displaystyle G_{0}}$-ból ${\displaystyle G_{1}}$-be helyezés.

  * A cél az, hogy az élkockák orientációját helyessé tegyük.

1. Lépés 2: ${\displaystyle G_{1}}$-ből ${\displaystyle G_{2}}$-be.

  * A cél az, hogy a sarokkockák orientációját helyessé tegyük.

1. Lépés 3: ${\displaystyle G_{2}}$-ből ${\displaystyle G_{3}}$-ba.

  * Az élek és sarkok részben rendezett permutációját érjük el.

1. Lépés 4: ${\displaystyle G_{3}}$-ból ${\displaystyle G_{4}}$-be (a megoldott állapotba).

  * Végül az élkockák és sarokkockák teljes permutációját helyreállítjuk.

---

• Az algoritmus biztosan megoldja a Rubik-kockát legfeljebb 52 lépésből.
• A csoportok közötti lépések száma:

  * ${\displaystyle G_{0}\to G_{1}}$: legfeljebb 7 lépés,
  * ${\displaystyle G_{1}\to G_{2}}$: legfeljebb 13 lépés,
  * ${\displaystyle G_{2}\to G_{3}}$: legfeljebb 15 lépés,
  * ${\displaystyle G_{3}\to G_{4}}$: legfeljebb 17 lépés.

$${\displaystyle {\text{Összesen}}:7+13+15+17=52\,{\text{lépés}}.}$$

---

1. Csoportok definiálása: A Rubik-kocka állapotai közötti csoportelméleti szabályok nagyon bonyolultak, ezért ezt nem könnyű programozni.
2. Megoldási stratégiák: A programban forgatási műveleteket definiálunk, majd ellenőrizzük, hogy az aktuális állapot melyik alcsoportba tartozik.
3. Heurisztika használata: A gyakorlatban az algoritmust optimalizálják heurisztikus lépésekkel, hogy gyorsabbá tegyék a megoldást.

---

A Rubik-kocka teljes állapotterének leírása itt nem lehetséges egy rövid kódban, de az alábbi példa bemutatja egy lépés orientációjának javítását egy egyszerűsített forgatási függvényekkel.

class RubiksCube:
    def __init__(self):
        self.state = self.solved_state()

    def solved_state(self):
        """Létrehoz egy megoldott állapotot."""
        return {
            'U':  * 9, 'D':  * 9,
            'F':  * 9, 'B':  * 9,
            'L':  * 9, 'R':  * 9
        }
    
    def rotate_face(self, face):
        """Egyszerű forgatás egy adott oldalra."""
        state = self.state
        self.state = [
            state, state, state,
            state, state, state,
            state, state, state
        ]

    def print_cube(self):
        for face, tiles in self.state.items():
            print(f"{face}: {tiles}")

# Példa használat
cube = RubiksCube()
print("Eredeti állapot:")
cube.print_cube()

print("\nForgatás után:")
cube.rotate_face('F')
cube.print_cube()

---

1. Rubik-kocka megoldó programok: A modern megoldók a Thistlethwaite-algoritmus továbbfejlesztett változatát használják.
2. Csoportelméleti kutatások: A Rubik-kocka megoldásának tanulmányozása segít a véges csoportok tulajdonságainak megértésében.
3. Optimalizálás: Az algoritmus a mozgások számának minimalizálására törekszik.

---

• A Thistlethwaite-algoritmus a Rubik-kocka kirakására szolgál csoportelméleti alapon.
• Az állapotteret alcsoportra bontja, és lépésről lépésre szűkíti a lehetséges állapotokat.
• A megoldás garantáltan legfeljebb 52 lépésből elérhető.
• Bár elméletileg hatékony, a gyakorlatban léteznek modernebb algoritmusok (pl. Kociemba algoritmus), amelyek gyorsabban működnek.

Ez az algoritmus mérföldkövet jelentett a Rubik-kocka matematikai vizsgálatában.

• Thistlethwaite-algoritmus - Értelmező szótár (MEK)
• Thistlethwaite-algoritmus - Etimológiai szótár (UMIL)
• Thistlethwaite-algoritmus - Szótár.net (hu-hu)
• Thistlethwaite-algoritmus - DeepL (hu-de)
• Thistlethwaite-algoritmus - Яндекс (hu-ru)
• Thistlethwaite-algoritmus - Google (hu-en)
• Thistlethwaite-algoritmus - Helyesírási szótár (MTA)
• Thistlethwaite-algoritmus - Wikidata
• Thistlethwaite-algoritmus - Wikipédia (magyar)