Pojawia sie nowa konkurencja - ukladanie kostki Rubika przez roboty,
na czas.
No - bardziej specjalizowane urzadzenia niz roboty

http://www.gizmag.com/jay-flatland-paul-rose-rubiks-
cube-robot/41523/

https://www.youtube.com/watch?v=bEiQwmEe45s
https://www.youtube.com/watch?v=laPVTrzGDpA
https://youtu.be/gVF_XUccMuo?t=38

Czas juz zszedl ponizej 1 sekundy, robi wrazenie.
W tym czasie robot wykonuje ok 20 ruchow.

No i pojawiaja sie dwa polskie nazwiska - Kociemba i Rokicki - autorzy
szybkiego algorytmu.

J.

do góry

to niepojęte, że dla niektórych super skomplikowane problemy są wręcz
banalne do rozwiązania... nie rozumiem tego co napisałeś, robot wykonuje
20 obrotów na sekundę i układa kostkę w poniżej sekundy?

do góry

Użytkownik "platformowe głupki" napisał w wiadomości grup
dyskusyjnych:n9kti6$ln0$...@n...news.atman.pl...
>to niepojęte, że dla niektórych super skomplikowane problemy są wręcz
>banalne do rozwiązania... nie rozumiem tego co napisałeś, robot
>wykonuje 20 obrotów na sekundę i układa kostkę w poniżej sekundy?

Robot uklada kostke w ok 20 ruchow - taka liczba jest teoretycznie
wystarczajaca do ulozenia, i jak widac praktycznie tez.
Uklada ja w sekunde, z czego wniosek, ze wykonuje ok 20
(cwierc)obrotow na sekunde :-)

Byc moze czasami wykonuje dwa ruchy naraz.

J.

do góry

niepojęte, dowolnie poskręcaną kostkę można ułożyć w 20(40) ruchów?
niepojęte...

do góry

Użytkownik "platformowe głupki" napisał w wiadomości grup
dyskusyjnych:n9ku3m$m9j$...@n...news.atman.pl...
>niepojęte, dowolnie poskręcaną kostkę można ułożyć w 20(40) ruchów?
>niepojęte...

To dziala tak - liczymy ilosc mozliwych ułozen/stanow kostki.
Wychodzi nam liczba dosc duza, ale przeciez skonczona, oznaczmy ja
przez S.

Teraz rozwazmy jeden ruch - cwierc obrotu jednej sciany.
Mamy 12 do wyboru - 6 scian, dwie strony.
Czyli w jednym ruchu mozemy zmienic stan na jeden z 12 innych.

W dwoch ruchach mamy juz 12*12 = 144 mozliwosc.
No - troche mniej, bo drugi ruch moze skasowac pierwszy i wrocimy do
stanu wyjsciowego.
Ale takimi drobiazgami sie na razie nie zajmujemy.

Po n ruchach mamy wiec kostke w jednym zgrubsza liczacz z 12^n stanow.

No i jesli mnie pamiec nie myli, to 12^21 > S.
Moze myli, i wykladniku jest np 23, ale tego rzedu liczba to jest.
Nawet nie 30.

Dalsze mieszanie teoretycznie nic nie daje, bo nie mozemy osiagnac
wiecej niz S stanow.

Czy nalezy wiec przyjac, ze kazda kostke da sie ulozyc w co najwyzej
21 ruchach ?
No ... na pierwsza mysl to niekoniecznie - moga byc uklady, ktore
wymagaja dluzszej sekwencji, kosztem tego, ze inne wymagaja krotszej,
czy powtarzaja sie czesto w czasie roznych sekwencji.

Na to sie bodajze pojawilo sporo publikacji matematykow, tym niemniej
nawet bez ich czytania jakis szacunek mamy - kostke powinno dac sie
ulozyc w okolo 21 czy tam z niewielkim zapasem 25 ruchow.

J.

do góry

to chyba tylko mandziejewicz rozumie...

do góry

Użytkownik "platformowe głupki" napisał
>to chyba tylko mandziejewicz rozumie...

No ba, nie ma obowiazku rozumienia, zawsze mozna worki nosic albo rowy
kopac.

J.

--
Jest 10 rodzajow ludzi - ci którzy rozumieja system binarny i ci,
ktorzy nie rozumieja.

do góry

On 12.02.2016 17:22, J.F. wrote:
> Użytkownik "platformowe głupki" napisał w wiadomości grup
> dyskusyjnych:n9ku3m$m9j$...@n...news.atman.pl...
>> niepojęte, dowolnie poskręcaną kostkę można ułożyć w 20(40) ruchów?
>> niepojęte...
>
> To dziala tak - liczymy ilosc mozliwych ułozen/stanow kostki.
> Wychodzi nam liczba dosc duza, ale przeciez skonczona, oznaczmy ja przez S.
>
> Teraz rozwazmy jeden ruch - cwierc obrotu jednej sciany.
> Mamy 12 do wyboru - 6 scian, dwie strony.
> Czyli w jednym ruchu mozemy zmienic stan na jeden z 12 innych.
>
> W dwoch ruchach mamy juz 12*12 = 144 mozliwosc.
> No - troche mniej, bo drugi ruch moze skasowac pierwszy i wrocimy do
> stanu wyjsciowego.
> Ale takimi drobiazgami sie na razie nie zajmujemy.
>
> Po n ruchach mamy wiec kostke w jednym zgrubsza liczacz z 12^n stanow.
>
> No i jesli mnie pamiec nie myli, to 12^21 > S.
> Moze myli, i wykladniku jest np 23, ale tego rzedu liczba to jest. Nawet
> nie 30.

