Problema satisfacției constrângerii

Multe probleme în contextul „ Inteligenței artificiale pot fi clasificate ca probleme Îndeplinirea constrângerilor (Constraint Satisfaction Problem sau CSP); printre acestea cităm probleme de complexitate combinatorie , alocarea resurselor, planificare și raționament temporal. Aceste probleme pot fi rezolvate eficient prin tehnici bine cunoscute de rezolvare a CSP.

Definiție formală

În mod formal, un CSP poate fi definit pe un set finit de variabile $(X_{1},X_{2},\dots ,X_{n})$ ${\ displaystyle (X_ {1}, X_ {2}, \ dots, X_ {n})}$ $(X_ {1}, X_ {2}, \ dots, X_ {n})$ ale căror valori aparțin unor domenii finite de definiție $(D_{1},D_{2},\dots ,D_{n})$ ${\ displaystyle (D_ {1}, D_ {2}, \ dots, D_ {n})}$ $(D_ {1}, D_ {2}, \ dots, D_ {n})$ și pe un set de constrângeri (constrângeri) $(C_{1},C_{2},\dots ,C_{n})$ ${\ displaystyle (C_ {1}, C_ {2}, \ dots, C_ {n})}$ $(C_ {1}, C_ {2}, \ dots, C_ {n})$ . O constrângere asupra unui set de variabile este o restricție asupra valorilor pe care variabilele le pot lua simultan. Conceptual, o constrângere poate fi văzută ca un set care conține toate valorile pe care variabilele le pot asuma în același timp: o constrângere între k variabile $C(X_{i_{1}},X_{i_{2}},\dots ,X_{i_{k}})$ ${\ displaystyle C (X_ {i_ {1}}, X_ {i_ {2}}, \ dots, X_ {i_ {k}})}$ $C (X _ {{i_ {1}}}, X _ {{i_ {2}}}, \ dots, X _ {{i_ {k}}})$ este un subset al produsului cartezian al domeniilor variabilelor implicate $D_{i_{1}},D_{i_{2}},\dots ,D_{i_{k}}$ ${\ displaystyle D_ {i_ {1}}, D_ {i_ {2}}, \ dots, D_ {i_ {k}}}$ $D _ {{i_ {1}}}, D _ {{i_ {2}}}, \ dots, D _ {{i_ {k}}}$ care specifică ce valori ale variabilelor sunt compatibile cu celelalte. Acest set poate fi reprezentat în multe moduri, de exemplu prin intermediul matricilor , ecuațiilor, inegalităților sau relațiilor . Gradul variabilei este definit ca numărul de constrângeri la care este supusă.

O problemă de satisfacție a constrângerii presupune o atribuire inițială , adică un set de variabile deja constrânse. Alocarea inițială poate fi, de asemenea, goală. Soluția la problemă continuă prin extinderea atribuirii inițiale, adică prin atribuirea treptată a valorilor variabilelor care sunt încă libere. Soluția unui CSP este o atribuire completă și consecventă a valorilor variabilelor (adică o atribuire care satisface toate constrângerile și nu lasă variabile libere), obținută prin extinderea atribuirii inițiale. ^[1]

Exemple

Problema celor opt regine

Un exemplu clasic de problemă care poate fi văzut ca un CSP este puzzle- ul Eight Queens . Problema constă în plasarea a opt regine pe o tablă de șah care nu se atacă reciproc; desigur, nu este posibil să aveți mai mult de opt, deoarece acest lucru ar presupune plasarea a două pe același rând. Pentru a formaliza problema ca CSP, trebuie să identificăm un set de variabile, un set de domenii și un set de constrângeri. Deoarece exact o regină trebuie așezată pe fiecare rând și pe fiecare coloană a tabloului de șah, o posibilă formalizare a problemei este să considerăm fiecare dintre cele opt rânduri ale tabloului de șah ca variabile; setul de variabile va fi deci $X=\{R_{1},R_{2},\dots ,R_{8}\}$ ${\ displaystyle X = \ {R_ {1}, R_ {2}, \ dots, R_ {8} \}}$ $X = \ {R_ {1}, R_ {2}, \ dots, R_ {8} \}$ . Fiecare dintre aceste variabile poate lua o valoare care reprezintă coloana pe care se află regina corespunzătoare, deci domeniile variabilelor sunt cele opt coloane posibile: $D_{1}=D_{2}=\dots =D_{8}=\{1,2,3,4,5,6,7,8\}$ ${\ displaystyle D_ {1} = D_ {2} = \ dots = D_ {8} = \ {1,2,3,4,5,6,7,8 \}}$ $D_ {1} = D_ {2} = \ dots = D_ {8} = \ {1,2,3,4,5,6,7,8 \}$ . Prin urmare, am inclus deja în această formalizare conceptul că două regine nu pot fi pe aceeași linie; rămâne să impui că două regine nu pot fi pe aceeași coloană sau pe aceeași diagonală. Prin urmare, setul de constrângeri va fi:

$\forall i,j.R_{i}\neq R_{j}$ ${\ displaystyle \ forall i, j.R_ {i} \ neq R_ {j}}$ $\ forall i, j.R_ {i} \ neq R_ {j}$

pentru a indica faptul că două regine nu pot fi pe aceeași coloană și:

