Prolog 手册或自定义标签

Question

我目前正在为 Prolog 中的平面规划问题编写求解器，但在标签部分遇到了一些问题。

当前的问题是我的约束已发布，但是当我启动标签时，它需要很长时间才能找到解决方案。我想引入一些启发式方法。

我的问题是，如何手动标记我的变量？恐怕在这样定义一个 clpfd 变量之后：

X in Xinf..Xsup

并限制它，如果我做类似的事情：

    fd_sup(X, Xmax),
    X = Xmax,
...

在我的自定义标签中，我不会使用 Prolog 的回溯能力来测试 X 域的其他值。我错了吗？

还有，有没有比编写自定义标记程序更聪明的方法来标记我的变量？我的启发式想法包括交替尝试变量域的极值（如 max(X)、min(X)、max(X-1)、min(X-1) 等...）

希望你能帮助我:)

Answer 1

首先，始终尝试内置启发式方法。 ff 通常是一个很好的策略。

对于自定义标签策略，最简单的方法通常是首先将域转换为列表，然后重新排序列表，然后简单地使用 member/2 使用新顺序分配域的值。

一个好的建筑黑色是 dom_integers/2，将 finite CLP(FD) 域与整数列表相关联：

:- use_module(library(clpfd)).

dom_integers(D, Is) :- phrase(dom_integers_(D), Is).

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

您的特定策略很容易在这样有序整数的列表中表达，将这些整数与第二个列表相关联，其中值按照您描述的顺序出现：

outside_in([]) --> [].
outside_in([I]) --> [I].
outside_in([First|Rest0]) --> [First,Last],
        { append(Rest, [Last], Rest0) },
        outside_in(Rest).

示例查询和结果：

?- phrase(outside_in([1,2,3,4]), Is).
Is = [1, 4, 2, 3] ;
false.

将此与 fd_dom/2 和 dom_integers/2 结合，我们得到（省略 X 以外的变量的绑定）：

?- X in 10..20,
   fd_dom(X, Dom),
   dom_integers(Dom, Is0),
   phrase(outside_in(Is0), Is),
   member(X, Is).
X = 10 ;
X = 20 ;
X = 11 ;
X = 19 ;
X = 12 ;
X = 18 ;
etc.

member/2 保留了不确定性。

Answer 2

确保将标记策略与额外的传播区分开来。这两个方面目前在你的问题中有点混杂。

在 SWI-Prolog 中，有一个叫做 clpfd:contracting/1 的谓词。它按照您的描述进行操作：它尝试来自域边界的值，并删除可以被视为 不一致 的值，即已知不存在解决方案的值。

因此，如果您有一个变量列表 Vs，您可以尝试：clpfd:contracting(Vs)，看看是否有帮助。

请注意，这也会显着降低搜索速度，但另一方面，甚至在尝试任何标记之前也有助于显着减少搜索 space！

Answer 3

为了补充其他答案（一个对比标记和传播，一个显示专用标记方法），我现在解决这个问题的另一个非常重要的方面：

很多时候，当初学者抱怨他们的代码速度时，事实证明他们的代码实际上甚至没有终止！在这种情况下，更高的效率无济于事。

因此，这个答案指出您首先要确保你们的关系真正终止。

确保 CLP(FD) 程序终止的最佳方法是将它们分成两部分：

第一个称为核心关系，只是发布所有约束。
第二个使用 labeling/2 执行实际的搜索。

你在你的程序中这样做了吗？如果没有，请做。完成后，确保核心关系，例如 solution/2（其中参数是：表示任务实例的术语，以及要标记的变量列表）通过查询普遍终止：

?- solution(Instance, Vs), false.

如果这个终止，那么以下也终止：

?- solution(Instance, Vs), label(Vs), false.

当然，在较大的任务中，你没有机会真正见证后一个查询的终止，但很有机会见证第一个查询的终止，因为设置约束往往比实际要快得多甚至获得一个单一的解决方案。

因此，测试你的核心关系是否终止！

Answer 4

编写自定义标记程序并不困难，对于大多数实际问题，您最终还是需要一个程序来结合特定问题的启发式方法。

标记程序的两个主要组成部分是

变量选择：从所有剩余的（即尚未实例化的）问题变量中，选择一个进行下一步考虑。
值选择或分支：通过回溯探索两个或更多备选子问题，方法是将所选变量的域减少到 (通常）互补的方式。

使用这个方案，默认的标注过程可以写成

label(Xs) :-
    ( select_variable(X, Xs, Xs1) ->
         branch(X),
         label(Xs1)
    ;
         true    % done, no variables left
    ).

select_variable(X, [X|Xs], Xs).     % 'leftmost' strategy

branch(X) :- indomain(X).

您现在可以重新定义 select_variable/3 以实现 "first-fail" 等技术，并重新定义 branch/1 以不同顺序尝试域值。只要您确保 branch/1 在回溯时枚举了所有 X 的域值，您的搜索就会保持完整。

有时您只想先尝试一个域值（例如，启发式建议的值），但是，如果它不好，请不要立即提交另一个值。假设在您的示例中，您想首先尝试最大域值。你可以写成

branch(X) :-
    fd_sup(X, Xmax),
    (
         X = Xmax           % try the maximum
    ;
         X #\= Xmax         % otherwise exclude the maximum
    ).

因为这两种情况是互补的并且涵盖了 X 的所有可能值，所以您的搜索仍然是完整的。但是，由于第二种选择，branch/1 现在可以使用未实例化的 X 成功，这意味着您必须确保在标记过程中不会从列表中丢失此变量。一种可能性是：

label(Xs) :-
    ( select_variable(X, Xs, Xs1) ->
         branch(X),
         ( var(X) -> append(Xs1, [X], Xs2) ; Xs2=Xs1 ),
         label(Xs2)
    ;
         true    % done, no variables left
    ).

Answer 5

这是的后续。

如果您还有更多 CPU 个循环要燃烧，请尝试 shave_zs/1，如 this previous answer 中所定义。

shave_zs/1 类似于辅助库谓词 clpfd:contracting/1。然而，与 contracting/1 不同的是，所有值都是 "up for grabs"——而不仅仅是边界处的值。 YMMV！

Prolog 手册或自定义标签

Prolog manual or custom labeling

prolog

clpfd

labeling