CSP feladat - 5 kiralyno

1. 
Oldjuk meg a kovetkezo kenyszerkielegitesi feladatot.
Egy 5x5 meretu tablara 5 kiralynot kell elhelyezni ugy hogy azok ne tamadjak egymast. Az elso es a masodik sor kiralynoi mar le vannak rakva, ezek a Q1=2 es a Q2=5. A Q3, Q4 es Q5 kiralynokhoz meg nincsenek ertekek rendelve, tehat a Q3, Q4 es Q5 kiralyno felveheti akarmelyik erteket az {1,2,3,4,5} halmazbol.
Eloszor a forward checking segitsegevel hatarozzuk meg a meg nem hozzarendelt kiralynok domenjet.
Amint az eloadason mar mondtuk, a forward checking a hozzarendelt valtozoktol tovabbitja az informaciot a meg nem hozzarendelt valtozok fele.

2.
Ha Q1=2, akkor a Q3, Q4 es Q5 valtozok domenjebol torolni kell valamely ertekeket. Q3 nem lehet 2 meg 4, Q4 nem lehet 2 meg 5, Q5 pedig nem lehet 2.

3.
A Q2=5 lerakott kiralyno miatt is torolni kell a Q3, Q4 es Q5 domenjebol. A Q3-bol toroljuk a 4-et es a 5-ot, a Q4-bol toroljuk a 3-at es az 5-ot, a Q5-bol pedig a 2-t es az 5-ot.
Ezek utan a Q3 domenje az {1,3}, a Q4 domenje az {1,4}, a Q5 domenje pedig az {1,3,4} marad.

4.
Probaljuk most a lerakni a tobbi kiralynot. Induljunk a Q3=1-gyel. Ekkor a forward checking alapjan torolni kell a Q4-bol az 1-et, a Q5-bol pedig az 1-et es a 3-at. Most a Q4 es a Q5 domenjeben is csak 1 ertek maradt, mind a ket valtozo csak 4 lehet es nyilvanvalo hogy tamadni fogjak egymast, de a forward checking ezt nem veszi eszre, hanem tovabblep. 

5.
A kovetkezo lepesben a Q4-hez rendeljuk a 4-et, es a forward checking ertelmeben a Q5-bol torolni kell a 4-et. Ekkor a Q5 domenje ures lesz, ami azt jelenti hogy a Q3=1-re es Q4=4-re nincs megoldas, ezert visszalepesre, illetve backtrackre kerul sor. 

6.
Eloszor felvesszuk a Q4-et, de mivel nincs mas szabad hely ahova lerakhatnank, meg egy lepest vissza kell lepni, es fel kell venni a Q3-at is. A Q3-nak van meg egy szabad helye a Q3=1 mezon kivul, ez a Q3=3. Ez a hozzarendeles utan a Q4-bol toroljuk a 4-et, a Q5-bol pedig toroljuk az 1-et es a 3-at. A Q4 domenje 1 marad, a Q5 domenje pedig 4. 

7.
A kovetkezo lepesben a Q4-hez rendeljuk az egyetlen megmaradt erteket, ez az 1. Ezt a hozzarendelest nem koveti semmilyen torles a Q5 domenjebol, es vegul a Q5-hoz rendeljuk a 4-et amivel meg is van a megoldas.
Arra kovetkeztethetunk, hogy a forward checking ugyan megtalalta a megoldast, de nem volt kepes koran detektalni hogy kenyszermegszeges fog tortenni, ezert kellett visszalepni.

8.
Vizsgaljuk most ki, hogy hogyan oldana meg az ag-konzisztencia ugyanezt a feladatot. Feltetelezzuk, hogy mar korabban meghataroztuk a megmaradt valtozok, tehat a Q3, Q4 es a Q5 domenjet. Az agak amelyeket ki kell vizsgalni a kovetkezok: Q3-Q4, Q4-Q3, Q3-Q5, Q5-Q3, Q4-Q5 es Q5-Q4. Ne felejtsuk el hogy amennyiben az ag nem konzisztens mindig a kezdopontbol torlunk.

9.
Vizsgaljuk eloszor a Q3-Q4 agat. Ha Q3=1, Q4 lehet 4, ha Q3=3, Q4 lehet 1. Tehat mivel minden ertekre a kezdopontbol hozza lehet rendelni a vegpontot ugy, hogy ne legyen kenyszermegszeges (tehat hogy a kiralynok ne tamadjak egymast), a Q3-Q4 ag konzisztens. 

