SWI-Prolog CLPFD

Question

Soy nuevo en Prolog para la programación de restricciones. Tengo un problema con CLPFD que no reduce un dominio como espero. Esto es probablemente muy simple.

 [A,B] ins 1..5,A*B#=5.

Espero que reduzca el dominio de A y B a

1//5

Pero solo da

A in 1..5,
A*B#=5,
B in 1..5.

Cualquier sugerencia sera apreciada.

Answer 1

Tienes razón de que 1//5 sería una poda óptima en este caso.

Sin embargo, por razones de eficiencia, los sistemas CLP (FD) típicamente mantienen solo la llamada consistencia de límites para las restricciones aritméticas, y en general no eliminan los elementos interiores de los dominios incluso cuando algunos de ellos no pueden participar en las soluciones.

La consistencia de los límites , en el caso finito, significa que hay soluciones donde la variable asume los límites inferior y superior del dominio. En este caso, hay soluciones para A=1 y A=5 .

Tenga en cuenta que estas son las únicas soluciones en este caso concreto, pero en general, también hay soluciones con puntos interiores en instancias análogas más grandes, por ejemplo:

?- [A,B] ins 1..10, A*B#=10, label([A,B]). A = 1, B = 10 ; A = 2, B = 5 ; A = 5, B = 2 ; A = 10, B = 1.

Sin embargo, la buena noticia es que el número de dichas soluciones solo crece de forma logarítmica en el tamaño del dominio:

?- length(_, Exp), N #= 2^Exp, [A,B] ins 1..N,A*B#=N,
   findall(., label([A,B]), Ls), length(Ls, L),
   writeln(Exp-L), false.
0-1
1-2
2-3
3-4
4-5
5-6
6-7
7-8
etc.

Esto contrasta con otros casos, como X mod 2 #= 0 , donde el número de soluciones crece linealmente en el tamaño del dominio de X (y, por tanto, exponencialmente en la longitud de su representación decimal), y por lo tanto no es factible para podar el dominio explícitamente

Por lo tanto, como una solución factible, puede usar label/1 para obtener soluciones concretas, y luego usar in/2 restricciones para restringir los operandos a sus dominios concretamente admisibles:

:- use_module(library(clpfd)).

stricter_domains(Vs) :-
        findall(Vs, label(Vs), Sols0),
        transpose(Sols0, Sols),
        maplist(list_to_domain, Sols, Ds),
        maplist(in, Vs, Ds).

list_to_domain([L|Ls], Dom) :- foldl(dom_disj, Ls, L, Dom).

dom_disj(D0, I, D0//I).

Tu ejemplo:

?- [A,B] ins 1..5, A*B#=5, stricter_domains([A,B]). A in 1//5, A*B#=5, B in 1//5.

Answer 2

Si bien esta respuesta se adapta a clpfd tal como se implementa en swi-prolog , la idea / método es portátil.

:- use_module(library(clpfd)).

Así es como podemos reducir los tamaños de dominio antes de comenzar la enumeración completa :

shave_zs(Zs) :-
   maplist(flag_zs_shave_z(F,Zs), Zs),
   once((var(F) ; ground(Zs) ; shave_zs(Zs))).

flag_zs_shave_z(Flag, Zs, Z) :-
   (  fd_size(Z, sup)
   -> true                                    % never shave the infinite
   ;  fd_dom(Z, Z_dom),
      phrase(dom_integers_(Z_dom), Z_vals),
      maplist(flag_zs_z_val(Flag,Zs,Z), Z_vals)
   ).

flag_zs_z_val(Flag, Zs, Z, Z_val) :-
   (  /+ call_with_inference_limit((Z #= Z_val,labeling([],Zs)), 1000, _)
   -> Z #/= Z_val,
      Flag = true
   ;  true
   ).

Utilizamos la gramática dom_integers_//1 , tal como se define en la página de manual de clpfd de SWI-Prolog:

dom_integers_(I)      --> { integer(I) }, [I].
dom_integers_(L..U)   --> { numlist(L, U, Is) }, Is.
dom_integers_(D1//D2) --> dom_integers_(D1), dom_integers_(D2).

Consultas de muestra:

?- [A,B] ins 1..5,  A*B #= 5,  (Shaved = false ; Shaved = true, shave_zs([A,B])).
Shaved = false, A*B #= 5, A in 1..5, B in 1..5 ;
Shaved =  true, A*B #= 5, A in 1//5, B in 1//5.

?- [A,B] ins 1..10, A*B #= 10, (Shaved = false ; Shaved = true, shave_zs([A,B])).
Shaved = false, A*B #= 10, A in 1..10      , B in 1..10 ;
Shaved =  true, A*B #= 10, A in 1..2//5//10, B in 1..2//5//10.