5.5. Összefoglalás

  • A kényszerkielégítési problémák (CSP-k) változókból állnak, melyekre kényszerek vonatkoznak. Nagyon sok fontos valósvilág-beli probléma írható le kényszerkielégítési problémaként. A kényszerkielégítési problémák struktúrája egy kényszergráffal reprezentálható.

  • A visszalépéses keresés (backtracking search), a mélységi keresés egyik formája, a kényszerkielégítési problémák megoldásának gyakran alkalmazott eszköze.

  • A legkevesebb fennmaradó érték (least-remaining value) heurisztika és a fokszám- (degree-) heurisztika tárgyterület-független módszerek annak eldöntésére, hogy a visszalépéses keresés során melyik változót válasszuk ki következőnek. A legkevésbé korlátozó érték (least-constraining value) heurisztika segítségül szolgálhat a változóértékek sorrendezésében.

  • A visszalépéses algoritmus nagyban csökkenteni tudja a probléma elágazási tényezőjét a létrehozott részleges hozzárendelések következményeinek terjesztésével. Erre a legegyszerűbb módszer az előrenéző ellenőrzés (forward checking). Az élkonzisztencia (arc consistency) kikényszerítés egy jóval nagyobb teljesítőképességű technika, de tovább is tart a futása.

  • Visszalépésre akkor kerül sor, amikor egy változóhoz már nem találunk hozzárendelhető értéket. A konfliktusvezérelt visszaugrás (conflict-directed backjumping) közvetlenül a probléma okához ugrik vissza. A min-konfliktusok (min-conflicts) heurisztikát használó lokális keresést komoly sikerrel alkalmazták a kényszerkielégítési problémákra.

  • A kényszerkielégítési probléma komplexitása szorosan kötődik a saját kényszergráfjának struktúrájához. A fastruktúrájú problémák megoldhatók lineáris időben. A vágóhalmaz-kondicionálás (cutset conditioning) az eredeti kényszerkielégítési problémát fastruktúrájúvá alakíthatja, és nagyon hatékonynak bizonyul, ha sikerül kis vágóhalmazt találnunk. A fadekompozíció (tree decomposition) technikák a kényszerkielégítési problémát részproblémák fájává alakíthatják, és hatékonyak, ha a kényszergráf faszélessége (tree width) kicsi.

5.5.1. Irodalmi és történeti megjegyzések

A kényszerkielégítéssel kapcsolatos legkorábbi munka a numerikus kényszerekhez kötődik. Az egész értékű egyenlőségi kényszereket Brahmagupta indiai matematikus tanulmányozta a 7. században. Ezeket gyakran diofantoszi egyenleteknek is nevezik Diofantosz görög matematikus (kb. 200–284) nyomán, aki valójában a pozitív racionális számok esetét vizsgálta. A lineáris egyenlőségek változókiküszöböléssel történő megoldásának szisztematikus módszereit Gauss tanulmányozta (Gauss, 1829), a lineáris egyenlőtlenség alakú kényszerek megoldása Fourier-ig vezethető vissza (Fourier, 1827).

A véges tartományú kényszerkielégítési problémáknak hosszú történetük van. A gráfszínezés például (amelynek a térképszínezés csak egy speciális esete) a matematika régi problémáinak egyike. Biggs és társai (Biggs és társai, 1986) szerint a négyszín-sejtést (minden síkbeli gráf kiszínezhető legfeljebb négy színnel) először Francis Guthrie, de Morgan egyik tanítványa fogalmazta meg 1852-ben. A feladat ellenállt a megoldási kísérleteknek – annak ellenére, hogy néhányan publikációkban az ellenkezőjét állították –, mígnem Appel és Haken (Appel és Haken, 1977) előállt egy számítógépre is támaszkodó bizonyítással.

A kényszerkielégítési problémák egyes osztályai gyakran felmerültek a számítógép-tudomány történetében. Az egyik legkorábbi nagy hatású példa a SKETCHPAD rendszer volt (Sutherland, 1963), amely geometriai kényszereket oldott meg diagramokban, és a modern rajzolóprogramok és CAD-programok előfutárának tekinthető. A kényszerkielégítési problémák általános problémaosztályként történő azonosítása Ugo Montanari (Montanari, 1974) nevéhez fűződik. A magasabb rendű kényszerkielégítési problémák visszavezetése segédváltozók felvételével tisztán bináris esetre (lásd 5.11. feladat) eredetileg a 19. századi logikushoz, Charles Sanders Peirce-hez fűződik. A CSP-irodalomba Dechter (Dechter, 1990b) vezette be, majd Bacchus és Van Beek (Bacchus és van Beek, 1998) dolgozták ki. A megoldásokra vonatkozó preferenciákkal kiegészített kényszerkielégítési problémákat széles körben tanulmányozza az optimalizáció irodalma; lásd (Bistarelli és társai, 1997)-et a CSP-keretrendszer preferenciákat is megengedő általánosításáról. A vödör-eliminációs algoritmus (Dechter, 1999) szintén alkalmazható az optimalizációs problémákra.

