Pengindeksan ke dalam basis data pola - solusi Cube Optimal Rubik milik Korf

Sebagai proyek yang menyenangkan, saya telah mengerjakan implementasi C # dari Richard Korf - Menemukan Solusi Optimal untuk Rubik's Cube Menggunakan Database Pola.

https://www.cs.princeton.edu/courses/archive/fall06/cos402/papers/korfrubik.pdf

Saya benar-benar membuatnya bekerja, saya hanya mencoba untuk meningkatkan solusi saya.

Satu hal yang Korf bahas dalam makalahnya adalah bagaimana ia menyimpan dan mengindeks ke dalam basis data pola. Idealnya, saya pikir kami ingin menggunakan contoh kubus rubik untuk menghasilkan indeks ke dalam array.

Pertanyaan saya adalah tentang cara terbaik untuk menghasilkan indeks ini.

Solusi saya adalah menghasilkan hash sempurna minimal. Ini melibatkan menjaga SEMUA kubus dalam memori sampai saya telah menemukan seluruh basis data pola kemudian menghasilkan hash sempurna minimal berdasarkan itu. MPH membutuhkan beberapa jam untuk berjalan tergantung pada ukuran basis data pola, tetapi saya hanya perlu melakukannya sekali sejak saya menyimpannya ke disk. Pada akhirnya, saya bisa membuang kubus itu sendiri hanya menyimpan MPH. Dengan cara itu saya bisa mengambil kubus rubik acak, menerapkan pola, lalu mencari indeks array di MPH untuk mendapatkan panjang solusi yang diperkirakan.

Saya percaya Korf dan Shultz menjelaskan cara yang lebih baik untuk menentukan indeks kubus di makalah mereka 2005 yang disebut "Pencarian Skala Besar Pertama Skala"

https://www.aaai.org/Papers/AAAI/2005/AAAI05-219.pdf

Makalah ini menjelaskan suatu algoritma untuk menghasilkan indeks berdasarkan dari urutan leksikografis permutasi. Pada dasarnya Anda dapat mengambil permutasi {1, 2, 3} dan mencari bahwa itu adalah yang terkecil dengan indeks 0. {1, 3, 2} berikutnya dengan indeks 1 dan seterusnya.

Saya merasa saya harus bisa menerapkan algoritma ini ke kubus rubik untuk mendapatkan indeksnya dalam basis data pola, tapi saya mengalami kesulitan mencari tahu bagaimana itu akan bekerja dalam prakteknya.

Database sudut hanya pola misalnya berisi semua kubus rubik yang memiliki stiker tepi mereka dilepas. Tepatnya ada 88.179.840 kubus di set ini. Setiap sudut kubus pada kubus rubiks dapat berada di salah satu dari 24 negara yang berbeda. Keadaan sudut kubus ke-8 dapat dihitung berdasarkan 7 lainnya sehingga kubus di sudut-sudut hanya basis data pola masing-masing memiliki 7 nilai antara 0 dan 23

mis. {0, 3, 6, 9, 12, 15, 18, 21} mendefinisikan kubus "yang diselesaikan" dengan semua stiker tepi dilepas.

jika saya memutar permukaan depan 90 derajat permutasi mungkin: {0, 3, 11, 23, 12, 15, 8, 20}

Apakah ada cara untuk mendapatkan indeks dari permutasi semacam ini?

$(p_i,o_i)$$(p_0,\ldots,p_7)$$(0,\ldots,7)$$o_i \in \{0,1,2\}$$o_7$$o_0,\ldots,o_6$$8! \cdot 3^7 = 88179840$$\{0,\ldots,23\}$$(p_i,o_i)$$(p_0,\ldots,p_7)$$o_0,\ldots,o_6$$3^7p + o$$8!o + p$