Espace d'état accessible d'un puzzle de 8

11

Je viens de commencer à étudier l'intelligence artificielle et je me demande pourquoi l'espace d'état accessible d'un puzzle de 8 est . Je vois que le nombre de permutations des tuiles est demais il n'est pas immédiatement évident pourquoi la moitié des états possibles du puzzle sont inaccessibles à un état donné. Quelqu'un peut-il élaborer?9!/29!

Une image d'un 8-puzzle pour référence avec une configuration aléatoire à gauche et l'état de l'objectif à droite:

Exemple de 8 casse-tête

Came
la source
3
Parce que le graphe d'état se compose de deux composants déconnectés de taille égale (le nombre total d'inversions de permutation de chaque état est invariant modulo 2, donc deux états qui ont un nombre total d'inversions de permutation impairs et pairs ne sont pas connectés); Je n'ai pas trouvé d'exemple bien expliqué, mais cette présentation devrait être suffisamment claire pour vous permettre de le comprendre (sauf la faute de frappe "connecté" qui devrait être remplacé par "déconnecté")
Vor
@Pour devenir une réponse?
Yuval Filmus

Réponses:

12

Il s'agit d'une extension de cette présentation .

Parce que le graphique d'état se compose de deux composants déconnectés de taille égale. Sans perte de généralité, nous pouvons supposer que l' état cible est .123...15

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

Étant donné un état une inversion de permutation est une tuile qui est placée après mais ; cela se produit lorsque (a) est dans la même rangée de , mais à sa droite, ou (b) est dans une rangée inférieure:STiTji<jTiTjTi

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

Nous définissons comme le nombre de tuiles , qui apparaît après . Par exemple, dans l'état:NjTii<jTj

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

nous avons qu'après il y a une tuile ( ) qui devrait être devant, donc ; après il y a quatre tuiles ( ) qui devraient être devant, donc .T7T6N7=1T10T7,T8,T9,T6N10=4

Soit la somme de tous les et le numéro de ligne de la tuile videNNiT

N=i=115Ni+row(T)

Dans l'exemple ci-dessus, nous avons:N=N7+N8+N9+N10+row(T)=1+1+1+4+4=11

On peut remarquer que lorsque la tuile vide est déplacée horizontalement, ne change pas; si nous déplaçons la tuile vide verticalement, change d'une quantité paire.N N

Par exemple:

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

Donc est invariant sous n'importe quel mouvement légal de la tuile vide .Nmod2

Nous pouvons conclure que l'espace d'état est divisé en deux moitiés déconnectées , l'une ayant et l'autre ayant .Nmod=0Nmod2=1

Par exemple, les deux états suivants ne sont pas connectés:

 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
la source
C'est le cas pour un puzzle de 15 mais il semble que le résultat peut être généralisé pour un puzzle de 8 également. Merci!
Cam