Satisfacția constrângerii

Introducere

Una dintre sarcinile importante ale inteligenței artificiale (AI) este problema satisfacției constrângerilor . Teoria UR oferă un aparat convenabil și o schemă formală simplă pentru reprezentarea și rezolvarea problemelor combinatorii AI.

Scopul rezolvării problemei RO este de a găsi valorile variabilelor care satisfac constrângerile date.

Problema existenței soluțiilor la problema PR este NP-complet .

Strâns legată de teoria RO este programarea prin constrângeri , care este o paradigmă de programare pentru descrierea declarativă și rezolvarea eficientă a problemelor combinatorii. Multe probleme combinatorii clasice, cum ar fi celebra teoremă a lui Fermat , problema de satisfacție (SAT) din logica propozițională, problema de colorare a grafurilor și problema izomorfismului grafului din teoria grafurilor, pot fi formulate ca probleme VR (SLT). Să ne oprim mai în detaliu asupra uneia dintre problemele de lungă durată din matematică - problema colorării unui grafic , un caz special al căruia este binecunoscuta problemă a colorării unei hărți . Formularea problemei de colorare sub forma unei probleme RO atribuie variabile vârfurilor graficului de colorat, culorile posibile sunt domenii (domenii) ale variabilelor, iar constrângerile de inegalitate între vârfurile adiacente sunt constrângerile problemei.

Desigur, aici este imposibil să descriem în detaliu toate aspectele și direcțiile teoriei satisfacerii restricțiilor și programării în restricții, prin urmare, informații și bibliografie mai complete pot fi găsite în monografia tradusă de Russell S., Norvig P., care acoperă problemele SR și în recenzia lui O.A.Șcherbina .

O trecere în revistă a principalelor domenii ale programării constrânse înainte de anul 2000 este oferită de Ushakov și Telerman (2000).

Istorie

Să atingem mai întâi terminologia și istoria apariției metodelor UR. Montanari a sugerat utilizarea modelelor VR pentru a descrie o serie de probleme combinatorii care apar în procesarea imaginilor computerizate și a numit aceste probleme VR „rețele de constrângeri” (rețele de constrângeri). Acest lucru se datorează faptului că sistemul de constrângeri poate fi reprezentat ca un graf nedirecționat cu vârfuri variabile și muchii corespunzătoare constrângerilor dintre două variabile. Potrivit lui Dechter, rețelele de constrângeri sunt o reprezentare grafică folosită pentru a găsi strategii pentru rezolvarea problemelor LR. Destul de repede, această abordare a fost folosită pentru a rezolva o clasă mult mai largă de probleme. Literatura științifică folosește ambii acești termeni rețele de constrângeri și probleme de satisfacție a constrângerilor.

Mai formal, problema satisfacției constrângerilor (CR) este un tuplu , unde este setul de variabile, este setul de domenii de valori variabile și este setul de constrângeri.

Exemple de probleme de satisfacție cu constrângeri

Să dăm o serie de exemple care ilustrează formularea problemelor ER în alte domenii ale matematicii.

Probleme de optimizare și probleme RO

Rezolvarea problemei de optimizare poate fi redusă la rezolvarea unei secvențe de probleme OE după cum urmează. Se găsește o soluție fezabilă, după care se adaugă o constrângere corespunzătoare funcției obiectiv, care exprimă condiția ca valoarea funcției obiectiv să fie mai bună decât pentru această soluție. Ajustările succesive ale acestei valori de prag, făcute până când problema devine de nerezolvat, ne permit să găsim soluția optimă.

Exemplul 1. Cel mai banal exemplu algebric al problemei EC este problema rezolvării unui sistem de ecuații. Dat un sistem de ecuații liniare peste un câmp finit . Are ea o soluție? Este clar că în acest exemplu, fiecare ecuație individuală este o constrângere, cu variabilele ecuației formând un interval, iar mulțimea tuturor tuplurilor corespunzătoare soluțiilor ecuației formând o relație de constrângere.

Exemplul 2. Problema standard de 3-satisfiabilitate propozițională (3-SAT) este definită dând o formulă logică propozițională constând dintr-o conjuncție de clauze, fiecare clauză conținând 3 literali (un literal este o variabilă sau negația sa) și răspunzând la întrebare dacă există valori ale variabilelor care fac formula adevărată. Fie o astfel de formulă, unde sunt clauze . Problema de fezabilitate pentru poate fi exprimată ca o problemă SR , unde este mulțimea tuturor variabilelor din formulă și este mulțimea constrângerilor , unde fiecare constrângere este construită după cum urmează: este lista de variabile incluse în , și constă din toate tupluri care fac clauza adevărată .

Soluțiile la această problemă RO sunt atribuirea de valori variabilelor care fac formula adevărată. Prin urmare, orice problemă de satisfacție 3 poate fi exprimată ca o problemă SR.

Problema RO poate fi, de asemenea, convertită într-o problemă de fezabilitate SAT. Pentru un ZUO dat, construim problema de satisfacție a SAT după cum urmează. Să introducem variabile. Variabilele sunt setate la adevărat dacă și numai dacă valoarea este atribuită variabilei. Pentru fiecare variabilă, se adaugă clauze (disjunctive) pentru toate perechile de valori ale aceleiași variabile pentru a se asigura că variabila nu poate avea două valori diferite în același timp. Se adaugă o clauză pentru a se asigura că variabilei i se atribuie cel puțin o valoare.

Exemplul 3. Orice sarcină specifică a AM poate fi exprimată într-o formă logică. Într-adevăr, folosind corespondența standard dintre relații și predicate, se poate rescrie problema RO ca o formulă de ordinul întâi, unde predicate și înseamnă predicatul aplicat tuplului de variabile. Întrebarea este dacă această formulă este fezabilă. Această sarcină este folosită în mod obișnuit în teoria bazelor de date, deoarece corespunde evaluării unei interogări conjunctive, așa cum se arată în exemplul următor.

Exemplul 4 O bază de date relațională poate fi privită ca un set finit de tabele. Un tabel constă dintr-o schemă și date specifice, unde schema este un set finit de atribute, fiecare atribut având un set corespunzător de valori posibile, numit domeniu. Datele concrete sunt un set finit de rânduri, unde fiecare rând este o mapare care mapează fiecare atribut de schemă la o valoare din domeniul său. O sarcină standard pentru bazele de date relaționale este problema de evaluare a interogărilor conjunctive, care întreabă dacă soluția are o interogare conjunctivă, de exemplu. interogare de forma , unde sunt formule atomice. O interogare conjunctivă asupra unei baze de date relaționale corespunde unui exemplu specific de problemă LR, care se realizează printr-o simplă înlocuire a termenilor: „atributele” sunt înlocuite cu „variabile”, „tabelele” cu „constrângeri”, „schema” cu „ interval”, „date specifice” prin „relație de restricție” și „șiruri” la „tupluri”. Prin urmare, o interogare conjunctivă este echivalentă cu un exemplu specific de sarcină RO ale cărei variabile sunt atribute de interogare. Pentru fiecare formulă atomică din interogare, există o constrângere, astfel încât domeniul de constrângere este o listă de variabile de formulă, iar relația de constrângere este un set de modele.

Literatură