A kényszerkielégítési problémák visszalépéses keresése Bitnertől és Reingoldtól (Bitner és Reingold, 1975) származik, noha ők az alapalgoritmust a 19. századig követik vissza. Bitner és Reingold az MRV-heurisztikát is bevezették (ők ezt leginkább-korlátozott-érték heurisztikának nevezték). Az MRV-heurisztika utáni eldöntetlen helyzetek megoldására Brelaz (Brelaz, 1979) a fokszám-heurisztikát alkalmazta. Az így létrejövő algoritmus, minden egyszerűsége ellenére, máig a leghatékonyabb tetszőleges gráfok k-színezésére. A legkevésbé-korlátozó-érték heurisztikát Haralick és Elliot javasolták (Haralick és Elliot, 1980).

A kényszerterjesztési módszereket Waltz (Waltz, 1975) sikere tette népszerűvé, amelyet a számítógépes látásnál felmerülő poliéder-élcímkézési problémán ért el. Waltz megmutatta, hogy sok probléma esetén a kényszerterjesztés teljesen kiküszöböli a visszalépést. Montanari (Montanari, 1974) bevezette a kényszerhálózat és az útvonalkonzisztencia-terjesztés fogalmát. Alan Mackworth (Mackworth, 1977) javasolta az AC-3 algoritmust az élkonzisztencia betartatására, csakúgy, mint annak általános lehetőségét, hogy valamilyen fokú konziszentencia-ellenőrzést építsünk be a visszalépéses algoritmusba. Az AC-4, egy jóval hatékonyabb algoritmus, melyet Mohr és Henderson fejlesztettek ki (Mohr és Henderson, 1984). Nem sokkal Mackworth cikkének megjelenése után a kutatók elkezdtek kísérletezni a konzisztencia-ellenőrzések költsége és a kereséslevágásban jelentkező előny csereviszonyának feltérképezésével. Haralick és Elliot (Haralick és Elliot, 1980) a McGregor által leírt (McGregor, 1979) minimális előrenéző ellenőrzés mellett álltak ki, míg Gaschnig (Gaschnig, 1979) minden egyes változó-hozzárendelés után élkonzisztencia-ellenőrzéseket javasolt (ezt az algoritmust nevezte később Sabin és Freuder (Sabin és Freuder, 1994) MAC-nak). Az utóbbi cikk valamennyire meggyőző bizonyítékot hoz fel amellett, hogy nehezebb problémáknál kifizetődik a teljes élkonzisztencia-ellenőrzés. Freuder (Freuder 1978, 1982) megvizsgálta a k-konzisztenciát és ennek kapcsolatát a kényszerkielégítési problémák megoldásának komplexitásával. Apt (Apt, 1999) egy általános algoritmikus keretrendszert mutat be a konzisztenciaterjesztési algoritmusok vizsgálatára.

A magasabb rendű kényszerek kezelésének külön módszerei elsősorban a kényszerlogikai-programozás (constraint logic programming) keretein belül alakultak ki. Marriott és Stuckey (Marriott és Stuckey, 1998) nagyszerű összefoglalást nyújt erről a kutatási területről. A MindKül kényszert Regin (Regin, 1994) tanulmányozta. Az alsó és felső határokból álló kényszereket Van Hentenryck és társai vezették be a kényszerlogikai programozásba (Van Hentenryck és társai,1998).

