ECLECLiiPSPSee
CLP CLP -- Constraint
Constraint Logic
Logic Programming
Programming
ECLECLiiPSPSee
Herramienta open
Herramienta open--source
útil para modelar problemas de satisfacción de restricciones:
útil para modelar problemas de satisfacción de restricciones:
de CLP [Constraint
Constraint Logic
source de CLP [
Logic Programming
Programming]]
http://www.eclipse--clp.org
http://www.eclipse
clp.org
Computer--Industry
European Computer
Historia
Historia
1991
1991 –– European
1999
1999 –– ParcParc Technologies (spin
2001
2001 –– Biblioteca
2004
2004 –– Adquisición de
Industry Research
Research Centre (ECRC),
Centre (ECRC), Munich
Munich
College, Londres)
, Londres)
Technologies (spin--off del Imperial
off del Imperial College
Biblioteca icic (propagación de restricciones)
(propagación de restricciones)
Adquisición de ParcParc Technologies por parte de Cisco
Technologies por parte de Cisco Systems
Systems
11
ECLECLiiPSPSee
PROLOG
PROLOG
Elementos del lenguaje
Elementos del lenguaje
Búsqueda en PROLOG: Backtracking
Búsqueda en PROLOG: Backtracking
Satisfacción de restricciones en PROLOG
Satisfacción de restricciones en PROLOG
ECLECLiiPSPSee
ECLECLiiPSPSee
Satisfacción de restricciones en ECLECLiiPSPSee
Satisfacción de restricciones en
Elementos del lenguaje: arrays
Elementos del lenguaje:
La biblioteca suspend
La biblioteca
suspend
Las bibliotecas sdsd & & icic
Las bibliotecas
Estrategias de búsqueda
Estrategias de búsqueda
arrays e e iteradores
iteradores..
22
PROLOG Satisfacción de restricciones
PROLOG
Satisfacción de restricciones
Los problemas de satisfacción de restricciones pueden
Los problemas de satisfacción de restricciones pueden
representarse mediante programas lógicos:
representarse mediante programas lógicos:
Problema
PSR
• Desigualdad triangular: La
• Desigualdad triangular: La
suma de las longitudes de
cualesquiera 2 lados no es
menor que la del tercero.
x
y
z
• Variables: X,Y,Z
• Variables: X,Y,Z
• Dominios: [0,inf)
• Restricciones
• X+Y>=Z
• X+Z>=Y
• Y+Z>= X
33
PROLOG Satisfacción de restricciones
PROLOG
Satisfacción de restricciones
Los problemas de satisfacción de restricciones pueden
Los problemas de satisfacción de restricciones pueden
representarse mediante programas lógicos:
representarse mediante programas lógicos:
PSR
Programa Lógico
• Variables: X,Y,Z
• Variables: X,Y,Z
• Dominios: [0,inf)
• Restricciones
• X+Y>=Z
• X+Z>=Y
• Y+Z>= X
• triangular(X,Y,Z)
• triangular(X,Y,Z)
:-
X>0 AND Y>0 AND Z>0
AND
X+Y>=Z AND X+Z>=Y AND Y+Z>=X
44
PROLOG Satisfacción de restricciones
PROLOG
Satisfacción de restricciones
Un programa lógico puede interpretarse como una base
Un programa lógico puede interpretarse como una base
de conocimiento (hechos y reglas) sobre la que se
de conocimiento (hechos y reglas) sobre la que se
realizan consultas
realizan consultas
Programa Lógico
El programa lógico termina con
El programa lógico termina con
El programa lógico termina con
El programa lógico termina con
Una respuesta “Sí”/”No”
Una respuesta “Sí”/”No”
en función de si se puede
en función de si se puede
deducir la consulta de la
deducir la consulta de la
base de conocimiento.
base de conocimiento.
Una sustitución de variables
Una sustitución de variables
que la hace cierta.
que la hace cierta.
• triangular(X,Y,Z):-
X>0 AND Y>0 AND Z>0 AND X+Y>=Z
AND X+Z>=Y AND Y+Z>=X
AND X+Z>=Y AND Y+Z>=X
Consulta
• triangular(3,4,5)?
Respuesta: Sí
• triangular(8,1,2)?
Respuesta: No
• triangular(3,4,Z)?
Respuesta: Z = [1..7]
55
PROLOG
PROLOG
Ejemplo
Ejemplo
REGLAS
REGLAS
HECHOS
HECHOS
ancestro(X,Y) :-- padre(X,Y).
ancestro(X,Y) :
padre(X,Y).
ancestro(X,Y) :-- padre(Z,Y), ancestro(X,Z).
ancestro(X,Y) :
padre(Z,Y), ancestro(X,Z).
homer).).
padre(abe,
padre(abe, homer
padre(abe, herbert
padre(abe,
herbert).).
padre(
homer, , bartbart).).
padre(homer
padre(
padre(margemarge, , bartbart).).
66
PROLOG
PROLOG
Consulta
Consulta
ancestro(
ancestro(X,bart
X,bart). ).
ancestro(X,Y) :-- padre(X,Y).
ancestro(X,Y) :
padre(X,Y).
ancestro(X,bart)
padre(X,Y)
Y=bart
padre(Z,X),
ancestro(Y,Z)
X=bart
padre(X,bart)
X=homer
padre(X,bart)
X=marge
Padre(Z,bart),
ancestro(Y,Z)
Z=homer
Padre(marge,bart),
ancestro(Y,marge)
ancestro(X,Y) :
ancestro(X,Y) :-- padre(Z,Y), ancestro(X,Z).
padre(Z,Y), ancestro(X,Z).
padre(abe,
homer).).
padre(abe, homer
padre(abe, herbert
padre(abe,
herbert).).
padre(
homer, , bartbart).).
padre(homer
padre(
padre(margemarge, , bartbart).).
Success
X=homer
Success
X=marge
Padre(Z,bart)
Z=homer
Success
Padre(abe,homer)
Y=abe
Success
X=abe
Ancestro(Y,Z)
Z=homer
Padre(Y,marge)
Padre(Y,marge),
ancestro(Z,Y)
Padre(abe,homer),
ancestro(Z,abe)
Fail
Fail
Padre(abe,homer)
Success
Ancestro(Z,abe)
Fail
77
PROLOG -- Aritmética
PROLOG
Aritmética
Operadores predefinidos para aritmética básica:
Operadores predefinidos para aritmética básica:
+, +, --,*,
,*, divdiv, , modmod, ^,
, ^, -- (unario),
(unario), absabs
Si no se especifica lo contrario, los operadores son como cualquier
Si no se especifica lo contrario, los operadores son como cualquier
otra relación (predicado)
otra relación (predicado)
X = 1+2.
X = 1+2.
Respuesta: X=1+2 % X unificado al término +(1,2)
Respuesta: X=1+2 % X unificado al término +(1,2)
Respuesta: X=1+2 % X unificado al término +(1,2)
Respuesta: X=1+2 % X unificado al término +(1,2)
El operador “
El operador “isis” fuerza la evaluación de expresiones aritméticas:
” fuerza la evaluación de expresiones aritméticas:
A A isis B B evalúa B a un número y unifica el resultado con A.
evalúa B a un número y unifica el resultado con A.
X X isis 1+2.
1+2.
Respuesta: X = 3
Respuesta: X = 3
Los operadores de comparación fuerzan también la evaluación
Los operadores de comparación fuerzan también la evaluación
145 * 34 > 100.
145 * 34 > 100.
Respuesta: Yes.
Respuesta: Yes.
88
PROLOG -- Comparación
PROLOG
Comparación
Operadores
Operadores
= vs. =:=
= vs. =:=
X > Y
X < Y
X >= Y
X =< Y
X es mayor que Y
X es menor que Y
X es mayor o igual que Y
X es menor o igual que Y
X =:= Y
Los valores de X e Y son iguales
X =\= Y
Los valores de X e Y no son iguales
unificación de X e Y
de X e Y
puede queque la la instanciación
instanciación de de
X=Y
X=Y
causa
causa la la unificación
(y (y puede
variables)
variables)
X =:= Y
X =:= Y
X =:= Y
X =:= Y
causa
causa unauna evaluación
X e Y (
X e Y (peropero no no puede
instanciación de variables)
instanciación
de variables)
evaluación aritmética
lugar a a
puede dardar lugar
aritmética de de
1 + 2 =:= 2 + 1.
> Yes
1 + 2 = 2 + 1.
> No
1 + A = B + 2.
> A = 2
> B = 1
1+A =:= B+2.
> Error (variables no instanciadas)
X is Y + 1
> Error (variable no instanciada)
Y=0, X is Y + 1.
> X = 1
X = 0, X is X + 1
> No.
No se puede unificar X con X + 1.
X = 0, X1 is X + 1.
> Yes. X = 0, X1 = 1.
99
PROLOG -- Listas
PROLOG
Listas
[a, [1,2,3],tomtom, 1995, fecha(1,mayo,1995)]
[a, [1,2,3],
, 1995, fecha(1,mayo,1995)]
Lista vacía: []
Lista vacía: []
Lista = [Cabeza | Cola]
Lista = [Cabeza | Cola]
Cabeza: primer elemento de la lista.
Cabeza: primer elemento de la lista.
Cabeza: primer elemento de la lista.
Cabeza: primer elemento de la lista.
Cola: Una lista formada por el resto de la lista.
Cola: Una lista formada por el resto de la lista.
[X|Y] = [a,b,c
[X|Y] = [
a,b,c]]
> X=a, Y=[
> X=a, Y=[b,cb,c]]
Representan a la misma lista:
Representan a la misma lista:
[[a,b,c
a,b,c] = [a| [
] = [a| [b,cb,c]] = [a, b |[c]] = [
]] = [a, b |[c]] = [a,b,c
a,b,c | []]
| []]
1010
PROLOG -- Listas
PROLOG
Listas
Ejemplos
Ejemplos
Miembro de una lista
Miembro de una lista
member(X, [
X|Tail]).]).
member(X, [X|Tail
member(X, [Head | Tail]) :
member(X, [Head | Tail]) :-- member(
member(X, [Head | Tail]) :
member(X, [Head | Tail]) :-- member(
member(X,Tail
member(X,Tail
X,Tail).).
X,Tail).).
Concatenación de listas
Concatenación de listas
append([],L,L).
append([],L,L).
append([X|L1], L2, [
append([X|L1], L2, [X|Result
X|Result]) :]) :-- append(L1,L2,Result).
append(L1,L2,Result).
1111
PROLOG -- Listas
PROLOG
Listas
Ejemplos de uso
Ejemplos de uso
a,b,c] ).] ).
a,b,c], [1,2,3], L).
], [1,2,3], L).
append( [
append( [a,b,c
> L = [a,b,c,1,2,3]
> L = [a,b,c,1,2,3]
append( L1, L2, [a,b,c
append( L1, L2, [
> L1 = [], L2 = [
> L1 = [], L2 = [a,b,c
> L1 = [], L2 = [
> L1 = [], L2 = [a,b,c
a,b,c];];
a,b,c];];
> L1 = [a], L2 = [
> L1 = [a], L2 = [b,cb,c];];
> L1 = [a,ba,b], L2 = [c];
> L1 = [
], L2 = [c];
> L1 = [
> L1 = [a,b,c
a,b,c], L2 = [];
], L2 = [];
> no> no
append( Before, [4|After], [1,2,3,4,5,6,7]).
append( Before, [4|After], [1,2,3,4,5,6,7]).
> Before = [1,2,3], After = [5,6,7]
> Before = [1,2,3], After = [5,6,7]
append(_, [
append(_, [PredPred, 4,
> > PredPred = 3, = 3, SuccSucc = 5= 5
, 4, SuccSucc |_], [1,2,3,4,5,6,7]).
|_], [1,2,3,4,5,6,7]).
PROLOG Ejemplos
PROLOG
Ejemplos
Selección de valores dentro de un rango definido:
Selección de valores dentro de un rango definido:
select_val(4,6,Val)
Min=<Max,
Val is Min
(Val = 4)
Min < Max,
Min1 is Min(4) +1,
Min1 is Min(4) +1,
select_val(5,6,Val)
Min=<Max,
Val is Min
(Val=5)
Min < Max,
Min1 is Min(5) +1,
select_val(6,6,Val)
select_val((Min,Max,Val
% % select_val
% variable Val en el rango [
% variable Val en el rango [Min,Max
Min,Max,Val) selecciona un valor para la
) selecciona un valor para la
Min,Max], ambos incluidos
], ambos incluidos
select_val
select_val((Min,Max,Val
select_val
select_val((Min,Max,Val
Min,Max,Val) :) :-- Min =< Max, Val
Min,Max,Val) :) :--
Min < Max, Min1
Min < Max, Min1 isis Min + 1,
Min + 1,
select_val(Min1,Max,Val).
select_val
(Min1,Max,Val).
Min =< Max, Val isis Min.Min.
1212
Min=<Max,
Val is Min
Val is Min
(Val = 6)
Min < Max,
FALLO!
1313
PROLOG Satisfacción de restricciones
PROLOG
Satisfacción de restriccione
Comentarios de: ECLiPSe - Constraint Logic Programming (0)
No hay comentarios