如何在 Prolog 中创建算术和不等式约束

Question

我是 Prolog 的新手，我有兴趣将以下单词问题转换为 (SWI) Prolog：

There are 4 children: Abe, Dan, Mary, and Sue. Their ages, in no particular order, are 3, 5, 6, and 8. Abe is older than Dan. Sue is younger than Mary. Sue's age is Dan's age plus 3 years. Mary is older than Abe.

到目前为止我想出了

child(X) :-
    member(X, [3,5,6,8]).

solution(Abe, Dan, Mary, Sue) :-
    child(Abe),
    child(Dan),
    child(Mary),
    child(Sue),
    Abe > Dan,
    Sue < Mary,
    Sue == Dan+3,
    Mary > Abe,
    Abe \== Dan,
    Abe \== Mary,
    Abe \== Sue,
    Dan \== Mary,
    Dan \== Sue,
    Mary \== Sue.

但是运行查询

?- solution(Abe, Dan, Mary, Sue)

我刚刚得到 false。作为一个附带问题，Prolog 是否会执行暴力搜索解决方案，或者是否有一些机器可以比 O(n!) 更好地解决这个（某种）问题？

我要的结果是Abe = 5, Dan = 3, Mary = 9, Sue = 6.

Answer 1

由于值在 child 调用后被固定，您可以使用 is 运算符：

child(X) :-
    member(X, [3,5,6,8]).
solution(Abe, Dan, Mary, Sue) :-
    child(Abe),
    child(Dan),
    child(Mary),
    child(Sue),
    Abe > Dan,
    Sue < Mary,
    Sue is Dan+3,
    Mary > Abe,
    Abe =\= Dan,
    Abe =\= Mary,
    Abe =\= Sue,
    Dan =\= Mary,
    Dan =\= Sue,
    Mary =\= Sue.

您可以通过交错 生成和测试 来进一步提高性能，而不是先生成再测试：

child(X) :-
    member(X, [3,5,6,8]).
solution(Abe, Dan, Mary, Sue) :-
    child(Abe),
    child(Dan),
    Abe > Dan,
    Abe =\= Dan,
    child(Mary),
    Mary > Abe,
    Abe =\= Mary,
    Dan =\= Mary,
    Sue is Dan+3,
    Sue < Mary,
    child(Sue),
    Abe =\= Sue,
    Dan =\= Sue,
    Mary =\= Sue.

那么你也可以消除一些不等于谓词（=\=）因为这些是由小于（ <) 或大于 (>) 谓词；或者通过 is 谓词：

child(X) :-
    member(X, [3,5,6,8]).
solution(Abe, Dan, Mary, Sue) :-
    child(Abe),
    child(Dan),
    Abe > Dan,
    child(Mary),
    Mary > Abe,
    Dan =\= Mary,
    Sue is Dan+3,
    Sue < Mary,
    child(Sue),
    Abe =\= Sue.

尽管如此，使用约束逻辑编程 (CLP) 工具可能是解决此问题的最佳方法。

Answer 2

整数的算术约束，例如本题中的约束，最好用您的 Prolog 系统的 CLP(FD) 约束.

来表达

例如，在 SICStus Prolog、YAP 或 SWI 中：

:- use_module(library(clpfd)).

ages(As) :-
        As = [Abe,Dan,Mary,Sue],    % There are 4 children: Abe, Dan, Mary, Sue
        As ins 3\/5\/6\/8,          % Their ages are 3, 5, 6 and 8
        all_different(As),
        Abe #> Dan,                 % Abe is older than Dan
        Sue #< Mary,                % Sue is younger than Mary
        Sue #= Dan + 3,             % Sue's age is Dan's age plus 3 years
        Mary #> Abe.                % Mary is older than Abe

示例查询及其结果：

?- ages([Abe,Dan,Mary,Sue]).
Abe = 5,
Dan = 3,
Mary = 8,
Sue = 6.

我们从这个答案中看出这个谜题有一个独特的解决方案。

请注意，无需任何搜索即可获得此答案！约束求解器通过称为约束传播的强大隐式机制推导出唯一解，这是 CLP 系统相对于蛮力搜索的关键优势。在此示例中成功使用约束传播来修剪搜索树中除一个剩余分支之外的所有分支。

Answer 3

——用低级算法生成和测试——是老派:

遗留 Prolog 代码将获得所有低级程序细节的负担直接放在 you.
Debugging / optimizing legacy code often boils down to some variant of program tracing。

相比之下， wins on generality / versatility / robustness, declarativity, conciseness, efficiency, and more! How come? Luck? Genius? Divine intervention? Likely a bit of each, but the main reason is this: @mat uses superior tools. @mat uses clpfd.

好消息！ clpfd 普遍可用。使用它并获得好处：

请注意@mat 的 Prolog 代码与原始规格有多接近！
代码保留logical-purity。这有重要的后果：
- 可以使用高级调试方法（利用纯 Prolog 代码的有用代数特性）！
- 低级调试也可能，但首先探索 高级方法！

如何在 Prolog 中创建算术和不等式约束

How to create arithmetic and disequality constraints in Prolog

prolog

clpfd