Kényszer elégedettség

Bevezetés

A mesterséges intelligencia (AI) egyik fontos feladata a kényszer - elégedettségi probléma. Az UR-elmélet kényelmes apparátust és egyszerű formális sémát kínál a kombinatorikus AI-problémák ábrázolására és megoldására.

Az RO probléma megoldásának célja, hogy megtaláljuk azon változók értékét, amelyek megfelelnek az adott megszorításoknak.

A PR-probléma megoldásainak meglétének problémája NP-teljes .

Az RO elmélethez szorosan kapcsolódik a kényszerprogramozás , amely a kombinatorikus problémák deklaratív leírásának és hatékony megoldásának programozási paradigmája. Számos klasszikus kombinatorikai probléma, mint például Fermat híres tétele , a propozicionális logikából a kielégíthetőségi probléma (SAT), a gráfszínezési probléma és a gráfelméletből a gráfizomorfizmus probléma megfogalmazható VR problémaként (SLT). Nézzük meg részletesebben a matematika egyik régóta fennálló problémáját - a gráf színezésének problémáját , amelynek speciális esete a térkép színezésének jól ismert problémája . A színezési probléma megfogalmazása RO feladat formájában változókat rendel a színezendő gráf csúcsaihoz, a lehetséges színek a változók tartományai (tartományai), a szomszédos csúcsok közötti egyenlőtlenségi kényszerek pedig a probléma kényszerei.

Természetesen itt nem lehet részletesen leírni a korlátozások kielégítésének elméletének és a korlátozásokban való programozásnak minden aspektusát és irányát, ezért teljesebb információ és bibliográfia található Russell S., Norvig P., lefordított monográfiájában. amely az SR kérdéseivel foglalkozik és O.A. Shcherbina áttekintésében.

Ushakov és Telerman (2000) áttekintést ad a 2000. év előtti korlátozott programozás főbb területeiről.

Történelem

Először érintsük meg az UR-módszerek terminológiáját és kialakulásának történetét. Montanari a VR-modellek használatát javasolta számos, a számítógépes képfeldolgozás során felmerülő kombinatorikus probléma leírására, és ezeket a VR-problémákat "korlátozások hálózatainak" (megszorítások hálózatainak) nevezte. Ez annak köszönhető, hogy a kényszerrendszer egy irányítatlan gráfként ábrázolható, amelynek változó csúcsai és élei megfelelnek a két változó közötti kényszereknek. Dechter szerint a kényszerhálózatok egy gráfábrázolás, amelyet az LR-problémák megoldására szolgáló stratégiák megtalálására használnak. Elég gyorsan ezt a megközelítést használták a problémák sokkal szélesebb osztályának megoldására. A tudományos irodalom mindkét kifejezést használja a kényszerhálózatok és a kényszer-elégedettségi problémák.

Formálisabban a megszorítások kielégítési problémája (CR) egy sor , ahol a változók halmaza, a változó értéktartományok halmaza és a megszorítások halmaza. $P = <X,D,C>$ $x$ $D$ $C$

Példák a korlátok kielégítési problémáira

Adjunk néhány példát a matematika más területein felmerülő ER-problémák megfogalmazására.

Optimalizálási problémák és RO problémák

Az optimalizálási feladat megoldása az alábbiak szerint redukálható az OE feladatok sorozatának megoldására. Találunk egy megvalósítható megoldást, amely után hozzáadunk egy, a célfüggvénynek megfelelő megkötést, amely azt a feltételt fejezi ki, hogy a célfüggvény értéke jobb legyen, mint ennél a megoldásnál. Ennek a küszöbértéknek az egymást követő módosításai, amíg a probléma megoldhatatlanná válik, lehetővé teszik számunkra, hogy megtaláljuk az optimális megoldást.

1. példa Az EC probléma legtriviálisabb algebrai példája az egyenletrendszer megoldásának problémája. Adott egy véges mező feletti lineáris egyenletrendszer . Van megoldása? Nyilvánvaló, hogy ebben a példában minden egyes egyenlet egy megszorítás, az egyenlet változói egy tartományt alkotnak, és az egyenlet megoldásainak megfelelő összes sor egy kényszerrelációt alkot. $F$