>
> Dalsze mieszanie teoretycznie nic nie daje, bo nie mozemy osiagnac
> wiecej niz S stanow.
>
> Czy nalezy wiec przyjac, ze kazda kostke da sie ulozyc w co najwyzej 21
> ruchach ?
> No ... na pierwsza mysl to niekoniecznie - moga byc uklady, ktore
> wymagaja dluzszej sekwencji, kosztem tego, ze inne wymagaja krotszej,
> czy powtarzaja sie czesto w czasie roznych sekwencji.
>
> Na to sie bodajze pojawilo sporo publikacji matematykow, tym niemniej
> nawet bez ich czytania jakis szacunek mamy - kostke powinno dac sie
> ulozyc w okolo 21 czy tam z niewielkim zapasem 25 ruchow.


Jak sam zauważyłeś, nie jest to żaden szacunek, bo bez trudu można
skonstruować obiekt, który ma 2 możliwe ruchu, a odległość pomiędzy
punktami jest znacznie większa niż log2(ilość_stanów).

Algebraiczne podejśćie dawało znacznie szerszy zakres. 19-30 czy coś
takiego.
Ostateczny wynik zrobiono w połowe btruteforcem na serwrach googla;-)

How We Did It

How did we solve all 43,252,003,274,489,856,000 positions of the Cube?
We partitioned the positions into 2,217,093,120 sets of 19,508,428,800
positions each.
We reduced the count of sets we needed to solve to 55,882,296 using
symmetry and set covering.
We did not find optimal solutions to each position, but instead only
solutions of length 20 or less.
We wrote a program that solved a single set in about 20 seconds.
We used about 35 CPU years to find solutions to all of the positions in
each of the 55,882,296 sets

http://www.cube20.org/

pzdr
bartekltg

do góry

Użytkownik "bartekltg" napisał w wiadomości grup
dyskusyjnych:n9l2d2$g5c$...@n...news.atman.pl...
On 12.02.2016 17:22, J.F. wrote:
>> Czy nalezy wiec przyjac, ze kazda kostke da sie ulozyc w co
>> najwyzej 21
>> ruchach ?
>> No ... na pierwsza mysl to niekoniecznie - moga byc uklady, ktore
>> wymagaja dluzszej sekwencji, kosztem tego, ze inne wymagaja
>> krotszej,
>> czy powtarzaja sie czesto w czasie roznych sekwencji.

>Jak sam zauważyłeś, nie jest to żaden szacunek, bo bez trudu można
>skonstruować obiekt, który ma 2 możliwe ruchu, a odległość pomiędzy
>punktami jest znacznie większa niż log2(ilość_stanów).

Ale w kostce jest dosc dobre mieszanie, wiec szansa rosnie ...

>How We Did It
>We did not find optimal solutions to each position, but instead only
>solutions of length 20 or less.

Cos tu chyba zle napisali, albo ja nie rozumiem.

>We wrote a program that solved a single set in about 20 seconds.
>We used about 35 CPU years to find solutions to all of the positions
>in each of the 55,882,296 sets
>http://www.cube20.org/

Szacunki jak widac okazaly sie bardzo dobre :-)

A teraz ta sekunda to razem z analiza ukladu ... niezle przyspieszenie
z oryginalnych 20s bez zadnego ukladania.

J.

do góry

Użytkownik "J.F." <j...@p...onet.pl> napisał w wiadomości
news:56be1710$0$22833$65785112@news.neostrada.pl...
>
>>How We Did It
>>We did not find optimal solutions to each position, but instead only
>>solutions of length 20 or less.
>
> Cos tu chyba zle napisali, albo ja nie rozumiem.
Ja rozumiem, że nie szukali optymalnego ale jak znaleźli w mniej jak 20
ruchów to odfajkowywali dany stan jako rozwiązywalny w mniej jak 20.

>
>>We wrote a program that solved a single set in about 20 seconds.
>>We used about 35 CPU years to find solutions to all of the positions in
>>each of the 55,882,296 sets
>>http://www.cube20.org/
>
> Szacunki jak widac okazaly sie bardzo dobre :-)
>
> A teraz ta sekunda to razem z analiza ukladu ... niezle przyspieszenie z
> oryginalnych 20s bez zadnego ukladania.
>
Mnie najbardziej zastanawia jakim cudem mistrzowie układali to chyba w
kilkanaście sekund. Może to ludzie z jakimś zespołem jak ci co liczą w
pamięci liczby z wynikami z chyba dziesiątkami (jak nie setkami) cyfr
wyniku.
Umiałem kiedyś to ułożyć, ale jakby mi ktoś dał kostkę w której zrobiono np.
7 ruchów to w życiu nie byłbym w stanie wykombinować jakie to ruchy i robiąc
moją metodą z pewnością początkowo tworzyłbym stany z których do rozwiązania
dalej niż ze stanu początkowego.
P.G.

do góry