Az alapvető visszaugró módszer John Gaschnigtől (Gaschnig, 1977; 1979) származik. Kondrak és van Beek (Kondrak és Van Beek, 1997) megmutatták, hogy ezt az algoritmust lényegében magában foglalja az előrenéző ellenőrzés. A konfliktusvezérelt visszaugrást Prosser (Prosser, 1993) alakította ki. Az intelligens visszalépés legáltalánosabb és legerősebb formáját tulajdonképpen már nagyon korán kifejlesztette Stallman és Sussman (Stallman és Sussman, 1977). Technikájuk, a függőségvezérelt visszalépés (dependency-directed backtracking) az igazság-karbantartó rendszerek (truth maintenance systems) kifejlesztéséhez vezetett (Doyle, 1979), amelyekkel a 10.8. alfejezetben foglalkozunk. A két terület közti kapcsolatot De Kleer (De Kleer, 1989) vizsgálta.

Stallman és Sussman munkája a kényszerfeljegyzés (constraint recording) elképzelését is bevezette: a keresés által elért részleges eredményeket elmentjük és a keresés során később felhasználjuk. Ezt az elképzelést a visszalépéses keresésbe formális módon Dechter (Dechter, 1990a) vezette be. A visszajegyzés (backmarking) (Gaschnig, 1979) egy különlegesen egyszerű módszer, amelyben a konzisztens és inkonzisztens páronkénti hozzárendeléseket elmentjük, hogy elkerüljük a kényszerek későbbi újraellenőrzését. A visszajegyzés ötvözhető a konfliktusvezérelt visszaugrással; Kondrak és Van Beek (Kondrak és Van Beek, 1997) bemutatnak egy hibrid algoritmust, amely bizonyíthatóan tartalmazza mindkét külön módszert. A dinamikus visszalépés (dynamic backtracking) (Ginsberg, 1993) megőrzi a változók későbbi részhalmazaiból származó sikeres parciális hozzárendeléseket, amikor egy olyan korábbi választási pontra ugrik vissza, amely a későbbi sikert nem teszi érvénytelenné.

A kényszerkielégítési problémák lokális keresését Kirkpatrick és társai (Kirkpatrick és társai, 1983) szimulált lehűtésről (simulated annealing) (lásd 4. fejezet) szóló munkája tette népszerűvé, és ezt széles körben alkalmazták az ütemezési problémáknál. A min-konfliktusok heurisztikát először Gu (Gu, 1989) javasolta, és tőle függetlenül Minton és társai (Minton és társai, 1992) is kifejlesztették. Sosic és Gu (Sosic és Gu, 1994) megmutatta, hogyan lehet ennek a heurisztikának az alkalmazásával a 3 000 000-királynő problémát kevesebb, mint egy perc alatt megoldani. A bámulatos siker, amit a min-konfliktusokat használó lokális keresés ért el az n-királynő problémában, a „könnyű” és a „nehéz” problémák természetének és elterjedtségének újraértékeléséhez vezetett. Peter Cheesman és társai (Cheesman és társai, 1991) feltérképezték a véletlenszerűen generált kényszerkielégítési problémák nehézségét, és azt találták, hogy majdnem minden ilyen probléma vagy triviálisan könnyű, vagy megoldhatatlan. Csak akkor találunk „nehéz” probléma példányokat, ha a problémagenerátor paramétereit egy bizonyos szűk tartományba állítjuk be, melyen belül a problémák közelítőleg fele megoldható. Ezzel a jelenséggel a 7. fejezetben foglalkozunk részletesebben.

A kényszerkielégítési problémák struktúrájának és nehézségének kapcsolatával foglalkozó kutatást Freuder (Freuder, 1985) indította el, aki megmutatta, hogy az élkonzisztens fák esetében a keresés visszalépések nélkül fut le. Egy hasonló eredmény az aciklikus hipergráfokra való kiterjesztésével együtt jött létre az adatbázisokkal foglalkozó kutatói közösségben (Beeri és társai, 1983). Ezen cikkek publikálása óta komoly haladás történt a kényszergráf struktúrája és a kényszerkielégítési probléma megoldási komplexitásának kapcsolatát illetően. A faszélesség fogalmát a gráfelmélettel foglalkozó Robertson és Seymour (Robertson és Seymour, 1986) vezették be. Freuder munkásságára építve Dechter és Pearl (Dechter és Pearl, 1987, 1989) ugyanezt a fogalmat – amit ők indukált szélességnek (induced width) hívtak – alkalmazták a kényszerkielégítési problémákra és kifejlesztették az 5.4. alfejezetben felvázolt fadekompozíciót. Az adatbázis-elméletre és erre az eredményre alapozva Gottlob és társai (Gottlob és társai, 1999a, 1999b) kialakították a kényszerkielégítési probléma hipergráfként történő felfogásán alapuló hiperfaszélesség (hypertree width) fogalmat. Annak megmutatásán túl, hogy minden w szélességű hiperfa-CSP megoldható O(nw+1logn) időben, azt is bebizonyították, hogy a hiperfaszélesség az összes korábbi „szélesség”-mértéket magában foglalja (abban az értelemben, hogy bizonyos esetekben a hiperfaszélesség korlátozott, bizonyos esetekben pedig nem).

