Coerența locală - Local consistency

În cazul satisfacției de constrângere , condițiile de consistență locală sunt proprietățile problemelor de satisfacție a constrângerilor legate de consistența subseturilor de variabile sau constrângeri. Acestea pot fi utilizate pentru a reduce spațiul de căutare și pentru a rezolva problema mai ușor. Sunt utilizate câteva tipuri de condiții de consistență locală, inclusiv consistența nodului , consistența arcului și consistența căii .

Fiecare stare de consistență locală poate fi pusă în aplicare printr-o transformare care schimbă problema fără a-și schimba soluțiile. O astfel de transformare se numește propagare de constrângere . Propagarea constrângerilor funcționează prin reducerea domeniilor variabilelor, consolidarea constrângerilor sau crearea de noi. Aceasta duce la reducerea spațiului de căutare, ceea ce face ca problema să fie mai ușor de rezolvat prin unii algoritmi. Propagarea de constrângere poate fi de asemenea folosită ca un verificator de insatisfacție, incompletă în general, dar completă în unele cazuri particulare.

Condițiile de consistență locală pot fi grupate în diferite clase. Condițiile de consistență locale originale impun ca fiecare alocare consistentă să poată fi extinsă în mod constant la o altă variabilă. Consistența direcțională cere ca această condiție să fie satisfăcută doar atunci când cealaltă variabilă este mai mare decât cele din sarcină, conform unei comenzi date. Consistența relațională include extensii la mai mult de o variabilă, dar această extensie este necesară numai pentru a satisface o constrângere sau un set de constrângeri.

Ipoteze

În acest articol, o problemă de satisfacție a constrângerilor este definită ca un set de variabile, un set de domenii și un set de constrângeri. Variabilele și domeniile sunt asociate: domeniul unei variabile conține toate valorile pe care variabila le poate lua. O constrângere este compusă dintr-o secvență de variabile, numită sfera acesteia și un set de evaluări ale acestora, care sunt evaluările care satisfac constrângerea.

Problemele de satisfacție de constrângere la care se face referire în acest articol sunt presupuse a fi într-o formă specială. O problemă este în formă normalizată , respectiv formă regulată , dacă fiecare secvență de variabile este scopul cel mult unei constrângeri sau exact al unei constrângeri. Asumarea regularității efectuată numai pentru constrângerile binare duce la forma standardizată . Aceste condiții pot fi întotdeauna aplicate prin combinarea tuturor constrângerilor de pe o secvență de variabile într-o singură și / sau adăugarea unei constrângeri care este satisfăcută de toate valorile unei secvențe de variabile.

În figurile utilizate în acest articol, lipsa legăturilor dintre două variabile indică faptul că nici o restricție, fie o constrângere satisfăcută de toate valorile nu există între aceste două variabile.

Coerența locală

Condițiile de coerență locală „standard” necesită ca toate evaluările parțiale consistente să poată fi extinse la o altă variabilă, astfel încât alocarea rezultată să fie consecventă. O evaluare parțială este consecventă dacă îndeplinește toate constrângerile al căror scop este un subset al variabilelor atribuite.

Coerența nodului

Coerența nodurilor necesită ca fiecare constrângere unitară asupra unei variabile să fie satisfăcută de toate valorile din domeniul variabilei și invers. Această condiție poate fi impusă în mod banal prin reducerea domeniului fiecărei variabile la valorile care satisfac toate constrângerile unare ale respectivei variabile. Drept urmare, constrângerile unare pot fi neglijate și asumate încorporate în domenii.

De exemplu, având în vedere o variabilă cu un domeniu de și o constrângere , consistența nodului ar restrânge domeniul la și constrângerea ar putea fi apoi aruncată. Acest pas de pre-procesare simplifică etapele ulterioare. ${\ displaystyle V}$${\ displaystyle \ left \ {1,2,3,4 \ right \}}$${\ displaystyle V \ leq 3}$${\ displaystyle \ left \ {1,2,3 \ right \}}$

Coerența arcului

x2 este în concordanță cu arcul cu x3, dar nu cu x1, întrucât valoarea x2 = 1 nu corespunde cu nicio valoare pentru x1.

O variabilă a unei probleme de satisfacție de constrângere este în concordanță cu o alta dacă fiecare dintre valorile sale admisibile sunt în concordanță cu o anumită valoare admisibilă a celei de-a doua variabile. În mod formal, o variabilă este în concordanță cu arcul cu o altă variabilă dacă, pentru fiecare valoare din domeniul de acolo există o valoare în domeniul de astfel încât să satisfacă constrângerea binară între și . O problemă este constantă în cazul în care fiecare variabilă este în concordanță cu un alt arc. ${\ displaystyle x_ {i}}$${\ displaystyle x_ {j}}$${\ displaystyle a}$${\ displaystyle x_ {i}}$${\ displaystyle b}$${\ displaystyle x_ {j}}$${\ displaystyle (a, b)}$${\ displaystyle x_ {i}}$${\ displaystyle x_ {j}}$

De exemplu, luați în considerare constrângerea în care variabilele se încadrează în domeniul 1 până la 3. Deoarece nu poate fi niciodată 3, nu există un arc de la 3 la o valoare, astfel încât este sigur să fie eliminat. La fel, nu poate fi niciodată 1, deci nu există un arc, prin urmare poate fi eliminat. ${\ displaystyle x <y}$${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle y}$

