Ruang keadaan yang bisa dicapai dari 8-puzzle

11

Saya baru saja mulai mempelajari Kecerdasan Buatan dan bertanya-tanya mengapa ruang keadaan yang dapat dicapai dari 8-puzzle adalah 9!/2 . Saya melihat bahwa jumlah permutasi ubin adalah 9!tetapi tidak segera jelas mengapa setengah dari keadaan yang mungkin dari teka-teki itu tidak dapat dijangkau pada keadaan tertentu. Adakah yang bisa menjelaskan?

Gambar 8-puzzle untuk referensi dengan konfigurasi acak di sebelah kiri dan status sasaran di sebelah kanan:

Contoh 8-puzzle

Cam
sumber
3
Karena grafik keadaan terdiri dari dua komponen yang terputus dengan ukuran yang sama (jumlah total inversi permutasi dari setiap state adalah modulo 2 invarian, sehingga dua state yang memiliki jumlah total inversi permutasi aneh dan bahkan tidak terhubung); Saya tidak menemukan contoh yang dijelaskan dengan baik, tetapi presentasi ini harus cukup jelas untuk membuat Anda memahaminya (kecuali kesalahan ketik "terhubung" yang harus diganti dengan "terputus")
Vor
@ Atau berubah menjadi jawaban?
Yuval Filmus

Jawaban:

12

Ini merupakan perluasan dari presentasi ini .

Karena grafik keadaan terdiri dari dua komponen yang terputus dengan ukuran yang sama. Tanpa kehilangan sifat umum kita dapat mengasumsikan bahwa negara target adalah .123...15

 1  2  3  4
 5  6  7  8
 9 10 11 12
13 14 15  *

Mengingat keadaan suatu inversi permutasi adalah genteng T i yang ditempatkan setelah T j tapi i < j ; ini terjadi ketika (a) T i adalah di baris yang sama dari T j , tapi di kanan, atau (b) T i adalah berturut-turut lebih rendah:STiTji<jTiTjTi

 .  .  .  .      .  .  .  .
 3  .  .  1      .  7  .  .
 .  .  .  .      .  5  .  .
 .  .  .  .      .  .  .  .
    (a)             (b)

Kami mendefinisikan sebagai jumlah ubin T i , i < j yang muncul setelah T j . Misalnya, di negara bagian:NjTii<jTj

 1  2  3  4
 5 10  7  8
 9  6 11 12
13 14 15  *

kami memiliki bahwa setelah ada satu ubin ( T 6 ) yang seharusnya sebelum itu, jadi N 7 = 1 ; setelah T 10 ada empat ubin ( T 7 , T 8 , T 9 , T 6 ) yang seharusnya ada sebelum itu, jadi N 10 = 4 .T7T6N7=1T10T7,T8,T9,T6N10=4

Misalkan adalah jumlah semua N i dan nomor baris dari ubin kosong T NNiT

N=i=115Ni+row(T)

Dalam contoh di atas kita memiliki: N=N7+N8+N9+N10+row(T)=1+1+1+4+4=11

N N

Sebagai contoh:

 .  .  .  .      .  .  .  .
 .  .  2  3      .  .  *  3
 4  5  *  .      4  5  2  .
 .  .  .  .      .  .  .  .

N=N+3 (2 is placed after 3,4,5)1 (empty tile is moved up)=N+2

 .  .  .  .      .  .  .  .
 .  .  *  4      .  .  3  4
 2  5  3  .      2  5  *  .
 .  .  .  .      .  .  .  .

N=N+1 (2 is placed after 3)2 (4,5 are placed after 3)+1 (empty tile is moved down)=N

Nmod2

Kita dapat menyimpulkan bahwa ruang keadaan dibagi menjadi dua bagian terputus , satu memiliki dan yang lainnya memiliki .NNmod=0Nmod2=1

Misalnya, dua negara berikut ini tidak terhubung:

 1  2  3  4     1  2  3  4
 5  6  7  8     5  6  7  8
 9 10 11 12     9 10 11 12
13 14 15  *    13 15 14  *  
    N = 4         N = 5
Vor
sumber
Ini adalah kasus untuk 15-puzzle tetapi tampaknya hasilnya dapat digeneralisasi untuk 8-puzzle juga. Terima kasih!
Cam