Sok jó áttekintés létezik a CSP-technikákhoz, például Kumar (Kumar, 1992), Dechter és Frost (Dechter és Frost, 1999) és Bartak (Bartak, 2001); továbbá a Dechter-től (Dechter, 1992) és Mackworthtől (Mackworth, 1992) származó enciklopédiacikkek. Pearson és Jeavons (Pearson és Jeavons, 1997) a könnyen kezelhető CSP-osztályokat veszik számba, beleértve mind a strukturális dekompozíciós módszereket, mind a maguknak a tartományoknak vagy a kényszereknek a tulajdonságaira támaszkodó módszereket. Kondrak és Van Beek (Kondrak és Van Beek, 1997) a visszalépéses keresési algoritmusok analitikus áttekintését adják, Bacchus és Van Run (Bacchus és Van Run, 1998) pedig empirikusabb képet festenek. Tsang (Tsang, 1993), valamint Marriott és Stuckey (Marriott és Stuckey, 1998) szövegei jóval mélyebbre hatolnak a témában, mint azt a fejezet korlátai számunkra lehetővé tették. Sok érdekes alkalmazást mutat be a Freuder és Mackworth szerkesztésében megjelent gyűjtemény (Freuder és Mackworth, 1994). Kényszerkielégítéssel foglalkozó cikkek rendszeresen jelennek meg az Artificial Intelligence-ben és egy specialistáknak szóló újságban, a Constraintsben. A legfőbb konferenciakiadvány az International Conference on Principles and Practice of Constraint Programming, amit gyakran CP-nek hívnak.

5.5.2. Feladatok

5.1.

Fogalmazza meg a saját szavaival a kényszerkielégítési problémák, a kényszerek, a visszalépéses keresés, az élkonzisztencia, a visszaugrás és a min-konfliktusok definícióját.

5.2.

Hány megoldása van az 5.1. ábra térképszínezési problémájának?

5.3.

Magyarázza el, miért jó heurisztika a leginkább korlátozott változót és a legkevésbé korlátozott értéket választani a kényszerkielégítési probléma megoldásának keresése közben.

5.4.

Tekintsük a keresztrejtvények készítésének (nem megoldásának) problémáját:[52] szavakat kell illeszteni egy négyszögletes rácsba. A rács, amely része a probléma specifikációjának, megadja, hogy mely négyzetek legyenek üresek és melyek sötétek. Tegyük fel, hogy adott a szavak egy listája (például egy szótár), és az a feladat, hogy az üres négyzeteket a lista tetszőleges részhalmazát használva kitöltsük. Fogalmazza meg pontosan ezt a problémát kétféle módon:

  1. Mint általános keresési problémát. Válasszon egy megfelelő keresési algoritmust, és specifikálja a heurisztikus függvényt (amennyiben elképzelése szerint szüksége van rá). A fehér kockákba egyszerre egy betűt vagy egész szavakat érdemes-e beírni?

  2. Mint kényszerkielégítési problémát. A változók betűk vagy szavak legyenek? Melyik megfogalmazást tartja jobbnak? Miért?

5.5.

Adjon precíz megfogalmazást az alábbiakra mint kényszerkielégítési problémákra:

  1. Négyszögletes kirakó: találjon nemátfedő helyeket egy nagy négyszögben kisebb négyszögek számára.

  2. Órarend-ütemezés: adott számú professzor és terem van, valamint rögzített az órarendi órák listája is a lehetséges időablakokkal együtt. Mindegyik professzorhoz adott az általa tartott órák halmaza.

5.6.

Oldja meg az 5.2. ábra betűrejtvényét kézzel, visszalépéses kereséssel, előrenéző ellenőrzéssel, valamint az MRV-, illetve a legkevésbé korlátozó érték heurisztikával.

5.7.

