SWI-Prolog CLPFD [英] SWI-Prolog CLPFD

问题描述

我是约束编程的 prolog 新手.我有一个 CLPFD 没有像我期望的那样减少域的问题.这可能真的很简单.

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

我希望它将 A 和 B 的域减少到

1\/5

但它只是给了

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

如有任何建议，我们将不胜感激.

解决方案

虽然这个答案是为 clpfd 在 swi-prolog，想法/方法是可移植的.

<预>:- use_module(图书馆(clpfd)).

以下是我们如何在开始完整枚举之前减小域大小:

shave_zs(Zs) :-地图列表(flag_zs_shave_z(F，Zs)，Zs)，一次((var(F)；地面(Zs)；shave_zs(Zs))).flag_zs_shave_z(Flag, Zs, Z) :-( fd_size(Z, sup)->true % 从不刮无限;fd_dom(Z, Z_dom),短语(dom_integers_(Z_dom)，Z_vals)，地图列表(flag_zs_z_val(标志，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,标志 = 真;真的).

我们使用语法 dom_integers_//1，定义在 SWI-Prolog clpfd 手册页:

dom_integers_(I) -->{整数(I)}，[I].dom_integers_(L..U) -->{ numlist(L, U, Is) }, Is.dom_integers_(D1\/D2) -->dom_integers_(D1), dom_integers_(D2).

示例查询:

?- [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.

I'm new to prolog for constraint programming. I have an issue with CLPFD not reducing a domain as I expect it to. This is probably really simple.

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

I expect it to reduce the domain of A and B to

1\/5

But it just gives

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

Any suggestions would be appreciated.

解决方案

While this answer is tailored to clpfd as implemented in swi-prolog, the idea/method is portable.

:- use_module(library(clpfd)).

Here's how we can reduce domain sizes before starting full enumeration:

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
   ).

We use grammar dom_integers_//1, as defined on the SWI-Prolog clpfd manual page:

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).

Sample queries:

?- [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.

这篇关于SWI-Prolog CLPFD的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！