Coerența arcului poate fi definită, de asemenea, în raport cu o constrângere binară specifică: o constrângere binară este consecventă în arc dacă fiecare valoare a unei variabile are o valoare a celei de-a doua variabile, astfel încât acestea să satisfacă constrângerea. Această definiție a consistenței arcului este similară celor de mai sus, dar este specifică unei constrângeri. Această diferență este relevantă în special pentru problemele care nu sunt normalizate, unde definiția de mai sus ar lua în considerare toate constrângerile dintre două variabile, în timp ce aceasta consideră doar una specifică.

Coerența arcului impusă prin eliminarea 1 ca valoare pentru x2. Drept urmare, x3 nu mai este în concordanță arc cu x2, deoarece x3 = 2 nu corespunde unei valori pentru x2.

Dacă o variabilă nu este în concordanță cu o alta, aceasta poate fi făcută prin eliminarea unor valori din domeniul său. Aceasta este forma de propagare a constrângerilor care impune consistența arcului: elimină, din domeniul variabilei, orice valoare care nu corespunde unei valori a celeilalte variabile. Această transformare menține soluțiile problemă, întrucât valorile eliminate nu sunt în niciun fel soluție.

Propagarea de constrângere poate face ca întreaga problemă să fie constantă prin repetarea acestei eliminări pentru toate perechile de variabile. Acest proces ar trebui să aibă în vedere o pereche de variabile date mai mult de o dată. Într-adevăr, eliminarea valorilor din domeniul unei variabile poate face ca alte variabile să nu mai fie în concordanță cu aceasta. De exemplu, dacă arc este în concordanță cu, dar algoritmul reduce domeniul de , consistența arcului cu nu mai ține și trebuie aplicată din nou. ${\ displaystyle x_ {3}}$${\ displaystyle x_ {2}}$${\ displaystyle x_ {2}}$${\ displaystyle x_ {3}}$${\ displaystyle x_ {2}}$

Un algoritm simplist ar rula pe perechile de variabile, aplicând coerența arcului, repetând ciclul până când nu se schimbă niciun domeniu pentru un ciclu întreg. Algoritmul AC-3 îmbunătățește în acest algoritm prin ignorarea constrângeri care nu au fost modificate de la ultima analizate. În special, funcționează pe un set de constrângeri care le conține inițial pe toate; la fiecare pas, este nevoie de o constrângere și aplică coerența arcului; dacă această operație ar fi putut produce o încălcare a coerenței arcului asupra altei constrângeri, o plasează înapoi în setul de constrângeri de analizat. În felul acesta, odată aplicată coerența arc pe o constrângere, această constrângere nu este luată în considerare din nou decât dacă se modifică domeniul uneia dintre variabilele sale.

Coerența căii

x1 și x2 nu sunt compatibile cu calea x3. Pot fi făcute trasee în concordanță prin eliminarea valorilor albastre din R12.

Coerența căii este o proprietate similară cu consistența arcului, dar consideră perechi de variabile în loc de una singură. O pereche de variabile este compatibilă cu calea cu o a treia variabilă dacă fiecare evaluare consistentă a perechii poate fi extinsă la cealaltă variabilă, astfel încât toate constrângerile binare sunt satisfăcute. Formal, și sunt în concordanță cu calea în cazul în care , pentru fiecare pereche de valori care satisface constrângerea binară între și , există o valoare în domeniul astfel încât și satisface constrângerea între și și între și , respectiv. ${\ displaystyle x_ {i}}$${\ displaystyle x_ {j}}$${\ displaystyle x_ {k}}$${\ displaystyle (a, b)}$${\ displaystyle x_ {i}}$${\ displaystyle x_ {j}}$${\ displaystyle c}$${\ displaystyle x_ {k}}$${\ displaystyle (a, c)}$${\ displaystyle (b, c)}$${\ displaystyle x_ {i}}$${\ displaystyle x_ {k}}$${\ displaystyle x_ {j}}$${\ displaystyle x_ {k}}$

Forma de propagare a constrângerilor care impune consistența căilor funcționează prin eliminarea unei atribuții satisfăcătoare dintr-o constrângere. Într-adevăr, coerența căii poate fi aplicată eliminând dintr-o constrângere binară toate evaluările care nu pot fi extinse la o altă variabilă. În ceea ce privește consistența arcului, această eliminare ar putea fi nevoită să ia în considerare o constrângere binară de mai multe ori. În ceea ce privește consistența arcului, problema rezultată are aceleași soluții cu cea inițială, deoarece valorile eliminate nu sunt nicio soluție.

Două variabile care nu sunt într-o restricție pot fi considerate legate de o constrângere virtuală care permite orice pereche posibilă de valori, reprezentată de marginile albastre din această figură.

Îmbunătățirea coerenței căii de x1 și x2 cu x3 elimină marginea din partea superioară. Valorile x1 și x2 nu mai sunt gratuite, ci sunt legate de o nouă constrângere reală.

Forma de propagare a constrângerilor care impune coerența căii poate introduce noi constrângeri. Când două variabile nu sunt legate de o constrângere binară, ele sunt legate în mod virtual de constrângerea care permite orice pereche de valori. Cu toate acestea, unele perechi de valori pot fi eliminate prin propagarea constrângerii. Constrângerea rezultată nu mai este satisfăcută de toate perechile de valori. Prin urmare, nu mai este o constrângere virtuală și banală.

Numele „coerența căii” derivă din definiția inițială, care implica o pereche de variabile și o cale între ele, mai degrabă decât o pereche și o singură variabilă. În timp ce cele două definiții sunt diferite pentru o singură pereche de variabile, ele sunt echivalente atunci când se referă la întreaga problemă.

generalizări

