Apakah ada maxima lokal dalam jumlah gerakan yang diperlukan untuk menyelesaikan Rubik's Cube?

Peter Shor dibesarkan titik yang menarik dalam kaitannya dengan upaya untuk menjawab sebelumnya pertanyaan pada kompleksitas memecahkan Rubiks cube. Saya telah memposting upaya yang agak naif untuk menunjukkan bahwa itu harus dimuat dalam NP. Seperti yang ditunjukkan Peter, pendekatan saya gagal dalam beberapa kasus. Salah satu kasus potensial dari instance semacam itu adalah di mana terdapat maksimal lokal dalam panjang lintasan. Maksud saya, mungkin diperlukan langkah S A untuk menyelesaikan kubus dari konfigurasi A , dan baik langkah S A atau S A - 1 untuk memecahkan kubus dari posisi apa pun yang dapat dicapai dalam satu gerakan dari$n \times n \times n$$S_A$$A$$S_A$$S_A - 1$ . Sekarang, ini tidak selalu menjadi masalah jika S A adalah jumlah maksimum gerakan yang diperlukan untuk menyelesaikan kubus secara umum (Nomor Tuhanuntuk kubus itu), tetapi jelas merupakan masalah jika S A benar-benar kurang dari Angka Tuhan untuk kubus itu . Jadi pertanyaan saya adalah apakah maksima lokal seperti itu ada? Bahkan jawaban untuk 3 × 3 × 3 kubus akan menarik bagi saya.$A$$S_A$$S_A$$3 \times 3 \times 3$

Menanyakan kepada Tomas Rokicki pertanyaan ini segera menghasilkan jawaban yang benar ("ya, maxima lokal ada"):

Jika suatu posisi menunjukkan total simetri, itu adalah suatu keharusan maksimum lokal (semua kecuali awal). Sedikit pemikiran harus menjelaskan mengapa hal ini terjadi dalam QTM [metrik seperempat putaran]. Untuk HTM [setengah-putar metrik], ini sedikit lebih halus tetapi tidak terlalu buruk.

...

Posisi seperti itu adalah pons asinorum, yaitu jarak 12 di QTM dan jarak 6 di HTM (U2D2F2B2L2R2).

Saya tidak melihat mengapa ini terjadi pada metrik setengah-putar; tetapi untuk metrik quarter-turn jelas. Dalam posisi dengan simetri total, semua posisi tetangga harus pada panjang jalur yang sama (karena semua gerakan setara dengan simetri). Jadi posisi dengan total simetri harus maksimum lokal atau minimum lokal ketat. Tapi minimum lokal yang ketat tidak ada ... harus ada beberapa langkah yang mengurangi jarak ke kondisi terpecahkan, hanya dengan definisi jarak. Argumen simetri diterjemahkan menjadi kubus, seperti halnya posisi contoh yang disediakan.$n \times n \times n$

Berikut argumen yang sangat heuristik yang menunjukkan di mana maksima lokal dapat ditemukan. Biarkan menjadi jumlah posisi yang membutuhkan d bergerak untuk menyelesaikannya. Setiap gerakan dari posisi seperti itu membutuhkan kubus untuk jarak d - 1 , d , atau d + 1 ; jadi ada total N d - 1 + N d + N d + 1 posisi yang dapat diakses. Ada M bergerak dari setiap posisi, mengarah ke posisi M baru; posisi pada jarak $N_d$$d$$d-1$$d$$d+1$$N_{d-1} + N_d + N_{d+1}$$M$$M$$d$adalah maksimum lokal ketika tidak ada posisi ini pada jarak d + 1 . Jika kita mengambil posisi ini untuk ditarik secara acak secara acak dari posisi yang dapat diakses (yang, tentu saja, tidak; ini adalah bagian heuristik), kita memiliki:$M$$d+1$

Jumlah maksimum lokal yang diharapkan pada jarak adalah N d X d .$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.