Prolog手册或自定义标签

问题描述：

我目前正在为Prolog中的楼层规划问题编写求解程序，并且在标注部分存在一些问题。Prolog手册或自定义标签

目前的问题是我的约束被张贴，但是当我启动标签时，它需要永远找到解决方案。我想引入一些启发式。

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

X in Xinf..Xsup

，并将其约束，如果我这样做：

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

在我的自定义标签

，我不会使用回溯Prolog测试X域的其他值的能力。我错了吗？

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

希望你可以帮助我:)

手动标签？只需将实际选定的值添加到约束存储... – CapelliC

对不起，我是初学者。通过将这些值添加到限制商店，你的意思是写“X＃= Xmax”？如果是这样，这是行不通的，我想要的是或者尝试变量的域的最大值和最小值，如果它们不起作用，则从域中删除这些值这将是一种标签（[min（ X），最大（X）]，[X]），除非我不知道这是否可行，而且我有一个变量的完整列表，我想要做同样的事情 – Manfred

为了得到最好的建议，你应该显示更多你的具体问题。 – false

答

首先，总是尝试内置启发式。 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).

样品的查询和结果：

 
?- 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保留。

感谢您的回答！所以你可以通过成员/ 2过程来赋值，但我不太了解你提供的“outside_in”，特别是语法，我们在swi prolog中使用“{}”吗？否则，它看起来就像我'm正在寻找！ – Manfred

是的，这正是你所要求的，而我给出的其他答案与你肯定也应该考虑的其他方面相辅相成，并解决了你的问题中隐含的问题。关于我在这里用来描述列表的语法见[tag：dcg]，你可以使用'phrase/2'接口谓词来调用DCGs，并且确保通过@jschimpf检查答案：不要简单地使用'member/2'，最好在两个分支中发布一个由（＃=）/ 2'和'（\＃=）/ 2'组成的析取结果，以增强传播的可能性。 – mat

答

确保区分标签策略与其他传播。这两个方面目前在你的问题上有点混杂。

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

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

请注意，这也会显着减慢搜索速度，但另一方面，即使尝试进行任何标记，也可显着减少搜索空间！

感谢您的精确！收缩是否在变量的每次赋值时动态地发生，或者在一开始就以静态方式发生？因为我建立我的领域的方式应该没有不一致的价值静态的方式。无论如何，我将在旧版本的解算器上尝试使用ff策略，无需任何自定义标签！我会让你保持最新！ – Manfred

收缩只发生在您调用它时，但您当然也可以多次调用它，例如，在自定义标签期间为特定变量*调用'clpfd：contracting/1'。 – mat

但是合同的效果会随着回溯而消失吗？我的意思是，如果另一个值的变化，它会恢复变量的不一致的值吗？ – Manfred

答

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

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

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

确保CLP（FD）计划终止，最好的办法是将它们分成两个部分：

第一，被称为核心关系，简单地发布所有的约束。

第二次使用labeling/2执行实际的搜索。

您是否在您的程序中完成了这项工作？如果没有，请做。当做到这一点，确保核心关系，说solution/2（这里的参数是：表示任务实例的术语，来标记变量列表）终止普遍通过查询：

?- solution(Instance, Vs), false.

如果此结束，然后以下也终止：

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

当然，在较大的任务中，你没有机会亲眼目睹后一个查询的终止，但是有一个很好的机会见证第一个查询的终止，因为设置约束通常要比实际获得单个查询要快得多解。

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

只有在SWI的'clpfd，标签总是终止 – false

在YAP中是一样的！可能很快也可以在SICStus ... – mat

是的！我的程序建立的方式，我有一个主要的程序，叫别人发布约束，然后是一个标签程序。我试着解决小问题，并打印出解决方案，我想我应该不应该有核心关系终止问题？ – Manfred

答

编写自定义标签过程并不困难，而且对于大多数实际问题，您最终还是需要一个问题才能将特定于问题的启发式方法合并。

标记过程的两个主要组件是

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

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

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

感谢您的详细解释。我知道分支需要覆盖域的所有值，但标签过程是否需要处理每个变量？我的意思是，我可以对某些变量使用自定义标签过程，而对其他变量使用常规标签过程？我会说不，但是想确定 – Manfred

是的，您可以使用标签例程（如标签（Xs），标签（Ys））的结合。但是你应该知道，X总是在搜索树的顶部，而Y在底部。你也可以使用'my_labeling（Xs），标签（Xs）'并让'my_labeling'处理一些变量，这样剩下的变量就会被'标签'处理。标记例程应该健壮并且忽略已经实例化的变量。 – jschimpf

答

这跟在this previous answer by @mat之后。

如果您有更多CPU周期需要刻录，请尝试shave_zs/1，如this previous answer中所定义。

shave_zs/1作品类似辅助图书馆谓词clpfd:contracting/1。不像contracting/1，然而，所有值是“抢”—不只是在边界的那些。因人而异！

Prolog手册或自定义标签

相关推荐