Consistența arcului și a căii poate fi generalizată la constrângeri non-binare folosind tupluri de variabile în loc de una sau de o pereche. Un tuple de variabile este în concordanță cu o altă variabilă dacă fiecare evaluare consecventă a variabilelor poate fi extinsă cu o valoare a celeilalte variabile, păstrând în același timp coerența. Această definiție se extinde la probleme întregi în mod evident. Consistența puternică este -conștiința pentru toți . ${\ displaystyle i-1}$${\ displaystyle i}$${\ displaystyle i-1}$${\ displaystyle i}$${\ displaystyle j}$${\ displaystyle j \ leq i}$

Cazul particular al coerenței 2 coincide cu consistența arcului (toate problemele sunt asumate în concordanță cu nodul în acest articol). Pe de altă parte, consistența 3 coincide cu consistența căii doar dacă toate constrângerile sunt binare, deoarece consistența căii nu implică constrângeri ternare în timp ce consistența 3.

Un alt mod de generalizare a consistenței arcului este consistența hiper arc sau consistența generalizată a arcului , care necesită extensibilitatea unei singure variabile pentru a satisface o constrângere. Anume, o variabilă este hiperarcă în concordanță cu o constrângere dacă fiecare valoare a variabilei poate fi extinsă la celelalte variabile ale constrângerii, astfel încât constrângerea este satisfăcută.

Consistența și satisfacția

Această instanță este constantă în arc și nu conține niciun domeniu gol, dar nu are soluție. Liniile albastre indică sarcini obligate de alegerea x1 = 1.

Propagarea constrângerilor (aplicarea unei forme de consistență locală) poate produce un domeniu gol sau o constrângere nesatisfăcătoare . În acest caz, problema nu are soluție. Inversul nu este adevărat în general: o instanță inconsecventă poate fi constantă sau constantă în timp ce nu are un domeniu gol sau o constrângere nesatisfăcătoare.

Într-adevăr, consistența locală este doar relativă la consistența grupurilor de variabile. De exemplu, consistența arc garantează că fiecare evaluare consistentă a unei variabile poate fi extinsă în mod constant la o altă variabilă. Cu toate acestea, atunci când o singură valoare a unei variabile este extinsă la alte două variabile, nu există nicio garanție că aceste două valori sunt în concordanță între ele. De exemplu, pot fi în concordanță cu și cu acestea , dar este posibil ca aceste două evaluări să nu fie în concordanță între ele. ${\ displaystyle x_ {1} = 1}$${\ displaystyle x_ {2} = 1}$${\ displaystyle x_ {3} = 1}$

Cu toate acestea, propagarea constrângerilor poate fi utilizată pentru a dovedi satisfacția în unele cazuri. Un set de constrângeri binare care sunt constante în arc și nu au un domeniu gol pot fi inconsistente numai dacă rețeaua de constrângeri conține cicluri. Într-adevăr, dacă constrângerile sunt binare și formează un grafic aciclic, valorile pot fi întotdeauna propagate prin constrângeri: pentru fiecare valoare a unei variabile, toate variabilele dintr-o restricție cu aceasta au o valoare care să satisfacă această constrângere. Ca urmare, o soluție poate fi găsită alegând iterativ o variabilă neasignată și propagând recursiv peste constrângeri. Acest algoritm nu încearcă niciodată să atribuie o valoare unei variabile care este deja atribuită, deoarece aceasta ar presupune existența unor cicluri în rețeaua de constrângeri.

O condiție similară este valabilă pentru coerența căii. Cazurile speciale în care se poate stabili fiabilitatea prin aplicarea consistenței arcului și a consistenței traseului sunt următoarele.

1. aplicarea coerenței arcului stabilește satisfacția problemelor din constrângerile binare fără cicluri (un arbore de constrângeri binare);
2. aplicarea coerenței căilor stabilește o fiabilitate pentru constrângerile binare (eventual cu cicluri) cu domenii binare;
3. aplicarea consistenței puternice stabilește satisfacția problemelor care conțin variabile.${\ displaystyle n}$${\ displaystyle n}$

Cazuri speciale

Unele definiții sau rezultate despre coerența relativă se păstrează numai în cazuri speciale.

Când domeniile sunt compuse din numere întregi , poate fi definită consistența legată. Această formă de consecvență se bazează pe consistența valorilor extreme ale domeniilor, adică valorile minime și maxime pe care le poate lua o variabilă.

Când constrângerile sunt algebice sau booleene , consistența arcului este echivalentă cu adăugarea unei noi constrângeri sau modificarea sintactică a unei vechi, iar acest lucru se poate realiza prin compunerea adecvată a constrângerilor.

Constrângeri specializate

Unele tipuri de constrângeri sunt frecvent utilizate. De exemplu, se utilizează deseori constrângerea că unele variabile sunt diferite. Există algoritmi eficienți specializați pentru aplicarea coerenței arcului pe astfel de constrângeri.

Limitarea care impune o serie de variabile care trebuie să fie diferite este de obicei scrisă sau . Această constrângere este echivalentă cu non-egalitatea tuturor perechilor de variabile diferite, adică pentru fiecare . Când domeniul unei variabile este redus la o singură valoare, această valoare poate fi eliminată din toate celelalte domenii prin propagarea constrângerii atunci când se aplică consistența arcului. Utilizarea constrângerii de specialitate permite exploatarea proprietăților care nu țin de deficiențe binare individuale . ${\ displaystyle \ mathop {\ rm {alldifferent}} (x_ {1}, \ ldots, x_ {n})}$alldifferent([X1,...,Xn])${\ displaystyle x_ {i} \ not = x_ {j}}$${\ displaystyle i \ not = j}$

