1

鉴于这个小例子：

go:-
  length( X, 200 ),
  domain( X, 1, 25),

  postConstraints( X, Y ),

  labeling( [minimize(Y), X ).

如果我们假设postConstraints设置了一些复杂的约束。Y 从postConstraints标签返回并用作成本函数。

我们假设我们对 设置的约束没有（或很少）知识postConstraints。但我们知道最优解（或一个好的解）将是 X 包含或多或少均匀分布的可能域。即值 1 将出现大约 8 (200/25) 次，2 将出现大约 8 次，依此类推。

但是我们不知道每个值会出现在什么位置。

如果我们从使用默认标签开始，X 将首先被分配只有 1，这是一个解决方案，但不是一个好的解决方案（高 Y）。通过长时间运行搜索，将找到最佳解决方案，这是在可能的域上或多或少均匀分布。

这意味着搜索需要很长时间才能从第一个可能的解决方案到最佳（或更好）的解决方案。

我认为如果可以在标记之前对 X 应用初始“猜测”，那么搜索会更快。前任。如果 X 填充了来自域的随机值？在 Sicstus 有没有办法做到这一点？这是你用value(Enum)的地方labeling吗？

4

2 回答 2

1

你的问题没有具体的例子，所以很难给出具体的建议。但是，您可以先考虑标签选项ff。至少有一个简单的原因：添加预定义的标签选项可能会影响运行时间，但不会影响正确性。更复杂的方法总是有引入错误的风险。

谓词labeling/2提供了两种预定义的方式来枚举选定变量的值：（up默认）和down. 要从不同的值开始，您可以将一个变量映射到另一个再次使用内置枚举之一的变量。定义自己的枚举方法是可能的，但绝对不是初学者的任务。事实上，甚至library/clpfd/examples/没有提供一个例子。

为了说明如何以不同方式枚举变量，我将使用单个变量X：

| ?- X in 1..5, labeling([],[X]).
X = 1 ? ;
X = 2 ? ;
X = 3 ? ;
X = 4 ? ;
X = 5 ? ;
no
| ?- X in 1..5, labeling([down],[X]).
X = 5 ? ;
X = 4 ? ;
X = 3 ? ;
X = 2 ? ;
X = 1 ? ;
no

现在我们要从X值 3 开始。因此X映射到Xx将在标签中使用的值：

| ?- X in 1..5, Xx #= (X+5-3)mod 5,labeling([],[Xx]).
X = 3,
Xx = 0 ? ;
X = 4,
Xx = 1 ? ;
X = 5,
Xx = 2 ? ;
X = 1,
Xx = 3 ? ;
X = 2,
Xx = 4 ? ;
no

通过这种方式，您可以将每个变量映射到其他一些初始值。或者都一样。但是请注意，由于 的一致性相对较弱(mod)/2，因此无法立即看到原始变量中存在的所有信息。ff如果您使用动态检查域的选项，这反过来可能会恶化标签：

| ?- assert(clpfd:full_answer).
yes
| ?- X in 1..5, Xx #= (X+5-3)mod 5, X #\= 2.
clpfd:(_A#=X+2),
clpfd:(_A mod 5#=Xx),
X in{1}\/(3..5),
_A in{3}\/(5..7),
Xx in 0..4 ? ;
no

因此，这里的域Xx尚未更新为0..3，尽管：

| ?- X in 1..5, Xx #= (X+5-3)mod 5, X #\= 2, Xx = 4.
no

非常智能的默认选项step也同样受到影响。

于 2014-06-27T09:37:30.917 回答
0

您说好的解决方案将“在可能的域上或多或少地分布均匀”，我认为这意味着所有域值将在解决方案向量中出现相似的次数。

在这种情况下，您可以引入一个辅助变量，以某种方式测量变量分配的启发式质量。然后，您首先标记此辅助变量，然后再标记其他变量来开始搜索。这样，可以首先检查潜在的好分配。

我没有 SICStus，但这里有一个ECLiPSe示例，应该很容易适应。我引入了约束来计算不同域值在主变量向量1中出现的频率。然后在变量 中计算计数变量的不平衡，这是首先被标记的变量（从值 0 开始，即完美平衡）：NDXsNsImbalance

:- lib(ic).
:- lib(ic_global).

main(NX, ND, Xs) :-
    length(Xs,NX),
    Xs::1..ND,
    ( for(I,1,ND), foreach(N,Ns), param(Xs) do
        occurrences(I, Xs, N)    % SICStus: count(I,Xs,#=,N)
    ),
    sum(Ns) #= NX,
    Imbalance #= max(Ns) - min(Ns),
    Imbalance :: 0..NX,

    labeling([Imbalance|Xs]).

示例运行显示了如何首先枚举平衡解决方案：

?- main(4, 2, Xs), writeln(Xs), fail.
[1, 1, 2, 2]
[1, 2, 1, 2]
[1, 2, 2, 1]
[2, 1, 1, 2]
[2, 1, 2, 1]
[2, 2, 1, 1]
[1, 1, 1, 2]
[1, 1, 2, 1]
[1, 2, 1, 1]
[1, 2, 2, 2]
[2, 1, 1, 1]
[2, 1, 2, 2]
[2, 2, 1, 2]
[2, 2, 2, 1]
[1, 1, 1, 1]
[2, 2, 2, 2]
No (0.01s cpu)

您的实际问题约束可以简单地添加到此模板中。

于 2014-06-28T18:53:27.063 回答