$\forall i,j$ ${\ displaystyle \ forall i, j}$ $\ forall i, j$ , de sine $R_{i}=a$ ${\ displaystyle R_ {i} = a}$ $R_ {i} = a$ Și $R_{j}=b$ ${\ displaystyle R_ {j} = b}$ $R_ {j} = b$ , asa de $i-j\neq a-b$ ${\ displaystyle ij \ neq ab}$ $i-j \ neq a-b$ Și $i-j\neq b-a$ ${\ displaystyle ij \ neq ba}$ $i-j \ neq b-a$

să impună că două regine nu pot fi pe aceeași diagonală.

Sudoku

Un alt exemplu clasic este rezolvarea unui puzzle sudoku . În acest caz, variabilele sunt cele 81 de celule ale grilei, domeniul fiecărei variabile sunt numerele de la 1 la 9, iar constrângerile sunt nerespectarea figurilor din rânduri, coloane, sub-grile. În acest caz este dată și o atribuire inițială (numerele deja prezente în grilă) care face ca soluția la schemă să fie unică. ^[1]

Căutați soluția

CSP-urile pot fi rezolvate cu toate mecanismele problemelor de găsire a soluției optime. Algoritmii de căutare pe copaci sunt favorizați de probleme CSP, deoarece de fapt aceste probleme oferă o indicație precisă a adâncimii maxime a soluției în arborele de căutare: a avea $Nu.$ ${\ displaystyle N}$ $Nu.$ variabile libere înseamnă a trebui să efectueze exact $Nu.$ ${\ displaystyle N}$ $Nu.$ sarcini. În special, abordarea utilizată de obicei în rezolvarea CSP implică utilizarea căutării în profunzime ^[1] : acest algoritm este de fapt excelent și complet, deoarece toate soluțiile sunt la aceeași adâncime (și de obicei au același cost) și există fără risc de a rula pe căi infinite, căutarea se termină întotdeauna la nivelul soluției. În plus, cercetarea aprofundată oferă compromisuri bune asupra complexității spațiale și temporale. Un dezavantaj major al problemelor CSP este factorul considerabil de ramificare : la fiecare nivel al arborelui, acest factor este de fapt egal cu numărul de variabile care nu au fost încă atribuite înmulțit cu numărul de valori pe care fiecare variabilă le poate asuma. Această problemă este rezolvată cu mecanismul de backtracking și luând în considerare o singură variabilă și toate atribuțiile sale posibile la fiecare nivel. Pentru a determina ce variabilă trebuie luată în considerare, se utilizează anumite euristici :

Variabilă cu gradul maxim , adică este preferată examinarea variabilelor utilizate în cel mai mare număr de constrângeri.
Numărul minor de valori ale domeniului , utilizat între variabilele selectate de euristica anterioară, se așteaptă să aleagă variabila cu cel mai restrâns domeniu.

Odată selectată variabila, sunt disponibile și euristicile pentru selectarea valorii:

Mai puțină valoare obligatorie , adică selectarea valorii care elimină cel mai mic număr de valori din domeniul variabilelor legate de cea în cauză.

Inferință

Ceea ce diferențiază cel mai mult CSP-urile de problemele normale de căutare este posibilitatea de a face deducții prin exploatarea propagării constrângerilor : în cazul sudoku, de exemplu, dacă un anumit număr este atribuit unei casete, este posibil să se elimine acel număr din toate casete din același rând, coloană și sub-grilă. Acest lucru duce în unele cazuri la posibilitatea de a rezolva probleme întregi fără a fi nevoie să recurgă la algoritmi de căutare, ca în cazul Sudoku. În cazul celor opt regine, pe de altă parte, este preferată o strategie care caută intervale prin inferență: de fiecare dată când unei variabile i se atribuie o valoare, toate valorile care nu mai sunt disponibile sunt eliminate din domeniile variabilelor legate de aceasta, pentru a păstra consistența ori de câte ori se face o alegere.

Algoritmi de rezoluție

Pentru a rezolva problemele de satisfacție a constrângerilor, sunt disponibili mai mulți algoritmi care iau în considerare această particularitate a acestui tip de problemă, împărțită între:

Algoritmi care evaluează constrângerile a posteriori:
- Backtracking
- Salt înapoi
- Marcare înapoi
- DLX (Linkuri de dans)
Algoritmi care evaluează constrângerile a priori
- Verificare înainte
- Privire parțială în față
- Privire completă în față
Algoritmi de inferență
- Verificarea consistenței între două variabile ( consistența arcului );
- Verificarea coerenței, date cu două variabile, pe a treia ( cale-consistență ), sau mai general:
- Verificarea coerenței, date $k-1$ ${\ displaystyle k-1}$ $k-1$ variabile, pe una $k-esima$ ${\ displaystyle k-th}$ $k-th$ variabilă ( k-Consistency ).

Notă

^ ^a ^b ^c Stuart Russell și Peter Norvig, Artificial Intelligence A Modern Approach 2nd Edition, Upper Saddle River, New Jersey, Pearson Education, 2003, ISBN 0-13-080302-2 .

Elemente conexe

[rn-1] Stuart Russell și Peter Norvig, Artificial Intelligence A Modern Approach 2nd Edition, Upper Saddle River, New Jersey, Pearson Education, 2003, ISBN 0-13-080302-2 .

[1]