Я только начал изучать искусственный интеллект и мне интересно , почему достижимо фазовое пространство 8-головоломки . Я вижу , что число перестановок из плитокно не сразу очевидно, почему половина возможных состояний головоломки недоступна в любом данном состоянии. Кто-нибудь может уточнить?
Изображение 8-головоломки для справки со случайной конфигурацией на левом и целевом состоянии справа:
artificial-intelligence
кулачок
источник
источник
Ответы:
Это расширение этой презентации .
Потому что граф состояний состоит из двух несвязанных компонентов одинакового размера. Без ограничения общности можно считать, что целевым состоянием является .123, , ,15□
Учитывая состояние перестановка инверсия является плитка , которая помещается после но ; это происходит, когда (a) находится в том же ряду , но справа от него, или (b) находится в нижнем ряду:Т я Т J я < J Т я Т J Г яS Tя TJ я < j Tя TJ Tя
Мы определяем как количество плиток , которое появляется после . Например, в состоянии:T i i < j T jNJ Tя я < j TJ
мы имеем, что после есть один тайл ( ), который должен быть перед ним, поэтому ; после есть четыре фрагмента ( ), которые должны быть перед ним, поэтому . Т 6, Н 7 = 1, Т 10, Т 7 , Т 8 , Т 9 , Т 6, Н 10 = 4T7 T6 N7= 1 T10 T7, Т8, Т9, Т6 N10= 4
Пусть будет суммой всех и номера строки пустого тайлаN я T ◻N Nя T□
В приведенном выше примере мы имеем:N= N7+ N8+ N9+ N10+ Г о ш ( Т□) = 1 + 1 + 1 + 4 + 4 = 11
Мы можем заметить, что при перемещении пустой плитки по горизонтали не изменяется; если мы переместим пустую плитку вертикально, изменится на четное количество.NN N
Например:
Таким образом, является инвариантом при любом законном перемещении пустой плитки .Nмод 2
Мы можем заключить, что пространство состояний разделено на две несвязанные половины, одна из которых имеет а другая имеет .Nмод = 0 Nмодификация2 = 1
Например, следующие два состояния не связаны:
источник