Достижимое пространство состояний 8-головоломки

11

Я только начал изучать искусственный интеллект и мне интересно , почему достижимо фазовое пространство 8-головоломки . Я вижу , что число перестановок из плитокно не сразу очевидно, почему половина возможных состояний головоломки недоступна в любом данном состоянии. Кто-нибудь может уточнить?9!/29!

Изображение 8-головоломки для справки со случайной конфигурацией на левом и целевом состоянии справа:

Образец 8-пазл

кулачок
источник
3
Поскольку граф состояний состоит из двух несвязанных компонентов одинакового размера (общее число инверсий перестановок каждого состояния является инвариантным по модулю 2, поэтому два состояния, которые имеют общее число инверсий перестановки нечетные и четные, не связаны); Я не нашел хорошо объясненного примера, но эта презентация должна быть достаточно ясной, чтобы вы могли ее понять (кроме опечатки «подключен», которую следует заменить на «отключен»)
Vor
@ Ты превратишься в ответ?
Юваль Фильмус

Ответы:

12

Это расширение этой презентации .

Потому что граф состояний состоит из двух несвязанных компонентов одинакового размера. Без ограничения общности можно считать, что целевым состоянием является .123...15

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

Учитывая состояние перестановка инверсия является плитка , которая помещается после но ; это происходит, когда (a) находится в том же ряду , но справа от него, или (b) находится в нижнем ряду:Т я Т J я < J Т я Т J Г яSTiTji<jTiTjTi

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

Мы определяем как количество плиток , которое появляется после . Например, в состоянии:T i i < j T jNjTii<jTj

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

мы имеем, что после есть один тайл ( ), который должен быть перед ним, поэтому ; после есть четыре фрагмента ( ), которые должны быть перед ним, поэтому . Т 6, Н 7 = 1, Т 10, Т 7 , Т 8 , Т 9 , Т 6, Н 10 = 4T7T6N7=1T10T7,T8,T9,T6N10=4

Пусть будет суммой всех и номера строки пустого тайлаN я T NNiT

N=i=115Ni+row(T)

В приведенном выше примере мы имеем:Nзнак равноN7+N8+N9+N10+ровес(T)знак равно1+1+1+4+4знак равно11

Мы можем заметить, что при перемещении пустой плитки по горизонтали не изменяется; если мы переместим пустую плитку вертикально, изменится на четное количество.NN N

Например:

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

N'знак равноN+3 (2 ставится после 3,4,5)-1 (пустая плитка перемещается вверх)знак равноN+2

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

N'знак равноN+1 (2 ставится после 3)-2 (4,5 ставятся после 3)+1 (пустая плитка перемещается вниз)знак равноN

Таким образом, является инвариантом при любом законном перемещении пустой плитки .Nмодификация2

Мы можем заключить, что пространство состояний разделено на две несвязанные половины, одна из которых имеет а другая имеет .Nмодификациязнак равно0Nмодификация2знак равно1

Например, следующие два состояния не связаны:

 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
Вор
источник
Это касается 15 головоломок, но, похоже, результат можно обобщить и для 8 головоломок. Спасибо!
Cam