1.2. Példák állapottér-reprezentációra

A nyolcas kirakó játék

Adott nyolc számozott négyzetalakú lapocska, melyek egy táblán -as sémában helyezkednek el. Egy lapocskányi hely a táblán így nyilván üres. Az üres hellyel szomszédos bármelyik lapocskát az üres helyre tolhatjuk. A feladat az, hogy adott kezdőállásból kiindulva adott célállásnak megfelelő elrendezést alakítsunk ki.

A probléma világa: a tábla a számozott lapocskákkal.

A világ leírása: a tábla egyes pozícióin épp mely számozott lapocskák vannak.

Table 1.1. Egy-egy pozícióra hivatkozás: (sor,oszlop)

pozíció

lapocska

ahol minden esetén.

Tehát minden -ra.

A probléma világának egy-egy állapotát egy-egy olyan

Equation 1.. 


érték 9-es (-as mátrix) határozza meg, melyben az értékek -beli elemek, és az érték 9-esben minden egyes érték -ból pontosan egyszer fordul elő:

Equation 1.. 


A kezdőállapot és a célállapot:

Equation 1.. 


Equation 1.. 


A számozott lapocskák tologatásai során az üres pozíciója mindig változik, az eredetihez képest fel, le, jobbra vagy balra kerül egy-egy pozícióval. Így tehát négy operátor segítségével leírhatjuk az állapotváltozásokat. A

Equation 1.. 


operátort akkor alkalmazhatjuk, ha

Equation 1.. 


Az alkalmazás eredménye, ha az éppen :

Equation 1..