5.4. A problémák struktúrája
Ebben az alfejezetben azt vizsgáljuk meg, miként lehet a probléma struktúráját, ahogy azt a kényszergráf megmutatja, felhasználni a megoldások gyors keresésére. Az itt tárgyalt megközelítések java része nagyon általános és a kényszerkielégítési problémákon kívül más eseteknél is alkalmazható, például a valószínűségi következtetésnél. Végül is a részproblémákká történő dekompozíció az egyetlen mód, mellyel remélhetjük, hogy megbirkózhatunk a valósvilág-beli problémákkal. Ismét ránézve az 5.1. (b) ábrára, miközben a probléma struktúráját keressük, egy tény ötlik a szemünkbe ki: Tasmania nincs összeköttetésben a nagy szárazfölddel.[50] Napnál világosabb, hogy Tasmania színezése és a szárazföld színezése független részproblémák (independent subproblems): a szárazföld színezésének bármely megoldása és Tasmania színezésének bármely megoldása kombinálva egyben a teljes térkép színezésének is megoldása lesz. A függetlenségről könnyű megbizonyosodni a kényszergráf összefüggő komponenseit (connected components) vizsgálva. Mindegyik komponens egy CSPi részproblémának felel meg. Ha az Si hozzárendelés egy megoldás a CSPi részproblémára, akkor az ∪i Si hozzárendelés megoldása lesz az ∪i CSPi-nek. Miért fontos ez? Gondoljunk bele a következőbe: tegyük fel, hogy minden egyes CSPi-nek c változója van az n-ből, ahol c konstans. Ekkor n/c részproblémánk van, amelyek mindegyike legfeljebb dc komplexitású. Tehát a teljes komplexitás O(dcn/c), ami lineáris n-ben, míg dekompozíció nélkül O(dn), ami exponenciális n-ben. Tegyük ezt még konkrétabbá: egy n = 80-nal jellemzett Boole CSP-t négy részproblémává osztva (c = 20) a megoldás futási idejét a legrosszabb esetben is az univerzum élethosszáról a másodperc törtrészére rövidítjük le.
Fontos
A teljesen független részproblémák ínyencfalatok, de ritkák. A legtöbb esetben a kényszerkielégítési problémák részproblémái kapcsolatban vannak egymással. A legegyszerűbb eset az, amikor a kényszergráf egy fát alkot: bármely két változót legfeljebb egy út köt össze. Az 5.10. (a) ábra egy sematikus példát mutat erre.[51] Meg fogjuk mutatni, hogy bármely fastruktúrájú kényszerkielégítési probléma megoldható a változók száma szerinti lineáris időben. Az algoritmusnak a következő lépései vannak:
-
Válasszuk ki bármelyik változót a fa gyökércsomópontjául, és rendezzük a többi változót a gyökértől a levelekig úgy, hogy mindegyik csomópontot a sorrendezésben megelőzzön a szülője (lásd 5.10. (b) ábra). Címkézzük ezeket a változókat sorban X1, …, Xn-nel. Most, a gyökércsomópontot leszámítva, mindegyik változónak pontosan egy szülője van.
-
Alkalmazzuk az élkonzisztenciát (Xi, Xj)-re, ahol Xi szülője Xj-nek (j pedig fusson visszafelé n-től 2-ig), és szükség esetén vegyünk ki értékeket a
TARTOMÁNY[ Xi]-ből. -
Adjunk Xj-nek bármilyen, Xi hozzárendelt értékével konzisztens értéket ahol Xi szülője Xj-nek, és j 1-től n-ig halad.
5.10. ábra - (a) Egy faszerkezetű kényszerkielégítési probléma kényszergráfja. (b) Az A csomópont gyökérnek tekintésével konzisztens változók egy lineáris rendezése.
Két dolog érdemes említésre. Egyrészt a 2. lépés után a kényszerkielégítési probléma irány szerint élkonzisztens, tehát a 3. lépés hozzárendeléseiben nincsen szükség visszalépésre (lásd a k-konzisztencia tárgyalását a „A kényszerek terjesztése” részben). Másrészt, miután a 2. lépésben fordított sorrendben alkalmaztuk az élkonzisztencia-ellenőrzéseket, elértük az algoritmussal, hogy a törölt értékek ne veszélyeztessék a már feldolgozott élek konzisztenciáját. A teljes algoritmus O(nd2) időben fut.
Most, hogy fákra már van egy hatékony algoritmusunk, megvizsgálhatjuk, miként lehet az általánosabb kényszergráfokat valahogyan fákra visszavezetni. Alapvetően két mód van erre: az egyik a csomópontok eltávolításán, a másik a csomópontok összevonásán alapul.
Az első megközelítés úgy jár el, hogy néhány változónak értéket ad, a maradékok pedig fát fognak alkotni. Vegyük ismét az 5.11. (a) ábrán látható kényszergráfot az Ausztrália-példához. Ha törölni tudnánk Dél-Ausztráliát, akkor a gráf fává válhatna (ahogy az ábra (b) részén látható). Szerencsére meg tudjuk tenni ezt (a gráfban, nem a kontinensen) azzal, hogy DA értékét rögzítjük, és a többi változó tartományából töröljük azokat az értéket, melyek inkonzisztensek a DA számára választottal.
Most tehát hogy mind DA-t, mind a rá vonatkozó kényszereket eltávolítottuk, a kényszerkielégítési probléma bármely megoldása konzisztens lesz a DA számára választott értékkel. (Ez bináris kényszerkielégítési problémák esetén működik; a helyzet jóval bonyolultabb magasabb rendű kényszerek esetén.) Tehát a keletkező fa a fenti algoritmussal megoldható, és így az egész problémát is megoldottuk. Általános esetben persze (nem úgy, mint a térképszínezésnél) a DA számára választott érték lehet rossz is, és ekkor egyesével végig kell próbálgatni őket. Az általános algoritmus az alábbi:
-
Válasszunk ki egy S részhalmazt a
VÁLTOZÓK[csp]-ből úgy, hogy a kényszergráf S eltávolítása után fa legyen. S-et ciklikusság-vágóhalmaznak (cycle cutset) nevezzük. -
S minden egyes változójának minden egyes, az S-re vonatkozó összes kényszert kielégítő lehetséges hozzárendelésére:
-
vegyük ki a fennmaradó változók tartományaiból az S számára választott hozzárendeléssel inkonzisztens értékeket, és
-
ha a fennmaradó kényszerkielégítési problémának van megoldása, akkor adjuk vissza ezt az S hozzárendelésével együtt.
-
Ha a ciklikusság-vágóhalmaz mérete c, akkor a teljes futási idő O(dc · (n – c)d2) lesz. Ha a gráf „közel fa”, akkor c kicsi lesz, a megtakarítás pedig tetemes a gondolkodás nélküli visszalépéses megoldáshoz képest. A legrosszabb esetben azonban c akár (n – 2) méretű is lehet. A legkisebb ciklikusság-vágóhalmaz megtalálása NP-nehéz probléma, de sok hatékony algoritmust ismerünk erre a feladatra. Az általános algoritmikus megközelítés a vágóhalmaz-kondicionálás (cutset conditioning); még találkozni fogunk ezzel a 14. fejezetben, ahol a valószínűségekről történő következtetésekhez használjuk.
5.11. ábra - (a) Az 5.1. ábrán szereplő eredeti kényszergráf. (b) A kényszergráf DA eltávolítását követően.
A második megközelítés a kényszergráf több, egymással kapcsolatban lévő részproblémából álló fadekompozíció (tree decomposition) előállításán alapul. Mindegyik részproblémát függetlenül oldjuk meg, és a keletkező megoldásokat összekapcsoljuk. A legtöbb „oszd meg és uralkodj” típusú megközelítéshez hasonlóan ez is akkor működik, ha egyik részprobléma sem túl nagy. Egy fadekompozíciónak az alábbi követelményeket kell kielégítenie:
-
Az eredeti probléma mindegyik változója szerepeljen a részproblémák legalább egyikében.
-
Ha bármely két változót az eredeti problémában egy kényszer köt össze, akkor a részproblémák legalább egyikében együtt is elő kell fordulniuk (és természetesen a kényszernek is).
-
Ha egy változó a fa két részproblémájában is előfordul, akkor a változónak az ezeket a részproblémákat összekötő út minden részproblémájában is elő kell fordulnia.
Az első két kikötés biztosítja, hogy az összes változó és kényszer előforduljon a dekompozícióban. A harmadik kikötés eléggé technikai ízűnek tűnik, de egyszerűen csak arról szól, hogy bármely adott változónak ugyanazzal az értékkel kell rendelkeznie az összes részproblémában, ahol előfordul – a részproblémákat a fában összekötő élek kényszerítik ezt ki. Például DA az 5.12. ábra mindegyik összekötött részproblémájában előfordul. Az olvasó az 5.11. ábra alapján igazolhatja, hogy van értelme ennek a dekompozíciónak.
Külön-külön megoldhatjuk az egyes részproblémákat, és ha bármelyiknek is nincs megoldása, akkor az egész problémának nincs. Ha az összes részproblémát meg tudjuk oldani, akkor a következők szerint megpróbálhatunk összeállítani egy globális megoldást. Először is tekintsünk minden egyes változót egy „megaváltozónak”, amelynek tartománya a részprobléma összes megoldásának halmaza. Például az 5.12. ábra bal szélső részproblémája az a térképszínezési probléma, amelynek három változója és – ezek szerint – hat megoldása van (ezek egyike az {NyA = vörös, DA = kék, ÚT = zöld}). Ezután a részproblémákat összekötő kényszereket meg tudjuk oldani a fákra adott fent bemutatott hatékony algoritmussal. A részproblémák közti kényszerek egyszerűen csak azért vannak, hogy a részproblémák megoldásai megegyezzenek az osztott változókban. Például, ha adott az {NyA = vörös, DA = kék, ÚT = zöld} megoldás az első részproblémára, akkor a következő részprobléma egyetlen konzisztens megoldása a {DA = kék, ÚT = zöld, Q = vörös} lehet.
Fontos
Egy adott kényszergráfnak több dekompozíciója is lehetséges; a dekompozíció kiválasztásakor az a cél, hogy a részproblémák a lehető legkisebbek legyenek. Egy gráf fadekompozíciójának faszélessége (tree width) eggyel kisebb, mint a legnagyobb részprobléma mérete; magának a gráfnak a faszélessége pedig definíció szerint a legkisebb faszélesség az összes fadekompozíciója között. Ha egy gráfnak w a faszélessége, és adott a megfelelő fadekompozíció, akkor a problémát meg lehet oldani O(ndw+1) időben. Tehát egy felülről korlátos faszélességű kényszergráffal rendelkező kényszerkielégítési probléma polinomiális időben megoldható. Sajnálatos módon egy minimális faszélességű fadekompozíció megtalálása NP-nehéz probléma, de vannak olyan heurisztikus módszerek, amelyek jól működnek a gyakorlatban.
[50] Egy nagyon gondos térképész vagy egy tasmaniai patrióta ellenvethetné, hogy Tasmaniát nem lehet ugyanolyan színnel színezni, mint a legközelebbi szárazföldi szomszédját, nehogy úgy tűnjön, mintha annak az államnak a része lenne.
[51] Sajnos nagyon kevés olyan területe van a világnak (talán Celebesz ilyen), amelynek faszerkezetű térképe van. (Celebesz egy közelítőleg csillagstruktúrájú sziget Közép-Indonéziában – A ford.)