2. példa A standard propozicionális 3-kielégíthetőség (3-SAT) problémát úgy határozzuk meg, hogy adunk egy kijelentési logikai formulát, amely tagmondatok konjunkciójából áll, és mindegyik tagmondat 3 literált tartalmaz (a literál egy változó vagy annak tagadása), és megválaszoljuk a kérdést. hogy vannak-e olyan változók értékei, amelyek igazzá teszik a képletet. Legyen egy ilyen képlet, ahol a záradékok . A megvalósíthatósági problémát SR problémaként fejezhetjük ki , ahol a képletben szereplő összes változó halmaza, és a megszorítások halmaza , ahol minden megszorítás a következőképpen épül fel: a változók listája szerepel benne , és mindenből áll sorok, amelyek igazzá teszik a záradékot . $\Phi = {\phi _{\rm{1))} \wedge \ldots \wedge {\phi _n}$ ${\phi _i}$ $\Phi$ $\left( {X,\,\left\{ {0,\,1} \jobbra\},\,C} \jobbra)$ $x$ $C$ $\left\{ {\left( {{s_1},\,{\rho _1}} \right), \ldots ,\,\left( {{s_n},\,{\rho _n}} \right)} \jobb\}$ $\left( {{s_k},\,{\rho _k}} \jobbra)$ ${s_k}$ ${\phi _k}$ ${\rho_k}$ ${\phi _k}$ $\left({k = 1,\, \lpontok ,\,n} \jobb)$

Az RO probléma megoldása olyan változókhoz való értékek hozzárendelése, amelyek igazzá teszik a képletet. Ezért bármely 3-as kielégíthetőségi probléma kifejezhető SR problémaként. $\Phi$

Az RO probléma SAT megvalósíthatósági problémává is konvertálható. Adott ZUO esetén a SAT kielégítési problémát a következőképpen szerkesztjük meg. Vezessünk be változókat. A változók akkor és csak akkor lesznek igazak, ha az érték hozzá van rendelve a változóhoz. Minden változóhoz záradékokat (diszjunktokat) adunk hozzá ugyanannak a változónak minden értékpárjához, hogy biztosítsuk, hogy a változónak ne legyen egyszerre két különböző értéke. Egy záradékot adunk hozzá annak biztosítására, hogy legalább egy érték legyen hozzárendelve a változóhoz.

3. példa : Az IH bármely konkrét feladata logikai formában kifejezhető. Valójában a relációk és predikátumok közötti szabványos megfeleltetést használva az RO problémát átírhatjuk egy elsőrendű formulává, ahol a predikátumok a változók sorára alkalmazott predikátumot jelentik. A kérdés az, hogy ez a képlet megvalósítható-e. Ezt a feladatot gyakran használják az adatbázis-elméletben, mert egy konjunktív lekérdezés kiértékelésének felel meg, amint az a következő példában látható.

4. példa A relációs adatbázist táblák véges halmazaként tekinthetjük meg. A táblázat egy sémából és meghatározott adatokból áll, ahol a séma attribútumok véges halmaza, és mindegyik attribútumnak megfelelő lehetséges értékkészlete van, amelyet tartománynak nevezünk. A konkrét adatok sorok véges halmaza, ahol minden sor egy leképezés, amely az egyes séma attribútumokat a tartományából származó értékre képezi le. A relációs adatbázisok szokásos feladata a konjunktív lekérdezés kiértékelési probléma, amely rákérdez, hogy a megoldásnak van-e konjunktív lekérdezése, pl. a forma lekérdezése, ahol atomi képletek vannak. Egy relációs adatbázison keresztüli konjunktív lekérdezés egy LR probléma konkrét példájának felel meg, amelyet a kifejezések egyszerű cseréjével érünk el: az „attribútumok” helyett a „változók”, a „táblázatok” helyett a „megszorítások”, a „séma” helyett a „ tartomány", "specifikus adatok" a "korlátozási reláció" és "karakterláncok" a "tuples". Ezért a konjunktív lekérdezés egyenértékű egy olyan RO feladat konkrét példájával, amelynek változói lekérdezési attribútumok. A lekérdezésben szereplő minden egyes atomi képlethez van egy megszorítás, így a kényszertartomány a képletváltozók listája, a kényszerreláció pedig modellek halmaza.

Irodalom

Russell S. Mesterséges intelligencia: modern megközelítés. 2. kiadás: Per. angolról. / S. Russell, P. Norvig M.: Williams, 2006. 1408 p.
Shcherbina O.A. Megszorítások kielégítése és kényszerprogramozás // Intelligens rendszerek. 2011. 15. (N 1-4). 53-170
Dechter R. Constraint Processing / R. Dechter. Morgan Kaufmann, 2003. 481 p.
Montanari U. Megszorítások hálózatai: A képfeldolgozás alapvető tulajdonságai és alkalmazásai // Information Sciences. 1974.7.2. P. 95-132.
Ushakov D.M., Telerman V.V. Rendszerek programozása megszorításokban (áttekintés) // Rendszerinformatika: Szo. tudományos tr. Novoszibirszk: Nauka, 2000. 7. szám: Elméleti és módszertani problémák párhuzamos és elosztott rendszerek létrehozásához. 275-310.