1. fejezet
Állapottér-reprezentálható problémák 1.1. 1.1.1.
Állati karácsony A feladat
A karácsonyra készülő Nagy családban a gyerekek (Botond, Emese, Karcsi, Orsi és Vanda) alaposan feladták a leckét a szülőknek. Úgy alakult ugyanis, hogy mind az öten konkrét kívánságot fogalmaztak meg ajándékuk kapcsán, történetesen valamennyien egy-egy kisállatra vágytak. A teknőssel és a hörcsöggel nem lett volna baja az ősöknek, s talán még a macskára is rá lehetett volna beszélni őket, ám a kutya és különösen a kakadu már végképp kiverte náluk a biztosítékot. Kivételezni azonban semmiképpen sem szerettek volna, így fájó szívvel kemény döntést hoztak: otthonukat kisállatmentes övezetté nyilvánították. Nem állíthatjuk, hogy a gyerekek egy cseppet sem csalódtak, ugyanakkor az is igaz, hogy a szerencsésen megválasztott ajándékokkal (bicikli, görkorcsolya, pipereasztal, PlayStation és villanyvasút) sikerült őket valamelyest kárpótolni, így igazán nem telt borús hangulatban az ünnep. Kérdésünk: az egyes gyerekek miféle kisállatra vágytak, mit kaptak helyette, s hányadikosok (elsősök, harmadikosok, ötödikesek, hatodikosok vagy nyolcadikosok)? 1. A nyolcadikos nagylány az új pipereasztalnak is szívből örült. 2. Orsi nem igazán rajong a teknősökért. Testvére, aki viszont kifejezetten egy páncélos kisállatra vágyott, egy PlayStationnel vigasztalódhatott. 3. A legkisebb gyerek hörcsögöt szeretett volna, Botond ugyanakkor egy kölyökkutyának örült volna igazán. 4. Az új bicikli gazdája idősebb Emesénél. 5. Vanda, aki öt évfolyammal jár Karcsi fölött, görkorcsolyát kapott, és sosem vágyott kakadura. A feladat eredeti szövege megtalálható a [9] folyóiratban.
1.1.2.
Egy lehetséges állapottér-reprezentáció
Problémánk lényeges jellemzői a gyerekek, valamint hozzájuk kapcsolódóan az, hogy • milyen kisállatra vágytak, • milyen ajándékot kaptak végül karácsonyra, és hogy • hányadikosok. Ez a fajta megközelítés egyúttal azt is meghatározza, hogy a kisállatokat, az ajándékokat és az évfolyamokat a gyerekekhez próbáljuk meg majd hozzárendelni.1 Hogy a későbbiekben sorrendet tudjunk értelmezni a gyerekek között, rendeljünk hozzájuk sorszámokat a következőképpen: Gyerek neve: Sorszám:
Botond 1
Emese 2
Karcsi 3
Orsi 4
Vanda 5
1 Lehetne másképp is csinálni: megpróbálhatnánk például meghatározni azt, hogy az egyes kisállatokra melyik gyerek vágyott, az a gyerek éppen hányadikos, és végül milyen ajándékot kapott a kisállat helyett.
8
1.
Állapottér-reprezentálható problémák
Hasonlóan a kategóriákhoz is rendeljünk sorszámokat: Kategória neve: Sorszám:
kisállat 1
ajándék 2
évfolyam 3
A továbbiakban a gyerekekre is és a kategóriákra is a sorszámaikkal fogunk hivatkozni. Ezek után definiáljuk azoknak a lehetőségeknek a halmazait, amelyek azt írják le, hogy az egyes gyerekekhez milyen kisállatokat rendelhetünk: Hi,1 = { hörcsög, kakadu, kutya, macska, teknős } ∪ { 0 },
i ∈ { 1, 2, 3, 4, 5 }
A 0 szimbólum itt azt fogja jelenteni, hogy az i-vel jelölt gyerekhez még nem rendeltünk hozzá semmilyen kisállatot sem. Ezt követően definiáljuk azoknak a lehetőségeknek a halmazait, amelyek azt írják le, hogy az egyes gyerekekhez milyen ajándékokat rendelhetünk: Hi,2 = { bicikli, görkorcsolya, pipereasztal, PlayStation, villanyvasút } ∪ { 0 },
i ∈ { 1, 2, 3, 4, 5 }
A 0 szimbólum itt azt fogja jelenteni, hogy az i-vel jelölt gyerekhez még nem rendeltünk hozzá semmilyen ajándékot sem. Végezetül definiáljuk azoknak a lehetőségeknek a halmazait, amelyek azt írják le, hogy az egyes gyerekekhez milyen évfolyamokat rendelhetünk: Hi,3 = { 1, 3, 5, 6, 8 } ∪ { 0 },
i ∈ { 1, 2, 3, 4, 5 }
A 0 szimbólum itt azt fogja jelenteni, hogy az i-vel jelölt gyerekhez még nem rendeltünk hozzá semmilyen évfolyamot sem. Képezzük a fenti halmazok Descartes-szorzatát! H1,1 ×H2,1 ×H3,1 ×H4,1 ×H5,1 ×H1,2 ×H2,2 ×H3,2 ×H4,2 ×H5,2 ×H1,3 ×H2,3 ×H3,3 ×H4,3 ×H5,3 = hörcsög 0 0 0 0 kakadu 0 0 0 0 0 0 0 0 0 = 0 0 0 0 0, 0 0 0 0 0, 0 0 0 0 0, . . . , 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 hörcsög 0 0 0 0 hörcsög teknős 0 0 0 0 0 0 pipereasztal 0, . . . , 0 0 0 pipereasztal 0, . . . , 0 0 0 0 0 0 0 3 0 0 0 hörcsög 0 0 0 hörcsög 0 0 0 macska 0 0 0 pipereasztal 0, . . . , PlayStation 0 0 pipereasztal 0 , . . . , 5 3 1 8 6 8 0 3 0 1 hörcsög kakadu kutya macska teknős bicikli görkorcsolya pipereasztal PlayStation villanyvasút, . . . , 1 3 5 6 8 kutya teknős hörcsög kakadu macska bicikli PlayStation villanyvasút pipereasztal görkorcsolya, . . . 5 3 1 8 6 Ennek a halmaznak az elemei rendezett számtizenötösök (3×5-ös mátrixok, ha az elemeiket mátrix alakban rendezzük el). Sokan vannak, számuk 615 = 470 184 984 576. Ha azonban figyelembe vesszük azt, hogy ugyanazt a kisállatot, ajándékot, illetve évfolyamot nem rendelhetjük hozzá egyszerre több gyerekhez, rögtön kevesebb elemtizenötössel lesz dolgunk. Ráadásképpen tehetünk olyan megszorításokat is, melyek szerint a kisállatokat, az ajándékokat és az évfolyamokat ebben a sorrendben rendeljük hozzá a gyerekekhez, azaz először azt mondjuk meg, hogy ki milyen kisállatra vágyott, aztán azt, hogy ki milyen ajándékot kapott, végül pedig azt, hogy ki hányadikos. Még tovább szűkíthetjük az állapotok halmazát, ha a gyerekek között is felállítunk valamilyen sorrendet, például azt a sorrendet követjük, amelyet az
1.1
9
Állati karácsony
alaphalmazok definiálásánál is megadtunk: először Botondhoz rendelünk adatot, aztán Emeséhez, később Karcsihoz, ezt követően Orsihoz, befejezésképpen pedig Vandához. Az előzőekben megfogalmazottak alapján egy
h1,1 h = h1,2 h1,3
h2,1 h2,2 h2,3
h3,1 h3,2 h3,3
h4,1 h4,2 h4,3
h5,1 h5,2 ∈ h5,3
∈ H1,1 ×H2,1 ×H3,1 ×H4,1 ×H5,1 ×H1,2 ×H2,2 ×H3,2 ×H4,2 ×H5,2 ×H1,3 ×H2,3 ×H3,3 ×H4,3 ×H5,3 elemtizenötös a probléma állapota, ha teljesülnek rá a következő kényszerfeltételek: .. . Itt lesznek a kényszerfeltételek definíciói. .. . Ezeknek a kényszerfeltételeknek mindössze 381 értéktizenötös tesz eleget, így problémánk állapotterét ennyi állapot alkotja: h1,1 h2,1 h3,1 h4,1 h5,1 A = h | h = h1,2 h2,2 h3,2 h4,2 h5,2 ∧ kényszerfeltétel (h) , h1,3 h2,3 h3,3 h4,3 h5,3 ahol
kényszerfeltétel (h) = . . . . A kezdőállapot az a helyzet, amikor még senkihez nem rendeltünk hozzá semmit: .. . Itt lesz a kezdőállapot definíciója. .. . A célállapotok halmazának azok az állapotok lesznek az elemei, amelyekben már azt is meghatároztuk, hogy Vanda hányadikos (azaz a mátrix jobb alsó elemének az értéke nem 0): .. . Itt lesz a célállapotok halmazának a definíciója. .. . Az operátorok halmazát a következő, beszédes nevű operátorazonosítókkal definiáljuk: O = Állat(gy, állat ), Ajándék(gy, ajándék ), Évfolyam(gy, évfolyam) , ahol gy ∈ { 1, 2, 3, 4, 5 } állat ∈ { hörcsög, kakadu, kutya, macska, teknős } ajándék ∈ { bicikli, görkorcsolya, pipereasztal, PlayStation, villanyvasút } évfolyam ∈ { 1, 3, 5, 6, 8 } Az Állat(gy, állat ) operátor akkor alkalmazható h1,1 h2,1 h = h1,2 h2,2 h1,3 h2,3
egy h3,1 h3,2 h3,3
h4,1 h4,2 h4,3
állapotra, ha teljesülnek a következő alkalmazási előfeltételek:
h5,1 h5,2 ∈ A h5,3
10
1.
Állapottér-reprezentálható problémák
.. . Itt lesznek az Állat(gy, állat ) operátor előfeltételeinek a definíciói. .. . Az Állat(gy, állat ) operátort egy
h1,1 h = h1,2 h1,3
h2,1 h2,2 h2,3
h3,1 h3,2 h3,3
h4,1 h4,2 h4,3
h5,1 h5,2 ∈ A h5,3
állapotra alkalmazva a következőképpen definiált
h′1,1 ′ h′1,2 h = h′1,3
h′2,1 h′2,2 h′2,3
h′3,1 h′3,2 h′3,3
h′4,1 h′4,2 h′4,3
h′5,1 h′5,2 ∈ h′5,3
∈ H1,1 ×H2,1 ×H3,1 ×H4,1 ×H5,1 ×H1,2 ×H2,2 ×H3,2 ×H4,2 ×H5,2 ×H1,3 ×H2,3 ×H3,3 ×H4,3 ×H5,3 elemtizenötöst kapjuk: .. . Itt lesz az Állat(gy, állat ) operátor hatásának a definíciója. .. . Az Ajándék(gy, ajándék ) operátor akkor alkalmazható egy h1,1 h2,1 h3,1 h4,1 h5,1 h = h1,2 h2,2 h3,2 h4,2 h5,2 ∈ A h1,3 h2,3 h3,3 h4,3 h5,3 állapotra, ha teljesülnek a következő alkalmazási előfeltételek: .. . Itt lesznek az Ajándék(gy, ajándék ) operátor előfeltételeinek a definíciói. .. . Az Ajándék(gy, ajándék ) operátort egy h1,1 h2,1 h = h1,2 h2,2 h1,3 h2,3
h3,1 h3,2 h3,3
h4,1 h4,2 h4,3
h5,1 h5,2 ∈ A h5,3
állapotra alkalmazva a következőképpen definiált
h′1,1 ′ h = h′1,2 h′1,3
h′2,1 h′2,2 h′2,3
h′3,1 h′3,2 h′3,3
h′4,1 h′4,2 h′4,3
h′5,1 h′5,2 ∈ h′5,3
∈ H1,1 ×H2,1 ×H3,1 ×H4,1 ×H5,1 ×H1,2 ×H2,2 ×H3,2 ×H4,2 ×H5,2 ×H1,3 ×H2,3 ×H3,3 ×H4,3 ×H5,3 elemtizenötöst kapjuk: .. . Itt lesz az Ajándék(gy, ajándék ) operátor hatásának a definíciója. .. .
1.1
11
Állati karácsony
Az Évfolyam(gy, évfolyam) operátor akkor alkalmazható h1,1 h2,1 h3,1 h4,1 h = h1,2 h2,2 h3,2 h4,2 h1,3 h2,3 h3,3 h4,3
egy h5,1 h5,2 ∈ A h5,3
állapotra, ha teljesülnek a következő alkalmazási előfeltételek: .. . Itt lesznek az Évfolyam(gy, évfolyam) operátor előfeltételeinek a definíciói. .. . Az Évfolyam(gy, évfolyam) operátort egy h1,1 h2,1 h = h1,2 h2,2 h1,3 h2,3
h3,1 h3,2 h3,3
h4,1 h4,2 h4,3
h5,1 h5,2 ∈ A h5,3
állapotra alkalmazva a következőképpen definiált
h′1,1 ′ h = h′1,2 h′1,3
h′2,1 h′2,2 h′2,3
h′3,1 h′3,2 h′3,3
h′4,1 h′4,2 h′4,3
h′5,1 h′5,2 ∈ h′5,3
∈ H1,1 ×H2,1 ×H3,1 ×H4,1 ×H5,1 ×H1,2 ×H2,2 ×H3,2 ×H4,2 ×H5,2 ×H1,3 ×H2,3 ×H3,3 ×H4,3 ×H5,3 elemtizenötöst kapjuk: .. . Itt lesz az Évfolyam(gy, évfolyam) operátor hatásának a definíciója. .. . Mivel operátorainkat úgy sikerült definiálni, hogy állapotból bizonyíthatóan állapotot állítanak elő, és a kezdőállapotunk állapot, ezért a megoldáskeresés során előállított elemtizenötösökre a kényszerfeltételek ellenőrzése elhagyható. Az állapottérnek, a probléma kezdőállapotának, a célállapotok halmazának, az operátorok alkalmazási előfeltételeinek és hatásának a definiálásával megadtuk az hA, kezdő, C, Oi négyest, a probléma egy lehetséges állapottér-reprezentációját.
