On 12.02.2016 18:31, J.F. wrote:
> 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 ...

A to teraz zdefiniuj dobre mieszanie, udowdonij, zę kostka Rubika
ma tę własność i udowodnij, jak ona wływa na przedstawione
wcześniej oszacowanie.

:p

W matematyce nie ma nic na oko i zamachanie rękoma. ;>


>> 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.

Ale nie napisałes czego nie rozumiesz.
Nie znajdują optymalnego rozwiązania z danego punktu, tylko
jakiekolwiek, byleby <20. Np z konfiguracji A masz 15 ruchów do
konfiguracji B. W cache masz, że B jest 4 ruchy od rozwiązania.
No to wiesz, że istnieje trajektoria z A do rozwiązania na 19 ruchów.
To, że optymalnne rozwiązanie A zajmuje 17 ruchów nie obchodzi cie,
nie zajmujesz się więcej A.

Aż się prosi o zastosowanie jakiegoś meet i the middle.

>> 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.

Set to nie pozycja. set to 19 miliardów pozycji.

pzdr
bartekltg