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

11

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?

Kosmosis
sumber
Anda mungkin akan menemukan ini menarik.
Tom van der Zanden
menarik! Anda mengatakan dia "sayu" sesuatu di koran. akan lebih baik untuk lebih spesifik tentang bagian yang tidak "disempurnakan". Anda juga mengatakan Anda membuatnya berfungsi. apa implementasi pengindeksan awal Anda? apakah ini proyek sekolah? sarankan Obrolan Ilmu Komputer lebih lanjut . misalnya blogging tentang hal itu atau sumber terbuka kode dapat bermanfaat bagi orang lain & mengarah ke lebih detail. juga kertas tampaknya tidak merujuk pada fungsi hashing ...
vzn
Saya menerapkan algoritma Korf: github.com/benbotto/rubiks-cube-cracker . Saya juga menemukan pengindeksan menjadi sulit, jadi saya menulis artikel tentang itu di Medium: medium.com/@benjamin.botto/…
avejidah

Jawaban:

6

(pi,oi)(p0,,p7)(0,,7)oi{0,1,2}o7o0,,o68!37=88179840{0,,23}(pi,oi)(p0,,p7)o0,,o637p+o8!o+p

Yuval Filmus
sumber
Hai Yuval, terima kasih atas komentarnya. Bagi saya, 0 hingga 23 adalah cara saya mengidentifikasi posisi / orientasi unik tempat sudut kubus berada. 8 posisi kali 3 orientasi per posisi = 24. Untungnya saya dapat dengan mudah membagi nilai ini menjadi tupel posisi / orientasi yang terpisah. Jawaban Anda membawa saya ke kode ini yang merupakan implementasi dari algoritma yang Anda uraikan. github.com/brownan/Rubiks-Cube-Solver/blob/master/cornertable.c Saya perlu melakukan sedikit pekerjaan untuk membuat ini lebih umum (sehingga saya dapat menangani pola yang berbeda dari "hanya sudut") tetapi sekarang Saya di jalur yang benar, terima kasih!
Cosmosis