Thistlethwaite-algoritmus

Magyar

Kiejtés

• IPA: [ ˈthiʃtlɛtxvɒjitɛɒlɡoritmuʃ]

Főnév

Thistlethwaite-algoritmus

1. (matematika)

Thistlethwaite-algoritmus

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.

---

Lényege

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.

---

Csoportelméleti háttér

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

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

1. Thistlethwaite az állapotteret alcsoportra bontja:

$$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 ( $G_{0}$ ) áthelyezzük egy kisebb csoportba ( $G_{1}$ ), majd lépésről lépésre egyre szűkebb alcsoportra korlátozzuk a forgatásokat.

---

Csoportok magyarázata

• $G_{0}$: Az összes lehetséges állapot $(4.3\times 10^{19})$.
• $G_{1}$: Az állapotok, ahol az élkockák orientációja helyes.
• $G_{2}$: Az állapotok, ahol az élkockák orientációja helyes, és a sarokkockák orientációja is helyes.
• $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.
• $G_{4}$: A megoldott állapot.

---

Thistlethwaite-algoritmus lépései

1. Lépés 1: Az aktuális állapotból $G_{0}$-ból $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: $G_{1}$-ből $G_{2}$-be.

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

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

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

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

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

---

Fontos tulajdonságok

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

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

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

---

Algoritmus implementálása és kihívások

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.

---

Egyszerűsített Python implementáció

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': ['W'] * 9, 'D': ['Y'] * 9,
            'F': ['G'] * 9, 'B': ['B'] * 9,
            'L': ['O'] * 9, 'R': ['R'] * 9
        }
    
    def rotate_face(self, face):
        """Egyszerű forgatás egy adott oldalra."""
        state = self.state[face]
        self.state[face] = [
            state[6], state[3], state[0],
            state[7], state[4], state[1],
            state[8], state[5], state[2]
        ]

    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()

---

Alkalmazások

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.

---

Összefoglalás

• 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.

Fordítások

Tartalom

angol: Thistlethwaite's algorithm (en)

További információk

• 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)