O primă proprietate este că numărul total de elemente din domeniile tuturor variabilelor trebuie să fie cel puțin numărul de variabile. Mai precis, după aplicarea coerenței arcului, numărul de variabile neatribuite nu trebuie să depășească numărul de valori din uniunea domeniilor lor. În caz contrar, constrângerea nu poate fi satisfăcută. Această condiție poate fi verificată cu ușurință pe o constrângere alldifferentsub formă, dar nu corespunde coerenței arc a rețelei de inegalități. O a doua proprietate a alldifferentconstrângerii unice este aceea că coerența hiper arc poate fi verificată eficient folosind un algoritm de potrivire bipartit . În special, un grafic este construit cu variabile și valori ca cele două seturi de noduri, iar pe acesta se execută un algoritm specializat de potrivire a graficului bipartit pentru a verifica existența unei astfel de potriviri.

Un alt tip de constrângere care este frecvent utilizat este aceea cumulative. A fost introdus pentru probleme de programare și plasare. Ca exemplu, cumulative([S1,...,Sm], [D1,...,Dm], [R1,...,Rm], L)poate fi utilizat pentru a formaliza condiția în care există mactivități, fiecare cu ora de pornire si, durata diși folosirea unei cantități ride resursă. Constrângerea afirmă că suma totală disponibilă a resurselor este L. Există tehnici specializate de propagare a constrângerilor pentru constrângerile cumulate; diferite tehnici sunt utilizate în funcție de care domenii variabile sunt deja reduse la o singură valoare.

O a treia constrângere specializată care este utilizată în programarea logicii de constrângere este cea element. În programarea logică de constrângere, listele sunt permise ca valori ale variabilelor. O constrângere element(I, L, X)este satisfăcută dacă Leste o listă și Xeste al Ișaptelea element al acestei liste. Există reguli specializate de propagare a constrângerilor pentru aceste constrângeri. Ca exemplu, dacă Lși Isunt reduse la un domeniu cu o singură valoare, Xse poate determina o valoare unică pentru . Mai general, se Xpot deduce valori imposibile ale domeniului și invers. ${\ displaystyle I}$

Consistență direcțională

Consistența direcțională este varianta arc, cale și -conștiență adaptată pentru a fi utilizată de un algoritm care atribuie valori variabilelor în urma unui anumit ordin de variabile. Acestea sunt similare cu omologii lor non-direcționali, dar necesită doar ca o alocare consecventă la unele variabile să poată fi extinsă în mod constant la o altă variabilă mai mare decât ele în conformitate cu comanda. ${\ displaystyle i}$

Arcul direcțional și consistența căii

O instanță care este constantă în sens direcțional în conformitate cu ordinea x1 x2 x3, dar nu este constantă în arc (nu există nicio constrângere între x1 și x3; marginile corespunzătoare sunt omise). Fiecare valoare a unei variabile a indexului inferior corespunde valorilor variabilelor cu index mai mare. Semnele de întrebare indică puncte în care conversația nu deține.

Dacă un algoritm evaluează variabilele din ordine , coerența este utilă numai atunci când garantează că valorile variabilelor cu index inferior sunt în concordanță cu valorile celor cu index superior. ${\ displaystyle x_ {1}, \ ldots, x_ {n}}$

Atunci când alegeți o valoare pentru o variabilă, valorile care sunt incompatibile cu toate valorile unei variabile neasignate pot fi neglijate. Într-adevăr, chiar dacă aceste valori sunt în concordanță cu evaluarea parțială curentă, algoritmul nu va găsi ulterior o valoare consistentă pentru variabila neatribuită. Pe de altă parte, aplicarea coerenței cu variabilele care sunt deja evaluate nu este necesară: dacă algoritmul alege o valoare care nu este în concordanță cu evaluarea parțială curentă, oricum este detectată inconsistența.

Presupunând că ordinea de evaluare a variabilelor este , o problemă de satisfacție de constrângere este consecventă din punct de vedere direcțional dacă fiecare variabilă este în concordanță cu orice altă variabilă, astfel încât . Coerența traseului direcțional este similară, dar două variabile trebuie să fie în concordanță cu doar dacă . Consistența puternică a căii direcționale înseamnă atât consistența căii direcționale, cât și consistența arcului direcțional. Definiții similare pot fi date pentru celelalte forme de consecvență. ${\ displaystyle x_ {1}, \ ldots, x_ {n}}$${\ displaystyle x_ {i}}$${\ displaystyle x_ {j}}$${\ displaystyle i <j}$${\ displaystyle x_ {i}, x_ {j}}$${\ displaystyle x_ {z}}$${\ displaystyle i, j <z}$

Propagarea constrângerilor pentru consistența arcului și a căii

Propagarea constrângerii care impune consistența arcului direcțional iterează asupra variabilelor de la ultima la prima, aplicând la fiecare pas consistența arc a fiecărei variabile a indexului inferior cu aceasta. Dacă ordinea variabilelor este , acest algoritm iterează peste variabile de la - ; pentru variabilă , aplică coerența arcului a fiecărei variabile a indexului mai mică decât cu . ${\ displaystyle x_ {1}, \ ldots, x_ {n}}$${\ displaystyle x_ {n}}$${\ displaystyle x_ {1}}$${\ displaystyle x_ {j}}$${\ displaystyle j}$${\ displaystyle x_ {j}}$

