Erreichbarer Zustandsraum eines 8-Puzzles

11

Ich habe gerade angefangen, künstliche Intelligenz zu studieren und frage mich, warum der erreichbare Zustandsraum eines 8-Puzzles . Ich sehe, dass die Anzahl der Permutationen der Kacheln 9 beträgt ! Es ist jedoch nicht sofort ersichtlich, warum die Hälfte der möglichen Zustände des Puzzles in einem bestimmten Zustand nicht erreichbar ist. Kann jemand näher darauf eingehen?9!/29!

Ein Bild eines 8-Puzzles als Referenz mit einer zufälligen Konfiguration links und dem Zielzustand rechts:

Beispiel 8-Puzzle

Nocken
quelle
3
Da der Zustandsgraph aus zwei getrennten Komponenten gleicher Größe besteht (die Gesamtzahl der Permutationsinversionen jedes Zustands ist invariant modulo 2, sodass zwei Zustände mit einer ungeraden und geraden Gesamtzahl der Permutationsinversionen nicht verbunden sind); Ich habe kein gut erklärtes Beispiel gefunden, aber diese Präsentation sollte klar genug sein, damit Sie es verstehen können (mit Ausnahme des Tippfehlers "verbunden", der durch "getrennt" ersetzt werden sollte)
Vor dem
@ Oder in eine Antwort verwandeln?
Yuval Filmus

Antworten:

12

Dies ist eine Erweiterung dieser Präsentation .

Weil das Zustandsdiagramm aus zwei getrennten Komponenten gleicher Größe besteht. Ohne Beschränkung der Allgemeinheit können wir davon ausgehen , dass der Soll - Zustand ist .123...15

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

Bei gegebenem Zustand eine Permutationsinversion eine Kachel T i , die nach T j platziert wird, aber i < j ; Dies geschieht, wenn (a) T i in derselben Reihe von T j liegt , aber rechts davon, oder (b) T i in einer unteren Reihe liegt:STiTji<jTiTjTi

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

Wir definieren als die Anzahl der Kacheln T i , i < j , die nach T j erscheinen . Zum Beispiel im Zustand:NjTii<jTj

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

wir haben, dass nach eine Kachel ( T 6 ) davor sein sollte, also N 7 = 1 ; Nach T 10 gibt es vier Kacheln ( T 7 , T 8 , T 9 , T 6 ), die davor liegen sollten, also N 10 = 4 .T7T6N7=1T10T7,T8,T9,T6N10=4

Sei die Summe aller N i und die Zeilennummer der leeren Kachel T NNiT

N=i=115Ni+row(T)

N=N7+N8+N9+N10+row(T)=1+1+1+4+4=11

N N

Beispielsweise:

 .  .  .  .      .  .  .  .
 .  .  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

Nmod=0Nmod2=1

Zum Beispiel sind die folgenden zwei Zustände nicht verbunden:

 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
quelle
Dies ist bei einem 15-Puzzle der Fall, aber es scheint, dass das Ergebnis auch für ein 8-Puzzle verallgemeinert werden kann. Vielen Dank!
Cam