Korlátozott elégedettségi probléma - Constraint satisfaction problem

A kényszer -elégedettségi problémák ( CSP ) olyan matematikai kérdések, amelyek objektumok halmazaként vannak definiálva, amelyek állapotának számos kényszernek vagy korlátozásnak kell megfelelnie . A CSP -k a változókra vonatkozó véges korlátozások homogén gyűjteményeként reprezentálják a problémába tartozó entitásokat, amelyet kényszer -elégedettségi módszerekkel oldanak meg . CSP a kutatási téma mind a mesterséges intelligencia és az operációkutatás , hiszen a rendszeresség azok kialakításába közös alapot a problémák elemzésére és megoldására számos látszólag független a családok. A CSP -k gyakran rendkívül bonyolultak , és heurisztika és kombinatorikus keresési módszerek kombinációját kell ésszerű időn belül megoldani. A kényszerprogramozás (CP) az a kutatási terület, amely kifejezetten az ilyen jellegű problémák kezelésére összpontosít. Továbbá, logikai SAT problémát (SAT), a SAT modulo elméletek (SMT), vegyes egészértékű programozási (MIP) és válasz beállított programozás (ASP) mind kutatási terület összpontosítva felbontása bizonyos formái a kényszer megelégedésére probléma.

Példák a kényszer -elégedettségi problémaként modellezhető problémákra:

Írja be a következtetést
Nyolc királynő puzzle
Térképszínezési probléma
Sudoku , keresztrejtvények , Futoshiki , Kakuro (keresztösszegek), Numbrix , Hidato és sok más logikai rejtvény

Ezeket gyakran CP , ASP, Boolean SAT és SMT megoldók oktatóanyagaival látják el. Általában a kényszerproblémák sokkal nehezebbek lehetnek, és előfordulhat, hogy ezek az egyszerűbb rendszerek némelyikében nem fejezhetők ki. A "valós élet" példái közé tartozik az automatizált tervezés , a lexikai egyértelműsítés , a zenetudomány , a termékkonfiguráció és az erőforrás -allokáció .

A CSP megoldásának létezése döntési problémának tekinthető . Ezt úgy lehet eldönteni, hogy megtaláljuk a megoldást, vagy nem találunk megoldást a kimerítő keresés után (a sztochasztikus algoritmusok általában soha nem jutnak kimerítő következtetésre, míg az irányított keresések gyakran megteszik a kellően kis problémákat). Bizonyos esetekben ismert, hogy a CSP -nek előzetesen vannak megoldásai, más matematikai következtetési folyamat révén.

Formális meghatározás

Formálisan a kényszer -elégedettségi problémát hármasként határozzák meg , ahol ${\ displaystyle \ langle X, D, C \ rangle}$

${\ displaystyle X = \ {X_ {1}, \ ldots, X_ {n} \}}$ változók halmaza,
${\ displaystyle D = \ {D_ {1}, \ ldots, D_ {n} \}}$ a megfelelő értéktartományok halmaza, és
${\ displaystyle C = \ {C_ {1}, \ ldots, C_ {m} \}}$ korlátok halmaza.

Minden változó felveheti az értékeket a nem üres tartományban . Minden kényszer viszont egy pár , ahol a változók egy részhalmaza és egy -aráris reláció a tartományok megfelelő részhalmazán . A változók értékelése a változók egy részhalmazától a tartományok megfelelő részhalmazának egy adott értékkészletéhez tartozó függvény. Az értékelés kielégíti a korlátozást, ha a változókhoz rendelt értékek kielégítik a relációt . ${\ displaystyle X_ {i}}$ ${\ displaystyle D_ {i}}$ ${\ displaystyle C_ {j} \ in C}$ ${\ displaystyle \ langle t_ {j}, R_ {j} \ rangle}$ ${\ displaystyle t_ {j} \ X részhalmaz}$ ${\ displaystyle k}$ ${\ displaystyle R_ {j}}$ ${\ displaystyle k}$ ${\ displaystyle D_ {j}}$ ${\ displaystyle v}$ ${\ displaystyle \ langle t_ {j}, R_ {j} \ rangle}$ ${\ displaystyle t_ {j}}$ ${\ displaystyle R_ {j}}$

Az értékelés következetes, ha nem sérti a korlátozásokat. Az értékelés akkor teljes, ha minden változót tartalmaz. Az értékelés akkor megoldás, ha következetes és teljes; egy ilyen értékelésről azt mondják, hogy megoldja a kényszer -elégedettség problémáját.

Megoldás

A korlátozott elégedettségi problémákat véges tartományokon általában keresési formával oldják meg . A leggyakrabban használt technikák a visszalépés , a kényszer terjedése és a helyi keresés változatai . Ezeket a technikákat is gyakran kombinálják, mint a VLNS módszerben, és a jelenlegi kutatás más technológiákat is magában foglal, például a lineáris programozást .

