更改列表域swi-prolog clpfd

Question

我正在使用带有clpfd库的SWI-Prolog。问题是，我用1..2^(N-1)中的项目生成了一个length N列表，约束该列表具有某些属性，并计算验证约束的最大值。在那之后，我必须找到这些最大值的最小值，但有太多的情况需要评估，Prolog结束要冻结。

maxConstrain(N,Max) :-
   listN(List,N),
   label(List),
   constrain(List),
   max_list(List,Max).

minMaxConstrain(N,M) :-
   findall(Max,maxConstrain(N,Max),Maxs), min_list(Maxs,M).

listN(-List,+N)在1..2^(N-1)中生成包含N项的列表。

如果maxConstrain(+N,-Max)验证了约束，它会给出List的最大值。

在maxConstrain(N,Max)的所有评估中，minMaxConstrain(+N,-M)给出了最少的评估。

因为我需要最大值的最小值，所以每当我找到一个最大值小于原始列表的有效列表时，我就想缩小列表的域。例如，如果我有N=4，那么列表的元素将是1..8格式的。假设我得到两个列表List1和List2，分别具有最大的8和7。现在我知道包含8的所有其他有效列表都将被拒绝，因为我发现List2的最大值=7小于8。所以我的想法是，每当我找到一个比之前更小的最大值时，就重新设置域的范围。例如，如果当前域是1..Max1，然后我找到了Max2 < Max1，那么我会将该域设置为1..Max2。

有可能做到这一点吗？

Answer 1

你所描述的想法就是branch-and-bound算法所做的:你修剪搜索的那些部分，这些部分不可能产生比你到目前为止找到的最好的解决方案更好的解决方案。约束解算器通常以某种形式提供此功能。

例如，在ECLiPSe中，这是由library(branch_and_bound)提供的，您可以将您的问题表述为

:- lib(ic).
:- lib(branch_and_bound).

min_of_max(N, Max) :-
    length(Xs, N),
    Xs #:: 1..2^(N-1),
    constrain(Xs),
    Max #= max(Xs),
    bb_min(labeling(Xs), Max, _).

通过围绕labeling/1搜索例程包装bb_min/3调用，任何创建其最大值大于或等于到目前为止找到的最小最大值的列表的尝试都将导致失败。默认情况下，这是通过动态降低Max的上限来实现的(类似于您在问题中概述的过程)，但也可以使用其他策略选项。