Az 5.5. ábra a különböző algoritmusokat az n-királynő problémán teszteli. Próbálja meg ugyanezt egy véletlenszerűen generált térképszínezési problémával is: osszon el az egységsíkon véletlenszerűen n pontot, válasszon ki véletlenszerűen egy X pontot, kösse X-et a legközelebbi olyan Y ponthoz, amelyikkel X még nincs összekötve, és a vonal semelyik más vonalat nem metsz; ismételje a fenti lépést mindaddig, amíg újabb összeköttetés már nem lehetséges. Számítsa ki a teljesítménytáblázatot a legnagyobb n-re, amire csak tudja (mind d = 3-at mind, d = 4-et használva). Fűzzön magyarázatokat a kapott eredményhez.

5.8.

Az AC-3 algoritmus felhasználásával mutassa meg, hogy az élkonzisztencia alkalmas arra, hogy kimutassa az 5.1. ábra {NyA = vörös, V = kék} parciális hozzárendelésének inkonzisztenciáját.

5.9.

Mi a fastruktúrájú kényszerkielégítési problémán futtatott AC-3 legrosszabb esetbeli komplexitása?

5.10.

Az AC-3 visszarak a sorba minden (Xk, Xi) élet, amikor Xi tartományából bármely értéket töröltek, akkor is, ha Xk minden értéke konzisztens Xi több fennmaradó értékével. Tegyük fel, hogy minden egyes (Xk, Xi) élhez nyilvántartjuk a fennmaradó Xi értékek számát, amelyek az Xk minden egyes értékével konzisztensek. Magyarázza el, hogyan lehet hatékonyan frissíteni ezeket az értékeket, és hogyan lehet ennek segítségével az élkonzisztenciát O(n2d2) lépésben elérni.

5.11.

Mutassa meg, hogy egy ternáris kényszer, mint például az „A + B = C” egy segédváltozó bevezetésével három bináris kényszerré alakítható. Feltételezheti, hogy a tartományok végesek. (Segítség: gondoljon egy olyan új változóra, amelynek értékei más értékekből álló párok, és gondoljon olyan kényszerekre, mint „X az első eleme az Y párnak”.) Ezután mutassa meg, hogyan lehet hasonlóan kezelni a háromnál több változót tartalmazó kényszereket. Végül mutassa meg, miként lehet kiküszöbölni az unáris kényszereket a változók tartományának megváltoztatásával. Ez teljessé teszi annak bizonyítását, hogy bármely CSP átalakítható olyan problémákká, melyek csak bináris kényszereket tartalmazhatnak.

5.12.

Olvasnivaló. Tegyük fel, hogy ismerjük egy gráfról, hogy van egy legfeljebb k csomópontot tartalmazó ciklikusság-vágóhalmaza. Írjon le n változós CSP-k esetén egy egyszerű algoritmust a minimális ciklikusság-vágóhalmaz megkeresésére, ahol a futási idő maximuma O(nk). Végezzen irodalomkutatást olyan vágóhalmaz-keresési eljárások után, amelyek a vágóhalmaz méretében közelítőleg polinomiális időben találnak közelítőleg minimális ciklikusság-vágóhalmazt. Praktikussá teszi az ilyen módszerek létezése a ciklikusság-vágóhalmaz módszereket?

5.13.

Tekintsük a következő logikai rejtvényt: Öt különböző színű házban öt különböző nemzetiségű személy él, és mindegyikük más márkájú cigarettát, más italt és más háziállatot szeret. Az alábbi tények alapján a megválaszolandó kérdés a következő: „Hol lakik a zebra, és melyik házban isznak vizet?”

Az angol a vörös házban lakik.

A spanyolnak kutyája van.

A norvég balról az első házban lakik.

A Kools cigarettát a sárga házban szívják.

A Chesterfieldset szívó ember a rókás ház mellett lakik.

A norvég a kék ház mellett lakik.

A Winstont szívó ember kígyókat tart.

A Lucky Strike-ot szívó narancslevet iszik.

Az ukrán teát iszik.

A japán Parliamentset szív.

A Koolsot abban a házban szívják, amely mellett lovat tartanak.

Kávét a zöld házban isznak.

A zöld ház közvetlenül jobbra (Ön felől nézve) van az elefántcsontszínű háztól.

Tejet a középső házban isznak.

Vizsgálja meg a probléma különböző CSP-reprezentációit. Milyen okokból részesítené előnyben az egyiket a másikkal szemben?



[52] Ginsberg és társai (Ginsberg és társai, 1990) több módszert tárgyalnak keresztrejtvények készítésére. Littman és társai pedig a nehezebb problémát, megoldásukat veszik célba (Littman és társai, 1999).