O instanță care nu este arc directă consistentă: nu corespunde nici unei valori a și nu corespunde nici unei valori a . Nu există nicio constrângere între și (marginile corespunzătoare sunt omise). ${\ displaystyle x_ {1} = 2}$${\ displaystyle x_ {2}}$${\ displaystyle x_ {2} = 3}$${\ displaystyle x_ {3}}$${\ displaystyle x_ {1}}$${\ displaystyle x_ {3}}$	Aplicarea coerenței direcționale a arcului începe cu și face ca arcul să fie în concordanță prin eliminarea valorii . ${\ displaystyle x_ {3}}$${\ displaystyle x_ {2}}$${\ displaystyle x_ {2} = 3}$	Consolidarea consecvenței arcului direcțional continuă . De când a fost deja eliminat, ambele și sunt eliminate. ${\ displaystyle x_ {2}}$${\ displaystyle x_ {2} = 3}$${\ displaystyle x_ {1} = 2}$${\ displaystyle x_ {1} = 3}$

Coerența căii direcționale și consistența direcției puternice a căii pot fi aplicate prin algoritmi similari cu cea pentru consistența arcului. Procesează variabile de la la ; pentru fiecare variabilă două variabile cu sunt luate în considerare, și calea de coerența dintre ele cu este executată. Nu este necesară nicio operație dacă problema nu conține nicio restricție și nici o restricție între și . Cu toate acestea, chiar dacă nu există nicio constrângere între și , se presupune una banală. Dacă propagarea constrângerii își reduce setul de misiuni satisfăcătoare, creează efectiv o nouă constrângere non-banală. Propagarea constrângerilor care impune consistența puternică a căii direcționale este similară, dar impune și consistența arcului. ${\ displaystyle x_ {n}}$${\ displaystyle x_ {1}}$${\ displaystyle x_ {z}}$${\ displaystyle x_ {i}, x_ {j}}$${\ displaystyle i, j <z}$${\ displaystyle x_ {z}}$${\ displaystyle x_ {i}}$${\ displaystyle x_ {z}}$${\ displaystyle x_ {j}}$${\ displaystyle x_ {z}}$${\ displaystyle x_ {i}}$${\ displaystyle x_ {j}}$

Consistență direcțională și fiabilitate

Consistența direcțională garantează că soluțiile parțiale care satisfac o constrângere pot fi extinse în mod constant la o altă variabilă a unui indice mai mare. Cu toate acestea, nu garantează că extensiile la diferite variabile sunt în concordanță între ele. De exemplu, o soluție parțială poate fi extinsă în mod constant la variabilă sau la variabilă , dar totuși aceste două extensii nu sunt în concordanță între ele. ${\ displaystyle x_ {i}}$${\ displaystyle x_ {j}}$

Există două cazuri în care acest lucru nu se întâmplă, iar consistența direcțională garantează satisfacția dacă niciun domeniu nu este gol și nici o constrângere nu este satisfăcătoare.

Primul caz este cel al unei probleme de constrângere binară cu o ordonare a variabilelor care face ca graficul ordonat al constrângerii să aibă lățimea 1. O astfel de ordonare există dacă și numai dacă graficul constrângerilor este un arbore. Dacă acesta este cazul, lățimea graficului limitează numărul maxim de noduri inferioare (în funcție de ordonare) cu care este alăturat un nod. Consistența arcului direcțional garantează că fiecare alocare consistentă unei variabile poate fi extinsă la noduri superioare, iar lățimea 1 garantează că un nod nu este unit la mai mult de un nod inferior. Drept urmare, după ce se atribuie variabila inferioară, valoarea acesteia poate fi extinsă în mod constant la fiecare variabilă superioară cu care este asociată. Această extensie nu poate duce ulterior la inconsistență. Într-adevăr, nicio altă variabilă inferioară nu este asociată cu acea variabilă superioară, deoarece graficul are lățimea 1.

Drept urmare, dacă o problemă de constrângere are lățimea 1 în ceea ce privește o ordonare a variabilelor sale (ceea ce presupune că graficul corespunzător este un arbore) și problema este arc directă în concordanță cu aceeași ordonare, o soluție (dacă există) poate fi găsit alocând iterativ variabile în funcție de comandă.

Al doilea caz în care consistența direcțională garantează satisfacția dacă niciun domeniu nu este gol și nici o constrângere nu este satisfăcătoare este cel al problemelor de constrângere binară al căror grafic a indus lățimea 2, folosind consistența direcțională puternică. Într-adevăr, această formă de consecvență garantează că fiecare alocare către o variabilă sau o pereche de variabile poate fi extinsă la o variabilă mai mare, iar lățimea 2 garantează că această variabilă nu este alăturată unei alte perechi de variabile inferioare.

Motivul pentru care lățimea indusă este considerată în loc de lățime este că aplicarea coerenței traseului direcțional poate adăuga constrângeri. Într-adevăr, dacă două variabile nu sunt în aceeași constrângere, dar sunt într-o constrângere cu o variabilă mai mare, unele perechi din valorile lor pot încălca consistența căilor. Înlăturarea acestor perechi creează o nouă constrângere. Ca urmare, propagarea constrângerii poate produce o problemă al cărei grafic are mai multe muchii decât cel original. Cu toate acestea, toate aceste muchii sunt neapărat în graficul indus, deoarece sunt toate între doi părinți ai aceluiași nod. Lățimea 2 garantează că fiecare evaluare parțială consistentă poate fi extinsă la o soluție, dar această lățime este relativă a graficului generat. Ca urmare, lățimea indusă fiind 2 este necesară pentru o consistență puternică a căii direcționale pentru a garanta existența soluțiilor.

Coerența direcțională a i

Liniile albastre indică faptul că nu există nicio restricție între x3 și x4, astfel încât fiecare pereche de valori este permisă. În aceste imagini, lipsa muchiilor între două variabile indică implicit lipsa unei constrângeri. Această problemă are lățimea 2.

