Programare constrângere

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare
Fără note de subsol
Acest articol sau secțiune despre subiectul informaticii lipsește sau lipsește de note specifice și referințe bibliografice .
Deși există o bibliografie și / sau legături externe , nu există o contextualizare a surselor cu note de subsol sau alte referințe precise care indică cu exactitate originea informațiilor. Puteți îmbunătăți această intrare citând mai precis sursele . Urmați sfaturile de proiectare de referință .

În calcularea programării constrângerii, numită și constrângere sau constrângere este o paradigmă de programare în care relațiile dintre variabile pot fi declarate sub formă de constrângeri. Constrângerile diferă de primitivele definite în mod normal de alte limbaje de programare prin faptul că nu specifică acțiuni individuale care trebuie efectuate pas cu pas, ci mai degrabă specifică pur și simplu proprietățile pe care trebuie să le aibă soluția de găsit. Constrângerile utilizate pot fi de diferite tipuri: cele bazate pe așa-numita problemă de satisfacție a constrângerii (Constraint satisfaction problem sau CSP), cele rezolvate de algoritmul Simplex (Simplex Algorithm) și altele. Constrângerile care trebuie aplicate pot fi furnizate încorporate în limbajul de programare sau în biblioteci separate.

Programarea constrângerii a început ca programare logică de constrângere, introducând constrângeri încorporate într-un program de tip logic. Această variantă a programării logice a fost opera lui Jaffar și Lassez, care, în 1987, au dezvoltat o clasă de constrângeri special concepute pentru a fi utilizate în limbajul Prolog II . Primele implementări ale programării logice de constrângere au fost Prolog III , CLP (R) și CHIP . În prezent există mulți interpreți pentru programe logice restricționate, cum ar fi GNU Prolog .

Spre deosebire de programarea logică, constrângerile pot fi inserate în programarea funcțională , rescrierea și limbajele imperative . În programarea funcțională, constrângerile sunt implementate, de exemplu, în limbajul de programare multi-paradigmă Oz . Constrângerile sunt încorporate (integrate) în limbajul imperativ Caleidoscop . Cu toate acestea, în limbile imperative, constrângerile sunt implementate în principal prin așa-numitele seturi de instrumente de rezolvare a constrângerilor , care sunt biblioteci separate, furnizate împreună cu limbajul. ILOG CP Optimizer , este un exemplu al acestor biblioteci pentru C ++ , Java și .NET .

Programare logică de constrângere

Programarea constrângerilor este integrarea constrângerilor într-un limbaj care acționează ca gazdă . Primele limbaje utilizate pentru găzduire au fost limbaje logice , atât de mult încât aceste aplicații au fost numite inițial programare logică de constrângere . Cele două paradigme împărtășesc multe caracteristici importante, cum ar fi variabilele logice și retrogradarea . În prezent, majoritatea implementărilor Prolog includ una sau mai multe biblioteci pentru a sprijini programarea logică de constrângere. Diferențele dintre programele logice și programele de constrângere sunt, în principiu, determinate de stilul folosit pentru a crea modele de simulare din lumea reală. În funcție de caz, unul dintre cele două stiluri de programare este mai simplu și „natural” de adoptat.

Abordarea pe care se bazează programarea constrângerilor este de a căuta o „stare” a „lumii” în care un număr mare de constrângeri sunt satisfăcute simultan. Rezolvarea unei „probleme” se presupune că este echivalentă cu găsirea unei „lumi posibile” descrisă de un număr (inițial necunoscut) de variabile. Programul caută valorile care, atribuite variabilelor, definesc cel mai bine „lumea” supusă constrângerilor impuse.

Temporal simultană Constrângere de programare (TCC) și non-deterministă Temporal simultană Constrângere de programare (NTCC) sunt variante de programare constrângere în care timpul variabilă intră în joc.

