Izvor: Politika, 25.Sep.2007, 12:00 (ažurirano 02.Apr.2020.)
Rubikova kocka u 26 poteza
Sećate li se kocke koju je 1974. izmislio Mađar Erne Rubik? Kakva je pomama zavladala među mladima, a i među starijima, u tome ko će brže da manje kockice namesti da na svakoj strani budu u istoj boji.
A od broja mogućih koraka do samog cilja da vas zaboli glava: 43 kvadriliona (43 x 1018 ili 43 i još 18 nula)! E sada se ta glavolomna igra vratila naučnicima u glavu, ali ne u doslovnom smislu. Čak ni superkompjuteri nisu još u stanju da proračunaju sve moguće načine preuređenja >> Pročitaj celu vest na sajtu Politika << (kombinacija) u razumnom roku. A svaku je moguće, kako su objavili američki naučnici, rešiti u samo 26 poteza!
Na svojevrsnom svetskom prvenstvu, maja ove godine u Španiji, pobednik je to uradio za – 9,86 sekundi.
Džin Kuperman sa Nortistern univerziteta (SAD) osmislio je, sa svojim saradnikom na doktorskim studijama Denijelom Kanklom, računarski program kojim je dokazao da se svaka može složiti u najviše 26 poteza, što je za jedan manje od dosadašnjeg rekorda (27). Smislili su inteligentnu matematičku i računarsku strategiju da ubrzaju izračunavanje (sto miliona puta u sekundi). Učeni ljudi su odavno poduhvat nazvali traganjem za "božjim brojem".
Da biste ga ugledali na monitoru, morali biste da upregnete 128 procesora da pređu bez prestanka 83 sata ili lični računar, čak, 8.000 sati.
Ako je, na primer, jedna strana u istoj boji, zadatak je rešen bez obzira na kojoj strani je koja boja. Određujući sva sklapanja kao istovetna kada su samo dve boje međusobno zamenjene, ovi istraživači su smanjili broj na nešto više od 1.000.000.000.000.000.000 (kvadrilion) kombinacija.
Zatim su razmotrili sklopove koji se mogu dobiti jednostavnim okretanjem za pola kruga, bez obrtanja za četvrtinu kruga. Samo 15.000 izbora je moguće izvesti na takav način, svaki slučaj s takvim "posebnim konfiguracijama" presloži se s 13 ili manje poteza.
Potom su proverili kako se ma koje nasumično obrtanje pretvori u tih 15.000 "posebnih konfiguracija". Grupisali su ih ponovo u grupe sa onima koje se mogu preobratiti jedna u drugu okretima za pola kruga. Grupe su bile tako obrazovane da niz poteza koji jedan sklop prevodi u "posebnu konfiguraciju" takođe pretvara svaku drugu iz iste u "posebnu konfiguraciju".
Konačno su dobili 1.400.000.000 (milijarda i 400 miliona) takvih grupa.
A posle su proračunavanje prepustili superkompjuteru pomogavši mu svojim strategijama – da neposredno pristupa podacima veoma tačno uskladištenim na tvrdom disku bez pretraživanja (sedam terabajta), što je znatno ubrzalo posao. Nakon 63 sata rada mašina je izbacila podatak da je potrebno izvesti, najviše, 16 poteza da bi se ma koje nasumično ustrojstvo kockica složilo u posebno.
Imajući u vidu da se posebne mogu izvesti u 13 poteza, zaključili su da je 29 poteza dovoljno za slaganje svih Rubikovih kocki.
Ali, ovaj ishod nije bio dovoljan za ostvarenje rekorda, budući da je prošle godine Silviju Radu iz Tehnološkog instituta u Lundu (Švedska) dokazao da je za to dovoljno 27 koraka. Bilo je jasno da moraju da odstrane još tri suvišna.
Postupak kojim su se do tada služili pokazao je da se sve kombinacije, osim 80 miliona grupa, postignu s 26 ili manje poteza. Proveravajući ovu prilično malu grupu, utvrdili su konačno da se, zapravo, svaka može dostići s najviše 26 poteza. Svoje rezultate predstavili su krajem jula na međunarodnom savetovanju u Voterluu (Kanada).
Novi cilj sada je da se zbir potrebnih poteza smanji na 25, a za to je neophodno imati na raspolaganju skladište od 20 terabajta. Ričard Korf sa Kalifornijskog univerziteta u Los Anđelesu, međutim, 1997. oglasio je – na osnovu vlastitog programa proračunavanja – da je najpodesnije broj koraka svesti na 18, ali ne na više od 20.
[objavljeno: ]