A visszalépés egy rekurzív algoritmus. Fenntartja a változók részleges hozzárendelését. Kezdetben minden változó nincs hozzárendelve. Minden lépésnél egy változót választanak ki, és az összes lehetséges értéket hozzárendelik. Minden értéknél ellenőrzik a részleges hozzárendelés összhangját a megszorításokkal; következetesség esetén rekurzív hívást hajtanak végre. Ha minden értéket kipróbáltunk, az algoritmus visszalép. Ebben az alapvető visszalépési algoritmusban a következetességet úgy határozzák meg, mint minden olyan kényszer kielégítését, amelynek minden változója hozzá van rendelve. A visszalépésnek több változata létezik. A visszajelzés javítja a konzisztencia ellenőrzésének hatékonyságát. A visszalépés lehetővé teszi a keresés egy részének mentését azáltal, hogy bizonyos esetekben "több változót" visszalép. A korlátozó tanulás következtetéseket von le és menti azokat, amelyek később felhasználhatók a keresés egy részének elkerülésére. Az előretekintést gyakran használják a visszalépésben is, hogy megpróbálják előre látni a változó vagy érték kiválasztásának hatásait, így néha előre meghatározzák, hogy egy alprobléma kielégíthető vagy nem kielégítő.

A kényszer terjedési technikák a korlátozások elégedettségi problémájának módosítására használt módszerek. Pontosabban olyan módszerekről van szó, amelyek kikényszerítik a helyi konzisztencia egy formáját , amelyek a változók és/vagy korlátozások egy csoportjának konzisztenciájához kapcsolódó feltételek. A kényszer terjedésének különféle felhasználási lehetőségei vannak. Először is, egy problémát egyenértékűvé változtat, de általában egyszerűbb megoldani. Másodszor, ez bizonyíthatja a problémák kielégíthetőségét vagy kielégíthetetlenségét. Ez általában nem garantált; ez azonban mindig előfordul a korlátozások terjedésének bizonyos formái és/vagy bizonyos típusú problémák esetén. A lokális konzisztencia legismertebb és leggyakrabban használt formái az ívkonzisztencia , a hiperív-konzisztencia és az útvonal-konzisztencia . A legnépszerűbb korlátozási terjedési módszer az AC-3 algoritmus , amely kikényszeríti az ív konzisztenciáját.

A helyi keresési módszerek hiányos kielégítési algoritmusok. Találhatnak megoldást egy problémára, de akkor is kudarcot vallhatnak, ha a probléma kielégíthető. Úgy dolgoznak, hogy iteratíven javítják a teljes hozzárendelést a változókhoz képest. Minden lépésben kis számú változó értékét változtatják meg, azzal a céllal, hogy növeljék az ezzel a hozzárendeléssel elégedett korlátozások számát. A min-konfliktus algoritmus egy helyi keresési algoritmus, amely a CSP-kre jellemző, és ezen az elven alapul. A gyakorlatban úgy tűnik, hogy a helyi keresés jól működik, ha ezeket a változásokat véletlenszerű döntések is befolyásolják. Kidolgozták a keresés integrálását a helyi kereséssel, ami hibrid algoritmusokhoz vezetett .

Elméleti szempontok

Döntési problémák

A CSP -ket a számítási komplexitáselméletben és a véges modellelméletben is tanulmányozzák . Fontos kérdés, hogy minden relációhalmaz esetében az összes CSP-k halmaza, amely csak az adott halmazból választott relációk használatával ábrázolható, P vagy NP-teljes . Ha egy ilyen dichotómia- tétel igaz, akkor a CSP-k az NP egyik legnagyobb ismert részhalmazát tartalmazzák, amely elkerüli az NP-köztes problémákat, amelynek létezését Ladner-tétel bizonyította, feltételezve, hogy P ≠ NP . Schaefer dichotómia tétele kezeli azt az esetet, amikor minden rendelkezésre álló reláció Boole -operátor , azaz a 2. tartományméret esetében.

A CSP-k legtöbb osztálya, amelyekről ismert, hogy kezelhetők, azok, amelyekben a korlátozások hipergráfja korlátozza a fa szélességét (és nincsenek korlátozások a korlátozási kapcsolatok halmazára), vagy ahol a korlátozások tetszőleges formájúak, de lényegében nem egységes polimorfizmusok léteznek a kényszerviszonyok halmaza.

Minden CSP konjunktív lekérdezés -korlátozási problémának is tekinthető .

Funkciós problémák

Hasonló a helyzet az FP és a #P funkcionális osztályok között . Ladner tételének általánosításával sem az FP, sem a #P-teljes probléma nem áll fenn , amíg az FP ≠ #P. A döntési esethez hasonlóan a #CSP problémáját egy relációhalmaz határozza meg. Minden feladat egy Boole -képletet használ bemenetként, és a feladat az, hogy kiszámítsa a kielégítő feladatok számát. Ez tovább általánosítható nagyobb tartományméret használatával, és minden kielégítő hozzárendeléshez súlyt helyezve, és kiszámítva e súlyok összegét. Ismeretes, hogy minden összetett súlyozott #CSP probléma vagy FP vagy #P-hard.

