Rubikovu kocku je možné vyriešiť na 25 ťahov, dôkaz uskutočnený na Q6600 s 8 GB

DSL.sk, 27.3.2008

Tomas Rokicki, vyštudovaný matematik zo Stanfordu, informoval o uskutočnení dôkazu, že ľubovoľnú permutáciu Rubikovej kocky je možné vyriešiť na maximálne 25 ťahov.

Doteraz bolo dokázané, že je to možné na maximálne 26 ťahov. Dôkaz uskutočnil minulý rok tím z Northeasternskej univerzity v Bostone pomocou počítačového dôkazu a grantu vo výške 200 000 dolárov na nákup rýchlej diskovej kapacity 20 TB a pamäťovej kapacity.

Rokicki podľa zverejnených informácií vypracoval lepší matematický model a dôkaz sa mu podarilo uskutočniť na hardvéri výrazne nižšej konfigurácie.

Použitým bol procesor Q6600 taktovaný na 1.6 GHz s 8 GB pamäte. Výpočet bol rozdelený do viacerých fáz, celkovú dĺžku výpočtu odhadol Rokicki na 1 500 hodín, teda niečo viac ako dva mesiace.

Podobne ako pri minuločnom dôkaze išlo o konštruktívny dôkaz, keď program hľadal riešenia pre celé triedy stavov zahŕňajúce približne 20 miliárd jednotlivých stavov.

Celkový počet rozličných jednotlivých permutácií Rubikovej kocky je približne 4.3 x 10 ^ 19, o niektorých stavoch je dokázané, že ich nie je možné vyriešiť na menej ako 20 ťahov. Podľa zatiaľ nedokázanej hypotézy je každú permutáciu možné vyriešiť práve na maximálne 20 ťahov.

Rokicki publikoval použitý dôkaz a správu tu. Aktuálne podľa informácií vo svojej správe pracuje na dôkaze, že Rubikovu kocku je možné vyriešiť vždy na maximálne 24 ťahov.


Najnovšie články:



Diskusia:

no teda Od reg.: Klix. | Pridané: 27.3.2008 12:15 On mi asi ukradol pocitac. :-) Odpovedať Známka: -5.0 Hodnotiť:

200kUSD Od reg.: Propediotika | Pridané: 27.3.2008 12:16 Takze tych 200 000 USD bolo zbytocne vyhodenych, kedze sa to da vypocitat aj na "obycajnom" pc. Odpovedať Známka: -0.8 Hodnotiť:

Re: 200kUSD Od: inspe | Pridané: 28.3.2008 9:16 to mas pravdu ale niekto musel dat tomu pc rozum a to nieco stoji Odpovedať Hodnotiť:

Re: 200kUSD Od: pipi | Pridané: 28.3.2008 13:06 tak ked na taku picovinu dostal 200k tak to rovno mohli splachnut do zachoda alebo dat bedomovcom Odpovedať Známka: 1.4 Hodnotiť:

Re: 200kUSD Od: Dinko | Pridané: 6.4.2008 10:38 Plne s tebou suhlasim. Odpovedať Hodnotiť:

maximálne alebo minimálne Od reg.: 3hlav | Pridané: 27.3.2008 12:16 asi by bolo lepšie použiť slovo minimálne, kedže maximálne sa pravdepodobne dá vyriešiť až nekonečným počtom ťahov (napr. v mojom prípade:)) Odpovedať Známka: 7.1 Hodnotiť:

Re: maximálne alebo minimálne Od reg.: K-NinetyNine | Pridané: 28.3.2008 20:41 pouzitie slova minimalne je v tomto pripade nespravne... lebo su stavy, ktore sa daju vyriesit aj na jeden tah a to je uz menej ako 25, cize 25 nie je minimalny pocet tahov... spravne by malo byt povedane nieco ako "kazda permutacia rubikovej kocky sa da najefektivnejsie vyriesit maximalne na 25 tahov" ale to dlhe a tazko pochopitelne... Odpovedať Známka: 10.0 Hodnotiť:

tak to uz ano Od: fotograf | Pridané: 27.3.2008 12:36 tomu sa hovori efektivne vyuzitie grantu... :-)) Odpovedať Známka: 5.3 Hodnotiť:

Toto mi pripomina iny pripad tykajuci sa sachu Od reg.: Edison | Pridané: 27.3.2008 14:01 mozno aj 20 rokov dozadu, ked sa jeden manik vytasil s urcitou situaciou, o ktorej dokazal, ze jedna strana ma vitaznu strategiu - moze dat druhej mat, ale nie na menej ako nejakych 80 tahov, pricom sa nevyhodi ziadna figura. V sachu plati pravdilo, ze ked sa 50 tahov nevyhodi ziadna figura, je remiza. Vychadzalo sa z predpokladu, ze situacie, ako popisana vyssie, neexistuju. Po zverejneni tohto dokazu sachova federacia velmi neochotne pravidla zmenila, ale aj to len takym sposobom, ze udelila vynimku na tuto jedinu situaciu. Odpovedať Známka: 5.6 Hodnotiť:

