constraints - Eclipse 约束编程 - 搜索/6

Question

我无法理解eclipse 约束编程框架中的 search/6 函数的文档。

我知道选择参数基本上会影响值排序。

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

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

谢谢

Answer 1

I'll try to answer it as briefly as possible, since search/6 is one of the most complex predicates you can find in the ECLiPSe system.

Any more detailed follow-up questions would probably better be asked in the ECLiPSe user mailing list, though.

The search/6 predicate is a generic predicate for controlling the search for a solution of a CLP problem. It allows the user to control the shape of the search tree (the order of variables along the branches, the order of the branches, and the portion of the search tree that is visited). The predicate has 6 parameters: search(+L, ++Arg, ++Select, +Choice, ++Method, +Option). (+ and ++ denote the mode of the parameter)

The first two parameters go together. L is either a list of variables or a list of terms. If it's the former, the Arg must be 0, if it's the latter, then Arg denotes the position of the variables that should be instantiated during the search, e.g.:

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

or

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

In both cases, the variables A and B are instantiated during search.

The third parameter is the selection method. This method is used by search/6 to select the next variable from the list L to instantiate.

The simplest option is input_order: the search simply iterates of the variables in the list. In the examples above, it would instantiate A first, then B. The other options consider the domain size and/or the number of constraints attached to the variables, and make the selection accordingly. E.g., first_fail chooses the variable with the smallest domain. If the current domain of A is [1,2,3] and B has the domain [1,3], then B will be selected and instantiated first. If more than one variable has the same smallest domain size, then the first of these by input order will be selected. Selection methods that take the domain size into account achieve a dynamic variable ordering, since the domain sizes will change (shrink) during search, depending on the amount of propagation that the constraints achieve.

The other selection methods should now be self-explanatory.

It is also possible to define your own selection method, provided that the predicate that implements it has arity 2, i.e., has two parameters. The predicate must take a variable as input and calculate some criterion value. The variable with the smallest criterion value will be selected.

The fourth parameter is the choice method. Once a variable is selected, the choice method controls the order in which the values in its domain are tried during search.

The simplest option is indomain, which chooses the values in the variable's current domain in ascending order. I.e., if variable A has the domain [1,3,5], then the search will initially bind A to 1, on backtracking bind it to 3, and finally to 5. indomain_middle will start with 3, then 1, then 5.

The more complex choice methods (i.e., other than indomain) will remove a tried value on backtracking, i.e., basically add additional constraints like A#\=1. This will cause additional propagation which may in turn allow earlier detection of infeasibilities. You can see the effect when running the n-queens example from the search/6 documentation that you linked to in your question.

Again, it is also possible to define your own choice method. The predicate must be of arity 1 or 3. If the arity is 1, then the predicate takes one variable as input and binds it to a value (or makes some other choice which alters the domain of the variable). If the arity is 3, then you can use the two additional parameters to pass along some state information which you can use to make the choice.

The fifth parameter is the search method. This controls the size of the section of the search tree that the search should explore (whereas the selection method controls the order of the variables along the branches of the tree, and the choice method controls the order of the branches in the search tree).

The simplest option is complete, which searches the tree left-to-right until the tree is exhausted. All other options (apart from symmetry breaking) are incomplete search methods, i.e., there will be branches in the search tree that are left unexplored. If the solution is on the leaf of such an unexplored branch, then it will not be found. You have to make sure that selection and choice methods shape the search tree in a way that the incomplete search method is able to find the solution. The option bbs, for instance, restricts the number of backtracks that can be made during search. If that number is exhausted, then the search will stop.

Symmetry breaking will only exclude branches that are equivalent (symmetrical) to other branches, in some way.

The sixth parameter is a list of possible additional options, described in the search/6 documentation. Normally, you won't need them.