- Consistența direcțională este garanția că fiecare alocare consistentă la variabile poate fi extinsă în mod constant la o altă variabilă care este mai mare în ordine. -Consistența direcțională puternică este definită într-un mod similar, dar toate grupurile de cel mult variabile sunt considerate. Dacă o problemă este puternic orientată în direcție și are o lățime mai mică decât și nu are un domeniu gol sau o constrângere nesatisfăcătoare, are soluții. ${\ displaystyle i}$${\ displaystyle i-1}$${\ displaystyle i}$ ${\ displaystyle i-1}$${\ displaystyle i}$${\ displaystyle i}$

Fiecare problemă poate fi determinată puternic în direcție , dar această operație poate crește lățimea graficelor corespunzătoare. Procedura de propagare a constrângerilor care impune consistența direcțională este similară cu cea utilizată pentru consistența arcului direcțional și consistența căii. Variabilele sunt considerate pe rând, de la ultima la prima în funcție de ordine. Pentru variabilă , algoritmul consideră fiecare grup de variabile care au un indice mai mic decât și sunt într-o restricție . Coerența acestor variabile este verificată și posibil aplicată prin eliminarea atribuțiilor satisfăcătoare din constrângerea dintre toate aceste variabile (dacă există, sau creând una nouă, altfel). ${\ displaystyle i}$${\ displaystyle x_ {k}}$${\ displaystyle i-1}$${\ displaystyle k}$${\ displaystyle x_ {k}}$${\ displaystyle x_ {k}}$${\ displaystyle i}$

Consolidarea coerenței pe x5 elimină linia roșie, creând astfel o nouă constrângere non-banală între x3 și x4. Drept urmare, x4 are x3 ca nou părinte, pe lângă x1 și x2. Această modificare mărește lățimea la 3.

Această procedură generează o instanță puternic direcțional- inconsistentă. Cu toate acestea, poate adăuga, de asemenea, noi constrângeri la instanță. Ca urmare, chiar dacă lățimea problemei inițiale este , lățimea instanței rezultate poate fi mai mare. Dacă este cazul, coerența direcțională puternică nu implică satisfacție, chiar dacă niciun domeniu nu este gol și nici o constrângere nu este satisfăcătoare. ${\ displaystyle i}$${\ displaystyle i}$

Cu toate acestea, propagarea constrângerilor adaugă numai constrângeri la variabile mai mici decât cea pe care o are în vedere în prezent. Drept urmare, nicio constrângere asupra unei variabile nu este modificată sau adăugată după ce algoritmul s-a ocupat de această variabilă. În loc să ia în considerare o fixă , se poate modifica la numărul de părinți al fiecărei variabile considerate (părinții unei variabile sunt variabilele de index mai mici decât variabila și care sunt într-o constrângere cu variabila). Aceasta corespunde luării în considerare a tuturor părinților unei variabile date la fiecare pas. Cu alte cuvinte, pentru fiecare variabilă de la ultima la prima, toți părinții ei sunt incluși într-o nouă constrângere care le limitează valorile la cele care sunt în concordanță . Deoarece acest algoritm poate fi văzut ca o modificare a precedentului, cu o valoare care este modificată la numărul de părinți al fiecărui nod, se numește consistență adaptivă . ${\ displaystyle i}$${\ displaystyle x_ {i}}$${\ displaystyle x_ {i}}$${\ displaystyle i}$

Acest algoritm aplică o rezistență puternic direcțională cu lățimea indusă a problemei. Instanța rezultată este satisfăcătoare dacă și numai dacă niciun domeniu sau restricție nu este făcut gol. Dacă acesta este cazul, o soluție poate fi găsită cu ușurință prin setarea iterativă a unei variabile neatribuite la o valoare arbitrară și prin propagarea acestei evaluări parțiale la alte variabile. Acest algoritm nu este întotdeauna timp polinomial, deoarece numărul de constrângeri introduse prin aplicarea unei consistențe direcționale puternice poate produce o creștere exponențială a dimensiunii. Problema este totuși rezolvată în timp polinomial dacă aplicarea unei consistențe direcționale puternice nu mărește superpolinomial instanța. Drept urmare, dacă o instanță a indus lățimea delimitată de o constantă, ea poate fi rezolvată în timp polinomial. ${\ displaystyle i}$${\ displaystyle i}$

Eliminarea găleții

Eliminarea cupei este un algoritm de satisfacție. Poate fi definit ca o reformulare a consistenței adaptive. Definițiile sale utilizează găleți, care sunt containere pentru constrângere, fiecare variabilă având o găleată asociată. O constrângere aparține întotdeauna cupei variabilei sale cea mai mare.

Algoritmul de eliminare a găleții trece la rândul său de la cea mai mare la cea mai mică variabilă. La fiecare pas, sunt luate în considerare constrângerile din bucile acestei variabile . Prin definiție, aceste constrângeri implică doar variabile mai mici decât . Algoritmul modifică constrângerea dintre aceste variabile inferioare (dacă există, în caz contrar, creează una nouă). În special, aplică valorile lor pentru a fi extensibile în mod constant cu constrângerile din găleata de . Această nouă constrângere, dacă există, este apoi plasată în găleata corespunzătoare. Deoarece această constrângere implică doar variabile mai mici decât , aceasta este adăugată la o găleată a unei variabile mai mică decât . ${\ displaystyle x_ {i}}$${\ displaystyle x_ {i}}$${\ displaystyle x_ {i}}$${\ displaystyle x_ {i}}$${\ displaystyle x_ {i}}$${\ displaystyle x_ {i}}$

Acest algoritm este echivalent cu aplicarea coerenței adaptive. Întrucât amândoi aplică coerența unei variabile cu toți părinții săi și din moment ce nu este adăugată o nouă constrângere după ce este considerată o variabilă, ceea ce rezultă este o instanță care poate fi rezolvată fără backtracking .

