为什么这个 CLP(FD) 约束求解缓慢以及如何调试它？

Question

我正在通过“代码来临”挑战来学习 Prolog。

以下是《代码降临 2021》第 7 天的剧透：

目标是：给定一个自然数列表n_1,..., n_k，找到

min_(x\in \N) \sum_i=0^k |x - n_i|

在下面的代码中norm1计算被加数，cost计算给定 处的总和x，并lowest_cost计算所有 s 的最小值x。

norm1(X, Y, N) :- N #= abs(X - Y).

cost(Nums, X, Cost) :-
    max_list(Nums, MaxX),
    min_list(Nums, MinX),
    X in MinX..MaxX,
    maplist(norm1(X), Nums, Costs),
    sum(Costs, #=, Cost).


lowest_cost(Nums, Cost) :-
    cost(Nums, X, Cost)
    once(labeling([min(Cost)], [X, Cost])).

一些示例查询：

?- lowest_cost([10,11,12], Cost).
Cost = 2.

?- cost([2,4,6,8], 4, Cost).
Cost = 8.

?- cost([2,4,6,8], 5, Cost).
Cost = 8.

?- cost([2,4,6,8], 8, Cost).
Cost = 12.

?- lowest_cost([2,4,6,8], Cost).
Cost = 8.

对于短列表，这可以正确且快速地解决它，但是当我在全长 1,000 输入上尝试它时，它会无限期地旋转。

我想象解决这个问题的方法是尝试X域中的所有方法，计算每个方法的成本，然后取最小的。但事实似乎并非如此；时间似乎与列表的长度呈超线性缩放，而与列表中的数字范围无关。

1. 我如何指示 CLP(FD) 以我描述的方式或其他有效的方式进行搜索？
2. 我怎样才能更好地理解求解器想要做什么？trace非常混乱，我不知道如何从中获得任何见解。

Answer 1

我想象解决这个问题的方法是尝试X域中的所有方法，计算每个方法的成本，然后取最小的。但事实似乎并非如此；时间似乎与列表的长度呈超线性缩放，而与列表中的数字范围无关。

你做了哪些实验才得出这个结论？

?- time(lowest_cost([0, 1000], Cost)).
% 596,377 inferences, 0.088 CPU in 0.088 seconds (100% CPU, 6799507 Lips)
Cost = 1000.

?- time(lowest_cost([0, 10000], Cost)).
% 5,933,218 inferences, 4.041 CPU in 4.041 seconds (100% CPU, 1468244 Lips)
Cost = 10000.

?- time(lowest_cost([0, 100000], Cost)).
^CAction (h for help) ? abort
% 31,000,962 inferences, 99.612 CPU in 100.751 seconds (99% CPU, 311218 Lips)
% Execution Aborted

我如何指示 CLP(FD) 以我描述的方式或其他有效的方式进行搜索？

不要隐瞒您知道必须保留的信息。正如您在评论中指出的那样，“我们总是可以选择它作为输入数字之一”，因此建模：

numbers_domain([N], N).
numbers_domain([N | Ns], N \/ Domain) :-
    numbers_domain(Ns, Domain).

cost_at_position(Nums, Pos, Cost) :-
    numbers_domain(Nums, Domain),
    Pos in Domain,
    maplist(norm1(Pos), Nums, Costs),
    sum(Costs, #=, Cost).

这样你就得到：

?- time(lowest_cost([0, 1000], Cost)).
% 5,252 inferences, 0.002 CPU in 0.002 seconds (100% CPU, 2439400 Lips)
Cost = 1000 .

?- time(lowest_cost([0, 10000], Cost)).
% 5,252 inferences, 0.002 CPU in 0.002 seconds (100% CPU, 2534299 Lips)
Cost = 10000 .

?- time(lowest_cost([0, 100000], Cost)).
% 5,252 inferences, 0.002 CPU in 0.002 seconds (100% CPU, 2952068 Lips)
Cost = 100000 .

我怎样才能更好地理解求解器想要做什么？

我从这个伟大的答案freeze/2中学到的一项技术是在约束变量上添加目标。然后，每次求解器尝试将变量绑定到具体值时，您都会收到通知。

例如：

cost_at_position(Nums, Pos, Cost) :-
    ...
    freeze(Pos, log('Pos', Pos)),
    freeze(Cost, log('Cost', Cost)).
    
log(Label, Value) :-
    write(Label), write(': '), writeln(Value).

?- lowest_cost([2,4,6,8], Cost).
Cost: 12
Pos: 2
Cost: 10
Pos: 3
Cost: 8
Pos: 4
Cost: 8
Pos: 4
Cost = 8.

我不确定它在这种特殊情况下有多大帮助，但至少您可以看到解算器尝试位置 3，该位置不会出现在输入位置中，因此（对于此成本函数）是无用的。