Re: Toto mi pripomina iny pripad tykajuci sa sachu Od: w1250 | Pridané: 27.3.2008 21:43 Presnejšie povedané, ak v priebehu 50 ťahov nie je vyhodená žiadna figúra a neurobí sa žiaden ťah pešiakom. Kedysi na nejaké pozície platilo pravidlo "100 ťahov", ale bolo zrušené. Odpovedať Hodnotiť:

Presne. Od reg.: DSL = LSD | Pridané: 27.3.2008 14:09 Maximum uvadza najviac tahov a nie najmenej. Nechapem ako si nieco take moze autor tohto clanku takto pomylit. Skor by ma zaujimalo, ci pri tych 1500 hodinach padol system intelu. Ked uz niekto nieco take robi mal by sa vyjadrit k tomu s cim to robi nie len CPU a RAM ale hlavne MB. Totizto myslim si, ze s AMD Phenom by to robil roky ak by sa to na tych suntoch vobec dalo. Ja rad steklim. ROFL! Odpovedať Známka: -6.4 Hodnotiť:

Re: Presne. Od: Thomas5 | Pridané: 27.3.2008 14:38 Je to pisane uplne korektne, evidentne nemas ziadne technicke vzdelanie a nikdy si necital ziadny matematicko-dokazny text... Odpovedať Známka: 6.0 Hodnotiť:

Re: Presne. Od: 34224 | Pridané: 27.3.2008 16:20 cumel sa strka do ust nie do riti Odpovedať Známka: 1.1 Hodnotiť:

Re: Presne. Od reg.: K-NinetyNine | Pridané: 28.3.2008 20:43 vid moj comment vyssie Odpovedať Hodnotiť:

takt? Od reg.: OmeGa | Pridané: 27.3.2008 14:30 "Použitým bol procesor Q6600 taktovaný na 1.6 GHz s 8 GB pamäte" nebol nahodou taktovany na 3.6 Ghz? respektive 400 MHz FSB = 1600 MHz efektivne... maximalne je spravne slovo, kedze hladal najefektivnejsie tahy, nie tahy nas, smrtelnikov. kedze niektore stavy sa daju vyriesit aj jedinym tahom, dvomi, tromi.. najzlozitejsi stav ktory nasiel ale zabral 25 tahov, takze maximalne na 25 tahov je mozne (efektivne) zlozit kocku. to je vsetko. Odpovedať Známka: 10.0 Hodnotiť:

Re: takt? Od: Anin | Pridané: 27.3.2008 14:52 A koľkože to tomu programu s tým procesorom trvalo??? Buď bol tak nešikovný program, alebo aj takáto "zložitá" úloha(teda blbosť pre ľudstvo)má náročné riešenie pre dnešné pomalinké procesory. Neviem ako by si podelil úlohu viacjadierkový procesor, to by musel byť fakt namakaný programátor a byť 0.1 v matematike a logike. Takže ak takéto bludy riešime mesiace, čo potom zložité a dôležité výskumné úlohy, napr. pre zdravie ľudí? Potom aj 131072 jadierok v procesore bude málo... Odpovedať Známka: -6.9 Hodnotiť:

Re: takt? Od: sineDD | Pridané: 27.3.2008 14:54 jadierka su akurat tak v tekviciach :D Odpovedať Známka: 7.5 Hodnotiť:

uiybiuybi Od: jdfebva | Pridané: 27.3.2008 15:41 kjhfd aj v jeho hlave? iubvreoeri Odpovedať Známka: -5.0 Hodnotiť:

Re: takt? Od: 34224 | Pridané: 27.3.2008 16:23 ty si dalsi koho svrbi anal Odpovedať Známka: 3.3 Hodnotiť:

Re: takt? Od reg.: OmeGa | Pridané: 27.3.2008 16:57 neviem ci sprosteho/tu hras, alebo si, ale v clanku je napisane, ze to trvalo cca 1500 hodin. napisat program, kde bude kazde jadro riesit jednu moznost podla mna nieje problem, kedze tych moznosti (ako poskladat kocku) asi hooodne vela (niekde to bolo spominane). pritom to musi zopakovat 20 miliard krat (to uz napisane je). tak si vyrataj. 20 mld x pocet moznosti ako zlozit kocku, a dojdes k cislu, ktore ti hovori, ze to tak dlho moze naozaj trvat. Odpovedať Hodnotiť:

