Programación con restricións

A programación con restricións é un paradigma da programación en informática, onde as relacións entre as variables son expresadas en termos de restricións (ecuacións). Actualmente é usada como unha tecnoloxía de software para a descrición e resolución de problemas combinatorios particularmente difíciles, especialmente nas áreas de planificación e programación de tarefas (calendarización).

Este paradigma representa un dos desenvolvementos máis fascinantes nas linguaxes de programación desde 1990 e non é sorprendente que recentemente ^[cando?] sexa identificada pola ACM (Asociación de Maquinaria Computacional) como unha dirección estratéxica na investigación en computación.

Trátase dun paradigma de programación baseado na especificación dun conxunto de restricións, as cales deben ser satisfeitas por calquera solución do problema exposto, no canto de especificar os pasos para obter a devandita solución.

A programación con restricións relaciónase moito coa programación lóxica e coa investigación operativa. De feito calquera programa lóxico pode ser traducido nun programa con restricións e viceversa. Moitas veces os programas lóxicos son traducidos a programas con restricións debido a que a solución é máis eficiente que a súa contraparte.

A diferenza entre ambos radica principalmente nos seus estilos e enfoques no modelado do mundo. Para certos problemas é máis natural (e polo tanto máis simple) escribilos como programas lóxicos, mentres que noutros é máis natural escribilos como programas con restricións.

O enfoque da programación con restricións baséase principalmente en buscar un estado no cal unha gran cantidade de restricións sexan satisfeitas simultaneamente. Un problema defínese tipicamente como un estado da realidade no cal existe un número de variables con valor descoñecido. Un programa baseado en restricións busca os valores para todas as variables.

Algúns dominios de aplicación deste paradigma son:

• Dominios booleanos, onde só existen restricións do tipo verdadeiro/falso.
• Dominios en variables enteiras e racionais.
• Dominios lineais, onde só se describen e analizan funcións lineais.
• Dominios finitos, onde as restricións son definidas en conxuntos finitos.
• Dominios mixtos, os cales involucran dous ou máis dos anteriores.

As linguaxes de programación con restricións son tipicamente ampliacións doutra linguaxe. A primeira linguaxe utilizada para ese efecto foi Prolog. Por esta razón é que este campo foi chamado inicialmente Programación Lóxica con Restricións. Ambos os paradigmas comparten características moi similares, tales como as variables lóxicas (unha vez que unha variable é asignada a un valor, non pode ser cambiado), ou o backtracking.

A programación con restricións pode ser implementada como unha linguaxe propia ou como bibliotecas para ser usadas nalgunha linguaxe de programación imperativo.

Algunhas linguaxes populares de programación con restricións son:

• B-Prolog (Baseado en Prolog , propietario)
• CHIP V5 Arquivado 02 de xaneiro de 2008 en Wayback Machine. (Baseado en Prolog, tamén existen bibliotecas en C e C++, propietario)
• Ciao Prolog^{[Ligazón morta]} (Baseado en Prolog, software libre: GPL/LGPL)
• Eclipse (Baseado en Prolog, propietario)
• Mozart (Baseado en Oz, software libre: X11)
• SICStus (Baseado en Prolog, propietario)
• GNU Prolog (Baseado en Prolog, software libre)
• SWI Prolog (unha contorna Prolog que contén varias librerías para solucións con restricións (LGPL))

Algunhas bibliotecas populares:

• Choco (Java, software libre: X11)
• Disolver (C++, propietaria)
• Gecode (C++ ,software libre: X11)
• ILOG CP (C++, propietaria)
• Koalog Constraint Solver (Xava, propietaria)

• Guía de Constraint Programming^{[Ligazón morta]} (en inglés)
• Que é Programación con Restricións?^{[Ligazón morta]} (en castelán)
• Mozart-oz