4

我目前正在为 Prolog 中的平面布置问题编写求解器，并且标签部分存在一些问题。

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

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

X in Xinf..Xsup

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

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

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

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

希望你能帮我 ：）

4

5 回答 5

6

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

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

  1. 变量选择：从所有剩余的（即尚未实例化的）问题变量中，选择一个来考虑下一个。
  2. 值选择或分支：通过回溯，通过以（通常）互补方式减少所选变量的域来探索两个或多个替代子问题。

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

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以实现“第一次失败”等技术，并重新定义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现在可以使用 uninstantiated 成功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
    ).
于 2016-03-28T16:01:57.213 回答
4

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

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

一个好的建筑黑色是dom_integers/2，将有限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).

示例查询和结果：

?- 短语（outside_in（[1,2,3,4]），是）。
是 = [1, 4, 2, 3] ;
错误的。

将其与fd_dom/2and结合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。

于 2016-03-28T11:13:55.253 回答
4

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

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

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

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

于 2016-03-28T11:26:22.213 回答
3

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

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

因此，此答案指向您首先确保实际终止您的关系。

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

  1. 第一个，称为核心关系，简单地发布所有约束。
  2. 第二个用于labeling/2执行实际搜索。

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

?- solution(Instance, Vs), false.

如果这终止，则以下也终止：

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

当然，在较大的任务中，您没有机会实际见证后一个查询的终止，但有机会见证第一个查询的终止，因为设置约束通常比实际获得单个解决方案要快得多.

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

于 2016-03-28T11:33:59.390 回答
1

这是@mat 之前的回答的后续。

如果您有更多的 CPU 周期要消耗，请按照上一个答案shave_zs/1中的定义尝试。

shave_zs/1像辅助库谓词这样的作品clpfd:contracting/1。contracting/1然而，与 不同的是，所有值都是“可供选择的”——不仅仅是边界处的值。YMMV！

于 2016-04-02T01:05:25.147 回答