Re: takt? Od: ground | Pridané: 27.3.2008 23:18 riešenie 4.3 x 10 ^ 19 permutácií nie je pre teba zložitá úloha? a inak jedna teta čo vymyslela v súšasnosti najpoužívanejší algorytmus na poskladanie rubikovej kocky teraz robí kódovacie algorytmy za ťažké prachy, takže na niečo to bude dobré. nemusí ísť len o skladanie nejakej kocky. Odpovedať Hodnotiť:

Re: takt? Od: Anin | Pridané: 28.3.2008 9:16 No hej, dôležitosť asi ako prvočísla. Tiež neviem načo to ktosi vymyslel... Keby radšej "raka" a iné pliagy skúmali... Odpovedať Známka: -7.5 Hodnotiť:

Re: takt? Od reg.: OmeGa | Pridané: 28.3.2008 13:16 uz vidim ze blbeho len nehras. kedze netusis ake su prvocisla dolezite (si predstav, ze aj 0 je dolezita). v podstate je dolezite vsetko okrem tvojich nazorov. Odpovedať Hodnotiť:

Re: takt? Od: Anin | Pridané: 28.3.2008 16:03 Hmmm... Napíš mi jeden úžitok v praxi z prvočísiel... Odpovedať Známka: -10.0 Hodnotiť:

Re: takt? Od: Bottle of Rum | Pridané: 28.3.2008 18:01 na prvocislach je zalozene asymetricke sifrovanie takze by si sa nemohol bezpecne prihlasit do svojich "uzitocnych" mailov Odpovedať Známka: 10.0 Hodnotiť:

Re: takt? Od: Anin | Pridané: 31.3.2008 7:44 Ďakujem. Odpovedať Hodnotiť:

hmhmh Od reg.: lolol | Pridané: 27.3.2008 14:39 a k comu to bolo ako dobre?? Odpovedať Známka: -3.3 Hodnotiť:

Re: hmhmh Od: sineDD | Pridané: 27.3.2008 14:47 aby si sa mal na co opytat Odpovedať Hodnotiť:

Re: hmhmh Od reg.: Drako | Pridané: 27.3.2008 14:54 A aby na DSL.sk pribudol dalsi clanok :D Odpovedať Známka: 5.7 Hodnotiť:

Re: hmhmh Od reg.: oppec | Pridané: 27.3.2008 16:40 spravne poznamenanie nema to ziadny vyznam, zistenie ze rubikova kocka sa da vyriesit zo vsetkych permutacii na 25 tahov... dolezite je ju vyriesit! a ne sa pozret na tu kocku a povedat: "ide to na 25 tahov" zachvilu volakto tresne ze rubikovu hyperkocku je mozne vyriesit 200 tahmi a naco nam to bude ked si ju nevieme ani predstavit? Odpovedať Známka: -10.0 Hodnotiť:

Re: hmhmh Od reg.: shadowboy | Pridané: 27.3.2008 18:28 no to mas pravdu, hyperkocka je dobra pakarna, len chcem vidiet toho, kto navrhne a vyrobi rubikovu hyperkocku, alebo este lepsie hypergulu... ;) Odpovedať Hodnotiť:

Re: hmhmh Od reg.: Lubo Hrobar | Pridané: 27.3.2008 22:02 hlavne teda toho kto ju vyrobi v troch dimenziach... Odpovedať Hodnotiť:

myslim Od: max - min? | Pridané: 27.3.2008 14:54 myslim ze slovko maximalne je tam rusive pretoze ked by to mal riesit na maximalny pocot tahov je nekonecno... minimalne sa hodi uz asi viac. ale myslim ze najviac sa hodi najviac efektivne.. Odpovedať Hodnotiť:

Re: myslim Od: Nemko | Pridané: 27.3.2008 17:24 ale oni pisu, ze kazda premutacia sa DA vyriesit na tych 25 tahov a nie, ze lubovolny clovek kazdu permutaciu vyriesi na maximalne 25 tahov... zober si priklad: da sa to spravit maximalne za den... nie je napisane, ze sa to spravi za den, ale je to mozne spravit do 24-hodinoveho casoveho limitu... Odpovedať Hodnotiť:

hurá....... Od: fú.. | Pridané: 27.3.2008 16:23 na čo sú ľudia schopní vyhadzovať peniaze...??!bože! Odpovedať Známka: -10.0 Hodnotiť:

IBM? GPU? Od: dej to sem nebo se objesim | Pridané: 27.3.2008 16:30 By ma zaujimalo ako by si napriklad s touto uloho IBM Cell alebo nejake GPU, urcite by to bolo zaujimave porovnanie. Odpovedať Hodnotiť:

Re: IBM? GPU? Od: claudius | Pridané: 27.3.2008 19:06 pomocou ps3 (rozumej viac pospajanych) a na nom (legalne) nainstalovanom linuxe spravili (velmi lacny) superpocitac, ktory sa dokonca zaradil do rebrickov Odpovedať Hodnotiť:

