我目前正在Prolog中编写一个楼层规划问题的求解器，并且在标签部分遇到了一些问题。
目前的问题是，我的约束条件已经发布，但当我启动标签时，需要很长时间才能找到解决方案。我想引入一些启发法。
我的问题是，如何手动标记变量？恐怕在定义了这样一个clpfd变量之后：
X in Xinf..Xsup
并约束它，如果我做一些类似的事情：
fd_sup(X, Xmax),
X = Xmax,
...
在我的自定义标签中，我不会使用Prolog的回溯功能来测试X域的其他值。我错了吗？
此外，有没有比编写自定义标记过程更聪明的方法来标记我的变量？我的启发式思想包括交替尝试变量域的极值（如max（X）、min（X），max（X-1）、min
希望你能帮助我：）
编写一个自定义标记过程并不困难，对于大多数实际问题，你最终都需要一个，以便结合特定问题的启发式方法。
标签程序的两个主要组成部分是
- 变量选择：从所有剩余的（即尚未实例化的）问题变量中，选择一个来考虑下一个
- 值选择或分支：通过回溯，以（通常）互补的方式减少所选变量的域，探索两个或多个备选子问题
使用此方案，默认标记程序可以写成
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现在可以使用未实例化的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
).
首先，一定要尝试内置的启发式方法。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，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保留了非确定性。
确保将标记策略与其他传播区分开来。这两个方面目前在你的问题中有点混淆。
在SWI-Prolog中，有一个谓词clpfd:contracting/1。它执行您所描述的操作：它尝试域边界中的值，并删除可以被视为不一致的值，即已知不存在解决方案的值。
因此，如果您有一个变量Vs的列表，您可以尝试：clpfd:contracting(Vs)，看看这是否有帮助。
请注意，这也会显著减慢搜索速度，但另一方面，也有助于在尝试任何标记之前显著减少搜索空间！
为了补充其他答案（一个对比标记和传播，一个显示专用标记方法），我现在解决这个问题的另一个非常重要的方面：
很多时候，当初学者抱怨他们的代码速度太快时，事实证明他们的代码甚至没有终止！在这种情况下，提高效率无济于事。
因此，这个答案指向您首先确保您的关系实际终止。
确保CLP（FD）程序终止的最佳方法是将它们分为两部分：
- 第一个称为核心关系，只是发布所有约束
- 第二个使用CCD_ 18来执行实际的搜索
你在你的节目中做到了吗？如果没有，请这样做。完成此操作后，请确保核心关系，例如solution/2（参数为：表示任务实例的术语和要标记的变量列表）通过查询普遍终止
?- solution(Instance, Vs), false.
如果终止，则以下也结束：
?- solution(Instance, Vs), label(Vs), false.
当然，在较大的任务中，您没有机会实际见证后一个查询的终止，但很有机会见证第一个查询的结束，因为设置约束通常比实际获得单个解决方案快得多。
因此，测试您的核心关系是否终止！
这是@mat之前的回答。
如果您还有更多的CPU周期要消耗，请尝试前面答案中定义的shave_zs/1。
CCD_ 23的工作原理类似于辅助库谓词CCD_。然而，与contracting/1不同，所有值都是"可供争夺的"—不仅仅是边界上的那些。YMMV！