< />
Szerző: Balázs R.
2010. augusztus 13.

Megoldódott a Rubik-kocka rejtély

Az eredményt közzétevő csapat a Google számítási teljesítményét és jópár matematikai csavart ötvözve végig ellenőrizte az összes, 43 kvintrillió lehetséges összekevert pozíciót, amit a kocka fel tud venni, megfejtve ezzel a híres kocka legnagyobb matematikai rejtvényét.

Az elsődleges áttörést egy, a csoportelmélet elnevezésű matematikai ágból vett technikának köszönhették, magyarázta Tomas Rokicki, kaliforniai programozó, aki az elmúlt 15 évet annak a legkisebb számnak a keresésével töltötte, amivel a kocka bármelyik elrendezése kirakható. Az "Isten számaként" is emlegetett értékről 2008-ban számoltunk be legutóbb, amikor Rokicki 22-re csökkentette, azonban már akkor is egyértelmű volt, hogy ez még nem a legkisebb szám.

A csoportelméletből származtatott technikával először felosztották az összes lehetséges kezdő konfigurációt 2,2 milliárd csoportra, melyek mindegyike 19,5 milliárd elrendezést foglalt magába, annak megfelelően hogyan reagálnak ezek a konfigurációk a kocka tekergetésének 10 lehetséges mozdulatára. A kocka különböző szimmetriáit kihasználva a projekten dolgozó matematikusoknak sikerült a csoportok számát 56 millióra csökkenteniük, mondván például, ha egy összekevert kockát egyszerűen az oldalára, vagy fejjel lefelé fordítunk, azzal nem lesz nehezebb a kirakása, tehát ezeket az egyenértékű pozíciókat máris el lehetett vetni. Ettől azonban még rengeteg ellenőrizendő induló konfiguráció maradt, ezért a csapat kidolgozott egy algoritmust a folyamat felgyorsítására.


A korábbi módszerekkel másodpercenként körülbelül 4000 kockát tudtak végig próbálni, az algoritmus megvizsgált egy sorozat induló mozdulatot, majd meghatározta, hogy az eredményként kapott pozíció közelebb van-e a megoldáshoz. Ha nem, akkor az algoritmus elvetette ezeket a lépéseket és újra indult. Rocicki felismerte, hogy ezek a zsákutcába torkolló lépések valójában más kiindulási pozíciók megoldásai, ami elvezette egy algoritmushoz, mellyel egy másodperc alatt egymilliárd kockát tudott kipróbálni. Ez a metódus olyan, mintha egy barátunkat meglátogatnánk egy számunkra ismeretlen városban, megkapjuk tőle az útirányt, hogy mikor forduljunk jobbra vagy balra, viszont azt nem árulta el, hogy mi is valójában a kiindulási pontunk. Ha egy véletlenszerű pontról kiindulva követjük az iránymutatást, igen csekély esélyünk lesz eljutni a célállomáshoz, ha azonban sikerül összeilleszteni a megfelelő kiinduló ponttal, akkor biztosan odaérünk.

A csapat algoritmusa a kissé leegyszerűsített példánkhoz hasonlóan, rendkívüli sebességgel párosítja a mozdulatokat a megfelelő kiinduló ponttal, így egy 19,5 milliárdos sorozatot 20 másodperc alatt meg tudnak oldani, ami döbbenetes sebességnek tűnik, de még így is 35 évig tartana egy hagyományos számítógép számára a teljes feladat megoldása, ezért a csapat egy újabb huszárvágást eszközölt a megoldás érdekében. John Dethridge, a Google egyik mérnöke a számítógépes birodalom szabad számítási kapacitásának felhasználásával néhány hét alatt megoldotta a problémát.

Azt már évek óta tudták, hogy a Rubik-kocka egyes konfigurációi csupán 20 forgatást igényelnek - sok matematikus sejtette is, hogy egyik elrendezésnek sincs szüksége ennél többre, a 15 éves kitartó kutatás azonban megerősítette feltevésüket. "Az ilyen kutatások példázzák, hogyan használható a tiszta matematika a nagy számítási kapacitást igénylő problémák leegyszerűsítésére" - tette hozzá Mark Kambites, a Manchester Egyetem egyik matematikusa, aki nem vett részt Rocki csapatának munkájában.



Forrás: sg.hu
Küldje tovább! Nyomtatható verzió Vissza a lap tetejére
Hozzászólás írása:
Kérjük írja be az ellenőrző kódot!
Atomerőműben Dolgozók Érdekvédelmi Szervezete AES-Tisza Erőmű Kft. VDSZSZ Tagszakszervezet Ajkai Hőerőmű Munkavállalóinak Szakszervezete Budapesti Erőművek Szakszervezete Villamosenergiaipari Dolgozók Szakszervezeti Szövetsége Borsodi Energetikai Kft. Szakszervezeti Bizottsága Dél-dunántúli Áramszolgáltató Dolgozóinak Szakszervezete Dél-magyarországi Áramszolgáltató Társaságcsoport Szakszervezete Dunamenti Hőerőmű Vállalat Munkástanács Dunántúli Villamosenergia-ipari Szakszervezet Elektromos Szakszervezet Energiaipari Karbantartók Szakszervezete Észak-Magyarországi Áramszolgáltató Dolgozóinak Szakszervezete Északdunántúli Villamosenergia-ipari Szakszervezet Ifjúsági Tagozat Komlói Fűtőerőmű Zrt. Dolgozóinak Szakszervezete Miskolci Erőmű Szakszervezet Műszakos Dolgozók Érdekvédelmi Szervezete Mátrai Erőmű Villamos Szakszervezete MVM Magyar Villamos Művek Dolgozóinak Szakszervezete MVM Társaságcsoporti Szakszervezeti Szövetség Nyugdíjas Tagozat VDSZSZ OVIT Rt. Tagszakszervezet Paksi Atomerőmű Dolgozóinak Szakszervezete Pannonpower Rt. Villamosenergia-ipari Dolgozóinak Szakszervezete Schneider Electric Rt. Szakszervezet Tiszavíz Vízerőmű Kft. Munkavállalóinak Szakszervezete Tiszántúli Villamosenergia-ipari Szakszervezet Villamosenergia-ipari Dolgozók Szakszervezeti Szövetsége ERBE Kft. Szakszervezete Villkesz Kft. Szakszervezete Villamosenergia-ipari Munkavállalók Érdekvédelmi Szervezete Villamosenergia-ipari Munkavédelmi Képviselők Fóruma Villamosenergia-ipari Rendszerirányító és Üzemeltető Szakszervezete Villamosenergia-ipari Üzemi Tanácsok Fóruma
A Szakszervezetek.hu Press legfrissebb hírei

Szolgáltatások

2016.01.13 07:01 - Aliraza521

Csalnak-e a munkáltatók?

2015.01.06 07:39 - mariamunir

Erőművek és Szolgáltatók

2015.01.02 12:51 - qudsia

Mi újság a PADOSZ-nál?

2015.01.02 12:51 - qudsia
Még több téma...