Eclipse约束编程-- search/6

Question

我在理解eclipse约束编程框架中搜索/6函数的this文档时遇到了困难。

我知道choice参数基本上会影响值的排序。

似乎选择方法选择了变量的顺序，但我并不完全理解它的所有选项。

我真的不太了解其他参数，所以我想知道是否有人可以用语言解释它们。我对约束逻辑编程的理论有很好的理解，所以请随意参考这些概念。我只是不理解文档中的许多CS术语(a等)。

谢谢

Answer 1

我将尽可能简短地回答这个问题，因为search/6是ECLiPSe系统中可以找到的最复杂的谓词之一。

不过，任何更详细的后续问题最好在ECLiPSe用户邮件列表中提出。

CLP谓词是用于控制对search/6问题的解决方案的搜索的通用谓词。它允许用户控制搜索树的形状(分支上变量的顺序、分支的顺序以及搜索树的访问部分)。该谓词有6个参数：search(+L, ++Arg, ++Select, +Choice, ++Method, +Option)。(+和++表示参数的方式)

前两个参数一起使用。L既可以是变量列表，也可以是术语列表。如果是前者，则Arg必须为0；如果是后者，则Arg表示在搜索过程中应实例化的变量的位置，例如：

search([A,B],0,input_order,indomain,complete,[]).

或

search([p(1,A),p(2,B)],2,input_order,indomain,complete,[]).

在这两种情况下，变量A和B都是在搜索期间实例化的。

第三个参数是selection方法。search/6使用此方法从列表L中选择下一个要实例化的变量。

最简单的选项是input_order：搜索只是迭代列表中的变量。在上面的示例中，它将首先实例化A，然后实例化B。其他选项考虑域大小和/或附加到变量的约束数量，并做出相应的选择。例如，first_fail选择具有最小域的变量。如果A的当前域名为[1,2,3]，且B的域名为[1,3]，则首先选择B并实例化。如果多个变量具有相同的最小域大小，则将按输入顺序选择第一个变量。考虑域大小的选择方法实现了动态变量排序，因为域大小将在搜索期间改变(缩小)，这取决于约束实现的传播量。

其他选择方法现在应该是不言而喻的。

还可以定义您自己的选择方法，前提是实现它的谓词的参数为2，即有两个参数。谓词必须将变量作为输入，并计算某个准则值。将选择标准值最小的变量。

第四个参数是choice方法。选择变量后，choice方法将控制搜索期间尝试其域中的值的顺序。

最简单的选项是indomain，它以升序选择变量当前域中的值。也就是说，如果变量A具有域[1,3,5]，那么搜索将最初将A绑定到1，在回溯时将其绑定到3，最后绑定到5。indomain_middle将从3开始，然后是1，然后是5。

更复杂的选择方法(例如，不同于indomain)将删除回溯的试用值，即基本上添加额外的约束，如A#\=1。这将导致额外的传播，这反过来可能允许更早地检测不可行。在运行n-queens示例时，您可以从问题中链接的search/6文档中看到效果。

同样，您也可以定义自己的选择方法。谓词的大小必须是1或3。如果大小为1，则谓词将一个变量作为输入并将其绑定到一个值(或者做出一些其他选择，从而改变变量的域)。如果参数是3，那么你可以使用两个额外的参数来传递一些状态信息，你可以使用这些信息来做出选择。

第五个参数是search方法。这控制搜索应该探索的搜索树部分的大小(而选择方法控制沿着树分支的变量的顺序，而选择方法控制搜索树中分支的顺序)。

最简单的选项是complete，它从左到右搜索树，直到树耗尽。所有其他选项(除了对称破坏)都是不完整的搜索方法，即搜索树中将有未探索的分支。如果解决方案在这样一个未探索的分支的叶子上，那么它将不会被找到。您必须确保选择和选择方法以不完全搜索方法能够找到解决方案的方式来塑造搜索树。例如，选项bbs限制了在搜索过程中可以进行的回溯的数量。如果该数字已耗尽，则搜索将停止。

对称破坏将只排除在某种程度上与其他分支等价(对称)的分支。

第六个参数是一个可能的附加选项列表，如search/6文档中所述。通常情况下，您不需要它们。