En primer lugar es interesante observar que la búsqueda de soluciones en Prolog es en sí misma un problema de satisfacción de restricciones: se trata de buscar valores para las variables que sean compatibles con las restricciones impuestas por las cláusulas.
Algunos problemas sencillos pueden expresarse en Prolog puro, haciendo uso de los predicados incorporados «=» , «>» , etc. Por ejemplo, para el coloreado del mapa de la Figura A.12 con tres colores podemos escribir:
color(rojo).
color(verde). color(azul). coloreado(A,B,C,D) :- satisface_restr(A,B,C,D), color(A), color(B), color(C), color(D). satisface_restr(A,B,C,D) :- noig(A,B), noig(A,C), noig(A,D), noig(B,C), noig(B,D), noig(C,D). noig(X,Y) :- X\=Y. |
Pero con el modelo procesal de Prolog que hemos estudiado no se hace uso de las podas y los heurísticos conocidos para los problemas de satisfacción de restricciones. De hecho, en este caso la conclusión de que no hay solución sólo se obtiene tras generar las 81 asignaciones. Se podría introducir la poda en el mismo programa mediante el uso de los operadores «cut» y «fail» que veremos en el Apartado A.4.4, pero entonces se perdería la ventaja de la programación declarativa.
En CLP se consideran variables con dominios finitos, y se utiliza otro operador para la restricción de desigualdad entre dos variables que : X##Y. El procesador sólo evalúa esta condición cuando una de las dos variables tiene asignado un valor, y entonces elimina ese valor del dominio de la otra. Naturalmente, es necesaria otra construcción sintáctica para declarar los dominios de las variables. En nuestro ejemplo, el programa se transforma en este otro:
color(rojo).
color(verde). color(azul). coloreado(A,B,C,D) :- [A,B,C,D]::[rojo,verde,azul], satisface_restr(A,B,C,D), color(A), color(B), color(C), color(D). satisface_restr(A,B,C,D) :- noig(A,B), noig(A,C), noig(A,D), noig(B,C), noig(B,D), noig(C,D). noig(X,Y) :- X##Y. |
El procesador ahora detecta la imposibilidad de solución tras probar sólo seis alternativas.
Los sistemas de CLP incluyen diversos predicados incorporados para la definición de dominios y para la expresión de restricciones, y en su procesador implementan técnicas y heurísticos generales para los problemas de satisfacción de restricciones, como la propagación de restricciones y la consistencia de arcos.
DIT-ETSIT-UPM