Re: IBM? GPU? Od: dej to sem nebo se objesim | Pridané: 27.3.2008 21:19 jj to viem, no tak hlavne ma zaujima celkova situacia ohladom CELL-u. By som rad vedel o kolko je vykonnejsi ako 4jadra intelu, viem ze u konzoli sa dba hlavne na optimalizaciu ale neco neoptimalizovaneho ako by to zvladalo... Odpovedať Hodnotiť:

..... Od reg.: girus | Pridané: 27.3.2008 16:35 tak to berte ako maximalne minimum poctu tahov. take tazke pochopit ze musim urobit MAXIMALNE 25 (24,26) tahov aby kocka bola poskladana z akejkolvek rozhadzanej poziciee...??? Odpovedať Hodnotiť:

mate tam chybu Od: madrac | Pridané: 27.3.2008 16:58 Podobne ako pri minuločnom dôkaze to ma byt asi minuloROcnom opravit! Odpovedať Hodnotiť:

brigádnik Od: PeHaha | Pridané: 27.3.2008 22:21 ako vidíš, vôbec mi to nevadí! Odpovedať Hodnotiť:

ako tak myslim xD Od: ku8ik | Pridané: 27.3.2008 18:45 mam pocit, ze ked si predstavim tie peniaze co sa na to minu je mi az luto ze nie su pouzite na nejake zmysluplnejsie veci, kedze na kolko krat najmenej sa da poskladat rubikova kocka s principu je to malo vyuzitelna informacia, vlastne statistika a statistika je najvacsie klamstvo.. Odpovedať Hodnotiť:

Re: ako tak myslim xD Od: chrt2 | Pridané: 27.3.2008 19:27 nemyslim si ze su to vyhodene meniaze bola to sutaz a ten kto vyhral ( skola ) dostala dotaciu. je to pomerne efektivny sposob ako dat vybavenie skole ktora ho efektivne vyuzije na vychovavanie novych odbornikov. Alebo si myslis ze to vybavenie pouziju iba raz a bude zapadat prachom? Ked si myslis ze davat peniaze do skol je plytvanie tak neviem kam by si ich chcel pchat. Okrem toho urcite neslo o nejaku charitu ale o reklamu ci uz politicku alebo komercnu a toto je jeden z tych uzitocnejsich sposobov. Odpovedať Hodnotiť:

Re: ako tak myslim xD Od: ku8ik | Pridané: 27.3.2008 20:48 tym padom, ak to ti studenti neprepiju tak je to fajn :D Odpovedať Hodnotiť:

Řešení Od: Accuphose | Pridané: 27.3.2008 19:18 Spíš by mě zajímalo, jak to vůbec složit, jako kluk jsem byl rád, když jsem dal dohromady 7 políček na jedný straně :-( Má někdo link na návod? Odpovedať Hodnotiť:

Re: Řešení Od reg.: Ethan | Pridané: 27.3.2008 20:03 na youtube ako instruktazne video roka to bolo, tak skus tam hladat Odpovedať Hodnotiť:

Re: Řešení Od: Svaty Dindi | Pridané: 29.3.2008 17:18 http://www.gk2-po.sk/heureka/ucastnici/zizalky/ rubikovakocka/ako_poskladat_rubikovu_kocku.htm (musis ten link dat do jedneho riadku) Podla tohto navodu som ju poskladal prvy krat v zivote. Konecne. Odpovedať Hodnotiť:

Re: Řešení Od reg.: Kominár | Pridané: 30.3.2008 17:09 Teraz si ľahni do postielky a prídem ťa prikryť a zhasnem ti svetlo. Odpovedať Známka: 5.0 Hodnotiť:

Re: Řešení Od: 3xo | Pridané: 31.3.2008 9:59 kapitalny trapas zabavne ako sa na internete este stale najdu ludia ktori si myslia ze maju zmysel pre humor a zakopavaju sa hlbsie a hlbsie na rozlicnych forach Odpovedať Hodnotiť:

....? Od: Dinko | Pridané: 6.4.2008 10:48 Ako mohol niekto dostat grant na takyto nezmysel? Ja chapem, ze kazdeho bavi nieco ine, a ze niektorych ludi bavi zaoberat sa aj takouto volovinou. Mozno to ma vacsi zmysel ako vysedavanie v krcme pri pive (aj ked nie som si isty). Ale 200k dolarov????? To sa tie peniaze fakt nedaju pouzit nejak zmysluplnejsie? A aj ten genialny matematik mohol svoju energiu a potencial vynalozit na nieco zmysluplnejsie :P. Nechapem... Odpovedať Hodnotiť:

ako ju zlozim? Od: pijavicka | Pridané: 30.10.2008 14:58 dajte tip ako ju zlozit. Dakujem Odpovedať Hodnotiť:

Pridať komentár