Programació de restriccions
La programació de restriccions (CP) [1] és un paradigma per resoldre problemes combinatoris que es basa en una àmplia gamma de tècniques d'intel·ligència artificial, informàtica i investigació operativa. En la programació de restriccions, els usuaris indiquen de manera declarativa les restriccions sobre les solucions factibles per a un conjunt de variables de decisió. Les restriccions difereixen de les primitives comuns dels llenguatges de programació imperatius perquè no especifiquen un pas o una seqüència de passos a executar, sinó les propietats d'una solució que cal trobar. A més de les restriccions, els usuaris també han d'especificar un mètode per resoldre aquestes restriccions. Això normalment es basa en mètodes estàndard com el retrocés cronològic i la propagació de restriccions, però pot utilitzar codi personalitzat com una heurística de ramificació específica del problema.[2]
La programació de restriccions pren les seves arrels i es pot expressar en forma de programació lògica de restriccions, que incorpora restriccions en un programa lògic. Aquesta variant de programació lògica es deu a Jaffar i Lassez, que van ampliar el 1987 una classe específica de restriccions que es van introduir a Prolog II. Les primeres implementacions de la programació lògica de restriccions van ser Prolog III, CLP(R) i CHIP.[3]
En lloc de la programació lògica, les restriccions es poden barrejar amb la programació funcional, la reescriptura de termes i els llenguatges imperatius. Els llenguatges de programació amb suport integrat per a restriccions inclouen Oz (programació funcional) i Caleidoscope (programació imperativa). Majoritàriament, les restriccions s'implementen en llenguatges imperatius mitjançant conjunts d'eines de resolució de restriccions, que són biblioteques separades per a un llenguatge imperatiu existent.[4]
Programació lògica de restriccions[modifica]
La programació de restriccions és una incrustació de restriccions en un llenguatge amfitrió. Els primers llenguatges d'amfitrió utilitzats van ser els llenguatges de programació lògica, de manera que el camp es va anomenar inicialment programació lògica de restriccions. Els dos paradigmes comparteixen moltes característiques importants, com ara variables lògiques i retrocés. Avui dia, la majoria de les implementacions de Prolog inclouen una o més biblioteques per a la programació lògica de restriccions.[5]
La diferència entre ambdós rau principalment en els seus estils i enfocaments per modelar el món. Alguns problemes són més naturals (i, per tant, més senzills) per escriure com a programes lògics, mentre que alguns són més naturals per escriure com a programes de restricció.
L'enfocament de la programació de restriccions és buscar un estat del món en el qual es compleixin un gran nombre de restriccions alhora. Normalment, un problema s'enuncia com un estat del món que conté una sèrie de variables desconegudes. El programa de restriccions cerca valors per a totes les variables.
La programació de restriccions concurrents temporals (TCC) i la programació de restriccions concurrents temporals no deterministes (MJV) són variants de la programació de restriccions que poden fer front al tem
Referències[modifica]
- ↑ Rossi, Francesca. Handbook of Constraint Programming (en anglès). Elsevier, 2006-08-18. ISBN 9780080463803.
- ↑ «Constraint Optimization | OR-Tools» (en anglès). [Consulta: 14 abril 2024].
- ↑ «Overview of constraint programming — IBM® Decision Optimization CPLEX® Modeling for Python (DOcplex) V2.25 documentation» (en anglès). [Consulta: 14 abril 2024].
- ↑ Harder, Hennie de. «Constraint Programming Explained» (en anglès), 12-01-2023. [Consulta: 14 abril 2024].
- ↑ «What Is Constrained Optimization?» (en anglès). [Consulta: 14 abril 2024].