Czy istnieją lokalne maksima w liczbie ruchów wymaganych do rozwiązania Kostki Rubika?

Peter Shor poruszył interesujący punkt w związku z próbą odpowiedzi na wcześniejsze pytanie dotyczące złożoności rozwiązania kostki Rubika $n \times n \times n$ . Podjąłem dość naiwną próbę wykazania, że musi być zawarta w NP. Jak zauważył Peter, moje podejście w niektórych przypadkach zawodzi. Jednym z potencjalnych przypadków takiego wystąpienia jest sytuacja, w której istnieją lokalne maksima długości ścieżki. Przez to znaczy, że może upłynąć $S_A$ przenosi się do rozwiązania sześcian z konfiguracji $A$ oraz albo $S_A$ lub $S_A - 1$ porusza się rozwiązać kostkę z dowolnym położeniu, które może być osiągnięte w jednym ruchu z $A$ . To niekoniecznie taki problem, jeśli $S_A$ jest maksymalną liczbą ruchów potrzebną do rozwiązania sześcianu w ogóle (liczbaBogadla tej kostki), ale jest zdecydowanie problemem, jeśli $S_A$ jest ściśle mniejsza niż Liczba Boga dla tej kostki . Więc moje pytanie brzmi, czy takie lokalne maksima istnieją? Nawet odpowiedź nakostkę $3 \times 3 \times 3$ byłaby dla mnie interesująca.

co.combinatorics puzzles

— Joe Fitzsimons
źródło

Chociaż nie mam takiego przykładu, byłbym zaskoczony, gdyby tak nie było, ponieważ wydaje się to sugerować, że możemy obliczyć liczbę Boga, po prostu znajdując jedną konfigurację, która jest lokalnym maksimum (choć nie jest to rygorystyczny argument).

— Tsuyoshi Ito

@Tsuyoshi Ah, ale może nie było wiadomo, czy były lokalne maksima, aż do obliczenia liczby Boga! Ale zgadzam się z tym, że spodziewam się, że te lokalne maksima istnieją. Po prostu nie wiem na pewno i chciałbym się dowiedzieć.

— Joe Fitzsimons,

@Joe: Tak, dokładnie to nie jest rygorystyczne w moim sporze. Byłbym bardziej rygorystycznie zaskoczony :) jeśli można udowodnić, że nie ma lokalnych maksimów bez przeprowadzenia wyczerpującego wyszukiwania.

— Tsuyoshi Ito,

@Tsuyoshi Wygląda na to, że lokalne maksima nie mogą wystąpić na bardzo krótkich odcinkach ścieżki i wydają się istnieć tylko w pobliżu liczby Boga, dlatego uważam, że nie jest tak jednoznaczne, że one istnieją.

— Joe Fitzsimons,

Wiem, że wykresy Cayleya dla dowolnych grup mogą mieć lokalne maksima. Zapominam, gdzie widziałem ten wynik, ale jestem pewien, że gdzieś go widziałem. Więc jeśli grupa kostek Rubika nie jest w jakiś sposób wyjątkowa, można się spodziewać, że ma także lokalne maksima.

— Peter Shor,

Odpowiedzi:

Pytanie Tomasa Rokickiego natychmiast dało prawidłową odpowiedź („tak, istnieją lokalne maksima”):

Jeśli pozycja wykazuje całkowitą symetrię, konieczne jest lokalne maksimum (wszystko oprócz początku). Mała refleksja powinna wyjaśnić, dlaczego tak jest w przypadku QTM [metr obrotu]. W przypadku HTM [metryka pół obrotu] jest to nieco bardziej subtelne, ale nie jest takie złe.

...

Taką pozycją jest pons asinorum, czyli odległość 12 w QTM i odległość 6 w HTM (U2D2F2B2L2R2).

Nie rozumiem, dlaczego tak jest w przypadku metryki półobrotu; ale dla metryki ćwierć obrotu jest to jasne. W pozycji o całkowitej symetrii wszystkie sąsiednie pozycje muszą mieć tę samą długość ścieżki (ponieważ wszystkie ruchy są równoważne symetrii). Zatem pozycja o całkowitej symetrii musi być albo lokalnym maksimum, albo ścisłym lokalnym minimum. Ale ścisłe lokalne minima nie mogą istnieć ... musi być jakiś ruch, który zmniejsza odległość do stanu rozwiązanego, przez samą definicję odległości. Argument symetrii przekłada się na kostkę , podobnie jak podana przykładowa pozycja. $n \times n \times n$

— mjqxxxx
źródło

Cóż za prosty argument, to jest genialne!

— Hsien-Chih Chang 張顯之

Doskonale, to bardzo miły argument!

— Joe Fitzsimons,

Oto niezwykle heurystyczny argument, który sugeruje, gdzie można znaleźć lokalne maksima. Niech będzie liczbą pozycji, które wymagają dokładnie ruchów do rozwiązania. Każdy ruch z takiej pozycji zabiera kostkę na odległość , lub ; tak więc w sumie pozycji, które są dostępne. Z każdej pozycji występuje ruchów, co prowadzi do nowych pozycji; pozycja w odległości $N_d$ $d$ $d-1$ $d$ $d+1$ $N_{d-1} + N_d + N_{d+1}$ $M$ $M$ $d$ jest lokalnym maksimum, gdy żadna z tych pozycji znajduje się w odległości . Jeśli weźmiemy te pozycje, aby losować je jednolicie losowo z dostępnych pozycji (które oczywiście nie są; jest to część heurystyczna), otrzymamy: $M$ $d+1$

\begin{array}{rcl} X_{d} & = & P [a given position at d is a local max] \\ = & {(\frac{N_{d - 1} + N_{d}}{N_{d - 1} + N_{d} + N_{d + 1}})}^{M} \\ = & {(1 + \frac{N_{d + 1}}{N_{d - 1} + N_{d}})}^{- M} . \end{array}

$\begin{eqnarray} X_d &=& P\left[\text{ a given position at }d\text{ is a local max }\right] \\ &=& \left(\frac{N_{d-1} + N_d}{N_{d-1} + N_d + N_{d+1}}\right)^M \\ &=& \left(1 + \frac{N_{d+1}}{N_{d-1} + N_d}\right)^{-M}. \end{eqnarray}$

$d$ $N_d X_d$

$3 \times 3 \times 3$ $M=18$ $N_d$ $N_{16} X_{16} = 0.2$ $N_{17} X_{17} = 9 \times 10^9$ $N_{18} X_{18} = 1.5 \times 10^{19}$ $d \le 16$ . At $d=17$ , the total number of positions is estimated to be $12 \times 10^{18}$ , so one might expect to test a billion positions before finding a local maximum. Finally, at $d=18$ , one expects a local maximum in every twenty positions.

— mjqxxxx
źródło

Thanks. It is however not clear to me that

N_{d - 1} + N_{d} + N_{d + 1}

$N_{d-1}+N_{d}+N_{d+1}$ is the correct number of states accessible from the

N_{d}

$N_d$ states of distance

d

$d$ . If for example there are local maxima of distance

d - 1

$d-1$ this would seem not to hold. It also seems to break for any state of distance

d

$d$ for which all neighbouring states have distance

d - 1

$d-1$ or

d + 1

$d+1$ , since this state cannot be reached in 1 move from any of the states of distance

d

$d$ . I have no idea how common or rare these situations will be.

— Joe Fitzsimons