10.
Kovetkezik a Q4-Q3. Ha Q4=1, Q3 lehet 3, ha Q4=4, Q3 lehet 1. Tehat ez az ag is konzisztens. Kovetkezik a Q3-Q5, ez is konzisztens. 

11.
Utana vizsgaljuk ki a Q5-Q3-at. Ha Q5=1, Q3 nem lehet se 1, se 3 mert mind a ket esetben tamadas lenne, ezert ez az ag nem konzisztens, de konzisztensse lehet tenni ugy, hogy a Q5 domenjebol kitoroljuk az 1-est. Vizsgaljuk tovabb a Q5 ertekeit. Ha Q5=3, a Q3-at megint nem lehet szabalyosan hozzarendelni, ezert a Q5-bol torolni fogjuk a 3-at is. A Q5=4-re nem lesz kenyszermegszeges, ezert ezt nem toroljuk ki. 

12.
Kovetkezik a Q4-Q5. Q4=1-re minden rendben van, de Q4=4-re nem lehet hozzarendelni a Q5-ot, ezert a Q4-bol toroljuk a 4-et. 

13.
Mivel a Q4 elveszitette a 4-est a domenjebol, a Q3-Q4 nem lesz tobbet konzisztens mert a Q3=1-re a Q4-et nem lehet hozzarendelni, ezert a Q3-bol toroljuk az 1-est. Most minden valtozo domenjeben csak egy ertek maradt, minden ag konzisztens, ezert megvan a megoldas. 

14.
Amint latjuk, az ag-konzisztencia segitsegevel hosszabb ideig tartott a kivizsgalas, de nem kellett egyszer se visszalepni.

15.
A kovetkezo peldat is az ag-konzisztencia segitsegevel oldjuk meg.
Feltetelezzuk, hogy egy konferencian ahol 3 resztvevo van (jeloljuk oket A, B es C-vel), 3 terminus letezik (legyenek 1, 2 es 3) amelyben az eloadok tarthatjak a beszamolokat. A szervezok feladata ugy megszervezni a konferenciat hogy mind a harom eloado kulonbozo terminusban tartsa a beszamolojat, es az A eloado a C eloado elott lepjen fel. Hatarozzuk meg, hogy melyik eloado melyik terminusban tarthatja az eloadasat. A betartando kenyszerek unarisak, binarisak vagy magasabb renduek?

16.
Ahhoz hogy meghatarozzuk a kenyszerek tipusat, rajzoljuk fel eloszor a feladat kenyszergrafjat. A kenyszerek negyzettel vannak jelolve. Az elso kenyszer 3 valtozot erint, ezert ez magasabb rendu kenyszer. A masodik kenyszer ket valtozot erint, ezert ez binaris kenyszer.

17.
Vizsgaljuk most ki az egyes agak konzisztenciajat.
Eloszor vegyuk az A-C kenyszert. Ha A=1, C lehet 2 vagy 3, ha A=2, C meg lehet 3, de ha A=3, C-t nem lehet hozzarendelni ugy hogy ervenyes legyen az A<C feltetel. Ezert ez az ag nem konzisztens, de konzisztensse lehet tenni ugy hogy az A-bol toroljuk a 3-at. Nezzuk most ugyanezt az agat forditott iranyban, tehat a C>A esetet. C=2 es 3-ra nincs gond, de C=1-re az A-t nem lehet hozzarendelni, ezert ez az ag sem konzisztens, es a C-bol torolni kell az 1-et. Amig nem vesznek fel egyforma ertekeket, az A-B, B-A, B-C es C-B mindig konzisztensek mert nincs az a kenyszer amelyik osszefuggesbe hozna oket. 

18.
Most kezdhetjuk a hozzarendendelest. Ha A=1, C lehet 2 vagy 3, a B pedig kulonbozik C-tol, itt ket megoldas van: az A,B,C es az A,C,B. Ha A=2, akkor C csak 3 lehet, B pedig 1. Ezt a kivizsgalast onallo gyakorlasra hagyjuk. Tehat osszesen 3 megoldas van: A,B,C, A,C,B es B,A,C. Mind a 3 esetben az eloadok kulonbozo terminusban prezentalnak, es az A eloado a C eloado elott tartja a beszamolojat.