Deoarece graficul instanței pe care o produc este o subgrafă a graficului indus, dacă lățimea indusă este delimitată de o constantă, instanța generată este de dimensiune polinomială în mărimea instanței inițiale. Drept urmare, dacă lățimea indusă a unei instanțe este delimitată de o constantă, rezolvarea ei se poate face în timp polinomial de către cei doi algoritmi.

Coerența relațională

În timp ce definițiile anterioare ale coerenței se referă la consistența atribuțiilor, consistența relațională implică satisfacția unei constrângeri date sau a unui set de constrângeri. Mai precis, coerența relațională implică faptul că fiecare atribuire parțială consecventă poate fi extinsă astfel încât o constrângere sau un set de constrângeri să fie satisfăcute. În mod formal, o constrângere asupra variabilelor este arc-relațională în concordanță cu una dintre variabilele sale dacă fiecare atribuire consistentă la care poate fi extinsă într-un asemenea mod este satisfăcută. Diferența dintre consistența „regulată” și consistența relațională a arcului constă în aceea că cea din urmă necesită doar atribuirea extinsă pentru a satisface o constrângere dată, în timp ce prima cere să satisfacă toate constrângerile relevante. ${\ displaystyle C}$${\ displaystyle X}$${\ displaystyle x}$${\ displaystyle X \ backslash \ {x \}}$${\ displaystyle x}$${\ displaystyle C}$${\ displaystyle i}$

(Regulat) coerența i: dacă o evaluare este consecventă, ea poate fi extinsă la o altă variabilă, astfel încât toate constrângerile relevante sunt satisfăcute.

Coerența arcului relațional: dacă o evaluare a variabilelor unei constrângeri, dar una este consistentă, ea poate fi întotdeauna extinsă la acea variabilă, astfel încât constrângerea este satisfăcută. Marginile cian reprezintă constrângeri care nu trebuie satisfăcute de extensie.

Această definiție poate fi extinsă la mai multe constrângeri și la mai multe variabile. În special, coerența căii relaționale este similară cu coerența relațională a arcului, dar două restricții sunt utilizate în locul uneia. Două constrângeri sunt calea relațională consistentă cu o variabilă dacă fiecare atribuire consistentă la toate variabilele lor, dar cea considerată poate fi extinsă astfel încât cele două constrângeri sunt satisfăcute.

Pentru mai mult de două constrângeri, este definită coerența relațională . Consistența relațională implică un set de constrângeri și o variabilă care se află în sfera tuturor acestor constrângeri. În particular, aceste constrângeri sunt în funcție de coeficientul relațional cu variabila dacă fiecare alocare consistentă la toate celelalte variabile care sunt în sfera lor de aplicare poate fi extinsă la variabilă, astfel încât aceste constrângeri sunt satisfăcute. O problemă este -relațională, în cazul în care fiecare set de constrângeri este relațional -consistent cu fiecare variabilă care se află în toate scopurile lor. Consistența relațională puternică este definită ca mai sus: este proprietatea de a fi relațional -conștient pentru fiecare . ${\ displaystyle m}$${\ displaystyle m}$${\ displaystyle m}$${\ displaystyle m}$${\ displaystyle m}$${\ displaystyle m}$${\ displaystyle m}$${\ displaystyle m}$${\ displaystyle m}$${\ displaystyle k}$${\ displaystyle k <m}$

Coerența relațională poate fi definită și pentru mai multe variabile, în loc de una. Un set de constrângeri este constant- relațional dacă fiecare atribuire consistentă a unui subset de variabile ale acestora poate fi extinsă la o evaluare la toate variabilele care satisfac toate constrângerile. Această definiție nu se extinde exact mai sus, deoarece variabilele la care se presupune că extensiile nu sunt neapărat în toate domeniile constrângerilor implicate. ${\ displaystyle m}$${\ displaystyle (i, m)}$${\ displaystyle i}$

Dacă este dată o ordine a variabilelor, coerența relațională poate fi limitată la cazurile în care variabilele (variabilele) evaluării ar trebui să fie extensibile pentru a urma celelalte variabile din ordine. Această condiție modificată se numește consistență relațională direcțională.

Consistența relațională și fiabilitatea

O problemă de satisfacție de constrângere poate fi relativ consistentă, nu are un domeniu gol sau o constrângere nesatisfăcătoare și totuși poate fi nesatisfăcător. Există totuși câteva cazuri în care acest lucru nu este posibil.

Primul caz este cel al problemei puternic-relaționale care sunt constant atunci când domeniile conțin cel mult elemente. În acest caz, o evaluare consecventă a variabilelor poate fi întotdeauna extinsă la o singură altă variabilă. Dacă există o astfel de evaluare și este variabila, există doar valori posibile pe care variabila le poate lua. Dacă toate aceste valori sunt incompatibile cu evaluarea, există constrângeri (neapărat unice) care sunt încălcate de evaluare și una dintre valorile sale posibile. Drept urmare, evaluarea nu poate fi extinsă pentru a satisface toate aceste - sau mai puțin constrângeri, încălcând condiția de rezistență relațională puternică . ${\ displaystyle m}$${\ displaystyle m}$${\ displaystyle k}$${\ displaystyle x_ {1} = a_ {1}, \ ldots, x_ {k} = a_ {k}}$${\ displaystyle x_ {k + 1}}$${\ displaystyle m}$${\ displaystyle m}$${\ displaystyle m}$${\ displaystyle m}$

