8. fejezet - Kényszer-kielégítés

Tartalom

Elméleti alapok
Feladatok

Elméleti alapok

A mesterséges intelligenciában és az operációkutatásban igen sok feladatot meg lehet fogalmazni úgy, hogy bizonyos változókra megkötéseket teszünk. Vegyük az általános iskolások számára feladott példák közül a SEND+MORE=MONEY kriptoaritmetikai feladatot! Ebben a nyolc betű mindegyike helyére egy-egy különböző számjegyet kell helyettesíteni úgy, hogy a kapott egyenlőség teljesüljön.

Kis munkával az érdeklődő olvasó át tudná fogalmazni a feladatot, hogy egy nyolcdimenziós probléma legyen belőle, ahol a célfüggvény értéke nem lesz más mint az egyenlőség két oldalán álló kifejezés különbségének abszolút értéke. Erre már lehetne alkalmazni a korábban ismertetett módszereket.

Viszont azt is megtehetjük, hogy teljességgel kizárjuk a véletlent. Ennél a feladatnál a keresési tér viszonylag kicsi, így egy számítógépes program igen gyorsan megadhatja a megoldást. Legegyszerűbb esetben kipróbálunk minden egyes kombinációt.

Tekintsük kicsit távolabbról a feladatot. Adva van változók egy X halmaza, esetünkben X = {s, e, n, d, m, o, r, y}. Továbbá adott egy D értelmezési tartomány, amelyből felvehetik értékeiket a változók, ami nálunk D = {0, 1, ... 9}. Végül a feladat meghatározza a kényszerfeltételek C halmazát. A kényszerek több módon is meghatározhatóak, például elég lehet az, hogy 1000s + 100e + 10n + d + 1000m +100o + 10r + e = 10 000m + 1000o + 100n + 10e +y. Viszont szétbonthatóak atomi részekre is, mint d + e = y vagy d + e = 10 + y. A feladat megoldása nem jelent mást, mint a változóknak úgy értéket adni az értelmezési tartományból, hogy az összes feltétel teljesüljön.

Ilyen feladatok nagy számban fordulnak elő logisztikai feladatok során, ütemezéseknél, és millió dollárokat lehet megtakarítani a használatukkal.

A kényszerkielégítési feladatok a 70-es években jelentek meg ebben a formában, és a nem sokkal ezután már helyet kaptak a programozási nyelvekben is. Megfelelő környezetet választva a felhasználónak egyszerűen meg kell fogalmazni a feladatot, és annak megoldását már a számítógépre bízhatja.

Az előbb említett rejtvény esetén az SWI Prolog nyelvű megfogalmazása a következő:

:- use_module(library(clpfd)).
sendmore(Digits) :-
  Digits = [S,E,N,D,M,O,R,Y],
  Digits ins 0..9,
  S #\= 0, M #\= 0,
  all_different(Digits), 
    1000*S + 100*E + 10*N + D
    + 1000*M + 100*O + 10*R + E
    #= 10000*M + 1000*O + 100*N + 10*E + Y,
  label(Digits). 

1

Mivel a Prolog nem tartalmazza alapból az ilyen feladatok megoldását, külső könyvtárat kell felhasználni. A parancsokat, definíciókat ponttal zárjuk le, míg az utasításokat vesszővel választjuk el .

2

A változók listájának megadása igen hasonlít a matematikai jelöléshez, csak szögletes zárójeleket használunk a kapcsos zárójelek helyett.

3

Az alkalmazott könyvtár véges számhalmazból álló értelmezési tartományokat használ. Egy-egy ilyen tartományt a két szélső értékével adhatunk meg. Az ins kulcsszó segítségével megadtuk, hogy az előbb felsorolt változók csak innen kaphatnak értéket.

4

Mivel az S és M betű a szám elején szerepel, ezért nem lehet nulla. A # jellel kezdődnek a kényszerek relációi. A \ jel a tagadás jelzésére szolgál, így egyben a #\= jelzi a nem egyenlőség kényszerét.

5

Ez az egyszerű utasítás 28 darab #\= kiváltására volt most jó, mert azt jelenti, hogy bármely két halmazbeli változónak különböző értéke van.

6

Most egyetlen egyenlőséggel fogalmazzuk meg a feladat fő állítását. Figyeljük meg a #= kényszert!

7

Ez a rövidke utasítás szolgál arra, hogy elindítsa a keresést, és a halmazban felsorolt minden egyes változónak megpróbáljon egy értéket meghatározni. Az utasításnak további paramétert is megadhatnánk, amely a felhasznált keresési módszert adná meg, ám ezzel mi most nem foglalkozunk.

További magyar nyelvű szöveges feladatok és hasonló megoldásaik megtalálhatóak a szerzők Prolog feladatgyűjteményében. Az ilyen — CLP-nek nevezett — feladatok megfogalmazásához nem szükséges a Prolog nyelv alapos ismerete, csak pár szerkezetre van szükségünk. Ezeknek az ismertetője a SWI Prolog leírásának A7 mellékletében szerepel.

A kényszerkielégítési feladatok jellemző példája a térképszínezés. [Russell10] 5. fejezete ezt igen részletesen ismerteti. Andrew Moore honlapján pár animáció folyamatában ismerteti a keresési módszert (http://www.cs.cmu.edu/~awm/animations/constraint/).

Ezen animációk megmutatják, hogy milyen megvalósítási szintek léteznek. A sima mélységi kereséssel az a probléma, hogy adott kényszer nem teljesülése esetén is megpróbálja további változók értékét is meghatározni. A backtrack megoldás azonnal visszafordul, amint megsért egy kényszert. Ezzel már jelentősen gyorsul a megoldás meghatározásának sebessége. A backtrack esetén egy-egy változót jelző csúcsnál a kiinduló értékkészlet a változó értelmezési tartománya.

A backtrack módszerén tovább javíthat a forward checking, amely úgy működik, ha egy változó értéket kap, akkor a vele valamilyen kapcsolatban álló még értékkel nem rendelkező változó értékkészletéből töröljük mindazokat az értékeket, melyek az első változó értékével nem férnek össze. (Így ezekkel a backtrack algoritmusnak már nem kell foglalkoznia.) Ha például a számrejtvényben először az E kap mondjuk 2-t értékül, akkor mivel más betű már nem jelölhet 2-t, így azok mellől töröljük ezt az értéket.

Ennek a módszernek a továbbfejlesztése a constraint propagation, ahol bizonyos kényszerek szülte megszorítások következményeit is meghatározzuk annak érdekében, hogy zsákutcákat elkerüljük. Viszont a következmények megtalálása időnként tovább tart, mintha sima keresést vetettünk volna be, így óvatosan kell alkalmazni ezt a módszert.

Az összes következmény megtalálása helyett egyszerűbb az arc consistency használata, mely olyan lehetőségeket keres a még értékkel nem rendelkező változók értelmezési tartományában, melyek nem fordulhatnak elő a vele kapcsolatban álló változó még felhasználható értékei alapján.

Ezek a módszerek a legtöbb kényszerprogramozási könyvtárban illetve rendszerben implementáltak. Így nem az implementálásukra, hanem az alkalmazásukra érdemes figyelmet fordítani.