Lista unor limbaje de programare logică de constrângere:

  • B-Prolog (Bazat pe Prolog, proprietar)
  • CHIP V5 (Bazat pe Prolog, include și biblioteci C ++ și C, proprietare)
  • Salut Prolog (Bazat pe Prolog, gratuit: GPL / LGPL)
  • ECLiPSe (Bazat pe Prolog, open source)
  • SICStus (bazat pe Prolog, proprietar)
  • GNU Prolog
  • YAP Prolog , pe ncc.up.pt. Adus la 9 ianuarie 2008 (arhivat din original la 18 aprilie 2006) .
  • SWI Prolog free, bazat pe Prolog, conține multe biblioteci de rezoluție de constrângeri

Domenii de aplicații

Constrângerile utilizate în programarea constrângerilor aparțin de obicei unor domenii specifice, inclusiv:

Domeniile finite sunt unul dintre domeniile în care programarea constrângerilor a avut cel mai mare succes. În unele domenii (cum ar fi cercetarea operațională ) programarea constrângerilor se bazează practic pe domenii finite. Algoritmii de rezolvare a domeniului finit sunt utili pentru rezolvarea problemelor de satisfacție a constrângerilor și se bazează adesea pe așa-numita consistență locală sau pe una dintre aproximările sale.

Sintaxa pentru exprimarea constrângerilor pe domeniile finite depinde de limba gazdă . Următorul exemplu este un exemplu de program Prolog care rezolvă puzzle-ul clasic al programelor de programare a constrângerilor logice, cunoscut sub numele de TRIMITE + MAI MULTE = BANI:

 sendmore ( cifre ) : -
    Cifre = [ S , E , N , D , M , O , R , E ], % Creați variabile
    Cifre :: [ 0..9 ], % Asociați domeniul cu variabile
    S # \ = 0 , % constrângere: S trebuie să fie diferit de 0
    M # \ = 0 ,
    alldifferent ( cifre ), % Toate elementele trebuie să aibă valori diferite
                 1000 * S + 100 * E + 10 * N + D % Alte constrângeri
               + 1000 * M + 100 * O + 10 * R + E
    # = 10000 * M + 1000 * O + 100 * N + 10 * E + Y ,
    etichetare ( cifre ). % Începe căutarea soluției

Interpretul creează o variabilă pentru fiecare literă a puzzle-ului. Simbolul :: este utilizat pentru a specifica domeniul acestor variabile, pentru a permite gama de valori {0,1,2,3, ..., 9}. Constrângerile S # \ = 0 și M # \ = 0 înseamnă că aceste două variabile nu pot asuma valoarea zero. Când interpretul procesează și aplică aceste constrângeri, acesta restricționează domeniile acestor două variabile prin eliminarea valorii 0. Apoi este procesată constrângerea alldifferent(Digits) , care nu produce reducerea niciunui domeniu, ci este pur și simplu stocată. Ultima constrângere dictează faptul că cifrele atribuite literelor trebuie să fie astfel încât expresia „TRIMITE + MAI MULTE = BANI” să rămână valabilă atunci când fiecare literă este înlocuită de cifra sa corespunzătoare. Din analiza acestei constrângeri, printr-o operație de inferență , programul de rezolvare deduce că M = 1. Prin urmare, toate constrângerile stocate anterior, și care conține variabila M, sunt examinate re: în exemplu, prin intermediul de propagare constrângere asupra alldifferent constrângerea, valoarea 1 este îndepărtat din domeniul tuturor celorlalte variabile. Propagarea constrângerii poate rezolva problema prin reducerea tuturor domeniilor la o singură valoare sau poate dovedi că problema nu admite soluții, reducând domeniul la un set gol. În plus, se poate termina și fără a demonstra satisfacția sau insatisfacția problemei. Literalele etichetate cu etichetare sunt folosite pentru a începe căutarea efectivă a unei soluții.

Programarea constrângerilor în limbaje imperative

Programarea constrângerilor este posibilă și în cazul unor limbaje imperative folosind biblioteci separate. Unele dintre cele mai populare biblioteci sunt:

Elemente conexe

linkuri externe

Controlul autorității Tezaur BNCF 62579 · LCCN (EN) sh94003833 · BNF (FR) cb124026426 (data)
Informatică Portal IT : accesați intrările Wikipedia care se ocupă cu IT
Adus de la „ https://it.wikipedia.org/w/index.php?title=Programmazione_a_constraints&oldid=116821568 ”