BIZIT 11 - prvi dan

Rešenje Rubikove kocke u najviše 20 poteza

rubik Već godinama zadaje glavobolje, stvara zavist i uzrokuje neprospavane noći, često nervozu i odustajanje. Na šta god ovaj opis ličio, mi pričamo o Rubikovoj kocki. E pa, zavisnici od ove zarazne igračkice, mogu da odahnu pošto je ona, (na sreću ili žalost), pomalo izgubila svoju draž. Naučnici (opet oni) su pronašli način da ovaj problem reše u svega 20 poteza.

Ipak, nije to uradila ljudska pamet, ili bar ne direktno. Zahvaljući Google-ovim superkompjuterima, tim istraživača je proverio svaku od 43.252.003.274.489.856.000 različitih pozicija (prvi ko nam napiše ovaj broj rečima, dobiće septembarski broj PC Press-a na kućnu adresu) kako bi utvrdili neophodni maksimalan broj poteza da bi se mozgalica razrešila. Utvrdili su da je 20 taj broj, ali do sada je bilo nemoguće to i izvesti. Postoji čak 300 miliona načina da se iz 20 poteza dobije rešenje.

Profesor Morley Davidson, matematičar sa Univerziteta u Ohaju, radio je zajedno sa  Google-ovim inženjerom i kolegama iz Nemačke i Kalifornije. On kaže da bi bilo nemoguće ispitati sve kombinacije pojedinačno, pa su ih umesto toga podelili 2,21 milijardi grupa, od po 20 milijardi pozicija. Kasnije su koristili principe simetrije, kako bi smanjili ovaj broj mogućih kombinacija.

U nastavku je neophodan broj poteza za rešenje Rubikove kocke, a u zavisnosti od položaja u kojem se nalazi u trenutku pre rešavanja:

0
1

1
18

2
243

3
3.240

4
43.239

5
574.908

6
7.618.438

7
100.803.036

8
1.332.343.288

9
17.596.479.795

10
232.248.063.316

11
3.063.288.809.012

12
40.374.425.656.24

13
531.653.418.284.628

14
6.989.320.578.825.358

15
91.365.146.187.124.313

16
oko 1.100.000.000.000.000.000

17
oko 12.000.000.000.000.000.000

18
oko 29.000.000.000.000.000.000

19
oko 1.500.000.000.000.000.000

20
oko 300.000.000

Da bi došao do maksimalnog neophodnog broja poteza za rešavanje problema, standardnom PC-ju potrebno je oko 35 godina, dok je Google-ov superkompjuter to uradio za nekoliko nedelja. Do čarobnih 20 se došlo zato što se ovaj broj odnosi na najefikasniji algoritam za rešavanje mozgalice, koji uvek koristi najbrži put.

Inače, od samih početaka Rubikove kocke, naučnici su pokušavali da pronađu taj skriveni broj. Trenutni (živi) šampion u rešavanju Rubikove kocke je Škot Breandan Vallance, čije je prosečno vreme rešavanja 10,74 sekunde.

Izvor: Daily Mail

Facebook komentari:
Računari i Galaksija
Tagovi: , , , , , ,