Al doilea caz este legat de o măsură a constrângerilor, mai degrabă decât de domenii. O constrângere este -test dacă fiecare evaluare la toate variabilele sale, dar una poate fi extinsă pentru a satisface constrângerea fie prin toate valorile posibile ale celeilalte variabile, fie prin cel mult valorile sale. Problemele care au constrângerile strânse sunt satisfăcătoare, dacă și numai dacă sunt puternic relaționale -conștiente. ${\ displaystyle m}$${\ displaystyle m}$${\ displaystyle m}$${\ displaystyle m + 1}$

O matrice convexă de rând: cele 1 din fiecare rând sunt contigue (nu există 0 între ele).

Al treilea caz este cel al constrângerilor binare care pot fi reprezentate prin matrice rând-convexe. O constrângere binară poate fi reprezentată printr-o matrice bidimensională , unde este 0 sau 1 în funcție de dacă valoarea -th a domeniului și valoarea -th a domeniului satisface constrângerea. Un rând al acestei matrice este convex dacă 1-ul pe care îl conține este consecutiv (formal, dacă două elemente sunt 1, toate elementele între ele sunt și 1). O matrice este rând convex dacă toate rândurile sale sunt convexe. ${\ displaystyle M}$${\ displaystyle M_ {ij}}$${\ displaystyle i}$${\ displaystyle x_ {i}}$${\ displaystyle j}$${\ displaystyle x_ {j}}$

Fiecare matrice reprezintă constrângerea dintre x _i și x _{k +1} . Dacă a ₁ ... a _k sunt valori pentru x ₁ ... x _k , rândurile unui ₁ ... a _k din fiecare matrice spun valorile permise pentru x _{k +1} . Row-convex-Ness și puternică consecvență calea relațională implică existența unei valori coerente a _{k +1} pentru x _{k + 1} .

Condiția care face ca consistența relațională puternică a traseului să fie echivalentă cu fiabilitatea este aceea a problemelor de satisfacție de constrângere pentru care există un ordin al variabilelor care face ca toată constrângerea să fie reprezentată de matrice convexe de rând. Acest rezultat se bazează pe faptul că un set de rânduri convexe având un element comun în pereche au, de asemenea, un element comun global. Având în vedere o evaluare a variabilelor, valorile permise pentru cea de -a doua sunt date prin selectarea unor rânduri dintre unele constrângeri. În particular, pentru fiecare variabilă dintre ele, rândul relativ la valoarea sa din matrice reprezentând constrângerea care o raportează la cea reprezintă valorile permise ale acesteia din urmă. Deoarece aceste rânduri sunt convexe și au un element comun în pereche datorită consistenței căii, au și un element comun comun, care reprezintă o valoare a ultimei variabile care este în concordanță cu celelalte. ${\ displaystyle k}$${\ displaystyle k + 1}$${\ displaystyle k}$${\ displaystyle k + 1}$

Utilizări ale consecvenței locale

Toate formele de consistență locală pot fi aplicate prin propagarea constrângerilor, care poate reduce domeniile variabilelor și seturile de atribuții care satisfac o constrângere și pot introduce noi constrângeri. Ori de câte ori propagarea constrângerii produce un domeniu gol sau o constrângere nesatisfăcătoare, problema inițială este nesatisfăcătoare. Prin urmare, toate formele de consistență locală pot fi utilizate ca aproximări ale satisfacției. Mai precis, ei pot fi folosiți ca algoritmi de incomodabilitate incompletă, deoarece pot dovedi că o problemă este nesatisfăcabilă, dar, în general, nu pot dovedi că o problemă este satisfăcătoare. Astfel de algoritmi aproximativi pot fi folosiți de algoritmi de căutare ( backtracking , backjumping , căutare locală etc.) ca euristică pentru a spune dacă o soluție parțială poate fi extinsă pentru a satisface toate constrângerile fără a o analiza în continuare.

Chiar dacă propagarea constrângerii nu produce un domeniu gol sau o constrângere nesatisfăcătoare, poate totuși reduce domeniile sau întări constrângerile. Dacă acesta este cazul, spațiul de căutare al problemei este redus, reducând astfel cantitatea de căutare necesară pentru rezolvarea problemei.

Consistența locală dovedește satisfacția în unele cazuri restrânse (a se vedea Complexitatea satisfacției constrângerii # Restricții ). Acesta este cazul unor tipuri speciale de probleme și / sau al unor tipuri de consecvență locală. De exemplu, aplicarea coerenței arcului pe problemele aciclice binare permite să se spună dacă problema este satisfăcătoare. Îmbunătățirea rezistenței direcționale puternice permite comunicarea gradului de satisfacție a problemelor care au indus lățimea în conformitate cu aceeași ordine. Coerența direcțională adaptativă permite să spună satisfacția unei probleme arbitrare. ${\ displaystyle i}$${\ displaystyle i-1}$

Vezi si

• Propagarea unității
• Programarea constrângerilor
• Programarea logicii de constrângere
• Privit (backtracking)

linkuri externe

• Propagarea constrângerii - dezertația de către Guido Tack oferind un bun sondaj asupra problemelor de teorie și implementare

Referințe

• Lecoutre, Christophe (2009). Rețele de constrângere: tehnici și algoritmi . ISTE / Wiley. ISBN  978-1-84821-106-3
• Dechter, Rina (2003). Procesarea constrângerilor . Morgan Kaufmann.ISBN  1-55860-890-7
• Apt, Krzysztof (2003). Principiile programării constrângerilor . Presa universitară din Cambridge.ISBN  0-521-82583-0
• Marriott, Kim; Peter J. Stuckey (1998). Programarea cu constrângeri: o introducere . Presa MIT.ISBN  0-262-13341-5