Változatok

A kényszer -elégedettségi probléma klasszikus modellje statikus, rugalmatlan kényszerek modelljét határozza meg. Ez a merev modell olyan hiányosság, amely megnehezíti a problémák egyszerű megjelenítését. A CSP alapvető meghatározásának számos módosítását javasolták, hogy a modellt sokféle problémához igazítsák.

Dinamikus CSP -k

A dinamikus CSP -k ( DCSP -k) akkor hasznosak, ha a probléma eredeti megfogalmazása valamilyen módon megváltozik, általában azért, mert a figyelembe veendő korlátozások a környezet miatt alakulnak ki. A DCSP -ket statikus CSP -k sorozatának tekintik, amelyek mindegyike az előző átalakítása, amelyben változókat és korlátozásokat lehet hozzáadni (korlátozás) vagy eltávolítani (relaxáció). A probléma kezdeti megfogalmazásaiban található információk felhasználhatók a következők finomítására. A megoldási módszer az információ továbbításának módja szerint osztályozható:

Orákulumok: a sorrendben korábbi CSP -k számára talált megoldást heurisztikaként használják az aktuális CSP felbontásának irányításához.
Helyi javítás: minden CSP kiszámítása az előző részleges megoldásából indul ki, és az inkonzisztens korlátozások helyi kereséssel történő kijavításával kezdődik .
Korlátozás rögzítése: a keresés minden szakaszában új korlátozásokat határoznak meg, amelyek a következetlen döntések csoportjának tanulását képviselik. Ezeket a korlátokat átviszik az új CSP -problémákba.

Rugalmas CSP -k

A klasszikus CSP -k keményen kezelik a korlátozásokat, ami azt jelenti, hogy elengedhetetlenek (mindegyik megoldásnak mindegyiknek meg kell felelnie) és rugalmatlanok (abban az értelemben, hogy teljesen elégedetteknek kell lenniük, különben teljesen megsértik őket). A rugalmas CSP -k lazítják ezeket a feltételezéseket, részben enyhítve a korlátokat, és lehetővé téve, hogy a megoldás ne feleljen meg mindegyiknek. Ez hasonló a preferencia alapú tervezés preferenciáihoz . A rugalmas CSP -k bizonyos típusai a következők:

MAX-CSP, ahol számos kényszer megsértése megengedett, és a megoldás minőségét az elégedett korlátozások száma méri.
Súlyozott CSP , egy MAX-CSP, amelyben egy korlátozás minden megsértését egy előre meghatározott preferencia szerint súlyozzák. Így előnyös a kényszer kielégítése nagyobb súllyal.
A homályos CSP -modell kötöttségek, mint fuzzy relációk, amelyekben a kényszer kielégítése a változók értékeinek folyamatos függvénye, a teljesen elégedettről a teljesen megsértettre.

Decentralizált CSP -k

A DCSP -kben minden kényszerváltozó külön földrajzi hellyel rendelkezik. A változók közötti információcserére erős korlátok vonatkoznak, amelyek megkövetelik a teljesen elosztott algoritmusok használatát a korlátozási elégedettség problémájának megoldásához.

Lásd még

Hivatkozások

További irodalom

Gyors bevezetés a korlátozó elégedettséghez a YouTube -on
Steven Minton; Andy Philips; Mark D. Johnston; Philip Laird (1993). "Konfliktusok minimalizálása: heurisztikus javítási módszer a kényszer-elégedettség és az ütemezési problémák megoldására". Journal of Artificial Intelligence Research . 58. (1–3): 161–205. CiteSeerX 10.1.1.308.6637 . doi : 10.1016/0004-3702 (92) 90007-k .
Tsang, Edward (1993). A kényszer -elégedettség alapjai . Academic Press. ISBN 0-12-701610-4
Chen, Hubie (2009. december). "A logika, a komplexitás és az algebra bemutatkozása". ACM Computing Surveys . 42. (1): 1–32. arXiv : cs/0611018 . doi : 10.1145/1592451.1592453 . S2CID 11975818 .
Dechter, Rina (2003). Kényszerfeldolgozás . Morgan Kaufmann. ISBN 1-55860-890-7
Apt, Krzysztof (2003). A kényszerprogramozás elvei . Cambridge University Press. ISBN 0-521-82583-0
Lecoutre, Christophe (2009). Kényszerhálózatok: technikák és algoritmusok . ISTE/Wiley. ISBN 978-1-84821-106-3
Tomás Feder, Kényszer -elégedettség: személyes perspektíva , kézirat.
Kényszerarchívum
Kényszerített kielégíthető CSP -referenciaértékek az RB modellhez
Referenciaértékek - CSP -példányok XML -reprezentációja
XCSP3-XML-alapú formátum, amelyet CSP-példányok ábrázolására terveztek
Kényszer terjedése - Guido Tack értekezése, amely jó áttekintést nyújt az elméletről és a megvalósításról

Languages

In other projects