Lines Matching refs:search
50 %%This tutorial is an overwiew of different search methods to Prolog,
67 search(Variables),
75 Once the model is set up, we go into the search phase.
79 which have to be located by search, e.g.\ in order to find the best one.
87 \item The {\em search space} is the set of all possible total assignments.
88 The search space is usually very large because it grows exponentially
104 \caption{A search space of size 16}
107 Figure \ref{figsearchspace} shows a search space with N (here 16)
111 We can classify search methods according to different criteria:
113 \item[Complete vs incomplete exploration] complete search means that the search space
116 that no better solution exists). Incomplete search may be sufficient when
120 assignments which represent subsets of the search space) or by moving
126 Here is table of a selection of search methods together with their properties:
133 Full tree search& complete& constructive& no\\
134 Credit search& incomplete& constructive& no\\
139 Tabu search& incomplete& move-based& possibly\\
145 The constructive search methods usually organise the search space by
147 search tree (Figure \ref{figsearchtree}). The nodes in this tree
148 represent choices which partition the remaining search space into two
150 a tree structure, the search space can be traversed systematically and
157 \caption{Search space structured using a search tree}
160 Figure \ref{figtreesearch} shows a sample tree search, namely a depth-first
163 incomplete move-based search which does not follow a fixed search space
170 \caption{A move-based search}
178 \caption{A tree search (depth-first)}
184 typical sizes of search spaces.
185 A complete exploration of a huge search space
189 Moreover, a complete search method must remember which parts of the
190 search space have already been visited.
224 Since search space sizes grow exponentially with problem size,
227 The only way out is {\em not} to look at the whole search space.
233 \item {\bf Ignore} parts of the search space that are unlikely to contain
234 solutions (i.e.\ do incomplete search), or at least postpone their exploration.
236 A heuristic is a particular traversal order of the search space
242 systematic tree search, which is the traditional search method
253 There is one form of tree search which is especially economic:
254 depth-first, left-to-right search by backtracking. It allows to
255 traverse a search tree systematically while requiring only a stack
257 search (e.g. breadth-first) have exponential memory requirements.
261 into play here because we deal with finite search trees.
263 Sometimes depth-first search and heuristic search are treated as antonyms.
264 This is only justified when the shape of the search tree is statically fixed.
267 allow to arrange for {\em any} order of visiting the leaves of the search tree,
275 In general, the nodes of a search tree represent {\em choices}.
278 \index{partition a search space}
279 search space into two or more disjoint sub-spaces.
289 branch of the search tree and to 1 in the other.
297 we can make a n-ary search tree node by writing
317 which means that the search tree nodes correspond to a variable
334 Figure \ref{figvarsel} shows how variable selection reshapes a search tree.
335 If we decide to choose values for X1 first (at the root of the search tree)
336 and values for X2 second, then the search tree has one particular shape.
360 The other way to change the search tree is value selection, i.e. reordering
377 To give an idea of the numbers involved, the following table shows the search
378 space sizes, the number of possible search space traversal orderings,
405 to backtrack search through variable and value selection.
434 labeling(Vars). % search
456 factor at the root of the search tree and the total number of internal nodes.
472 search space is not reduced, just re-shaped. Heuristics that yield good
557 %The size of the (remaining) search space can be computed easily
570 both constraint propagation and search heuristics.
627 One way to limit the scope of backtrack search is to keep a
628 record of the number of backtracks, and curtail the search when this
634 The predicate defining bounded backtrack search is
696 Credit search is a tree search method where the number of
698 starting the search at the tree root with a certain integral amount of
708 implements credit search. For ease of understanding, it is
711 % Credit search (for boolean variables only)
718 ParentCredit > 0, % possibly cut-off search here
734 leaf of the search tree is reached. The leftmost alternative should
735 therefore be the one favoured by the search heuristics.
737 What is a reasonable amount of credit to give to a search?
738 In an unconstrained search tree, the credit is equivalent to the
747 root of the search tree and disallows choices completely below a certain
749 is not good enough. A possible remedy is to combine credit search with
750 bounded backtrack search.
757 Another form of incomplete tree search is simply to use time-outs.
793 Limited discrepancy search ({\em LDS}) is a search method that assumes
794 the user has a good heuristic for directing the search. A perfect
795 heuristic would, of course, not require any search. However most
802 search restarts. In theory the search is complete, as eventually the
804 the whole search space. In practice, however, it is only beneficial
806 is found, other search methods should be tried.
824 search. The predicate supporting static LDS takes a list of variables
828 the LDS search can still succeed even if this is not the case).
835 LDS search is implemented in the file
841 Static LDS search is then available via the predicate
852 is an output of the search (an integer between $0$ and the number of
899 Often the heuristic value is calculated on the fly, during search. To
904 The tentative value may be changed during search. For example if a
906 during search, its tentative value is automatically changed to its
909 Dynamic LDS search is available in {\eclipse} via the predicate
960 The two search techniques, BBS and LDS, can be merged quite simply in
1005 to constructive search) methods. These methods have originally been developed
1009 From a technical point of view, the main difference between tree search
1010 and move-based search is that tree search is monotonic in the sense that
1014 In a move-based search, the main characteristics is that a move produces
1031 We will demonstrate the local search methods using the well-known
1042 The tree search program for this problem looks as follows:
1050 min_max(labeling(Vars), -Profit). % branch-and-bound search
1052 At the end of the problem modelling code, a standard branch-and-bound tree search
1062 To be able to use local search, we load the {\bf repair} library and
1064 At the end, we invoke a local search routine instead of tree search:
1096 queried using tent\_get/2. We will use these inside the local search
1111 local search methods are often characterised by
1128 except that some methods (random walk and the tabu search)
1138 As a simple example of local search, let us look at a random walk
1272 Simulated Annealing is a slightly more complex variant of local search.
1282 that decreases with the temperature. The search routine must be invoked
1325 Another variant of local search is tabu search. Here, a number of moves
1327 search. Moves are selected by an acceptance criterion, with a
1329 list. As in most local search methods there are many possible variants and
1375 In practice, the tabu search forms only a skeleton around which a complex
1376 search algorithm is built. An example of this is applying tabu search to
1402 constraint, then the current search is abandoned, and a new search restarted
1405 values to the already labelled variables in the just abandoned search. This
1407 the new search. This is in contrast to a conventional backtracking search,
1408 where the search would not be entirely abandoned, but will try assigning
1410 `weak-commitment' refers to this feature of the search technique, wherein
1411 it is not `strongly committed' to the current branch in the search-space as
1412 in conventional backtracking search. The aim is that the search would not
1413 be `stuck' exhaustively exploring a particular region of a search-space
1414 that might not lead to a solution. The search is instead guided by the
1441 search, and \verb'Initial' is a list of the initial tentative values that
1443 already have set up the initial constraints so that the search can
1444 proceed. During the search process, additional nogood constraints would be
1445 added to direct the search.
1447 Two example usage of the search are given: 1) a search for potentially all
1448 the solutions to the N-Queens problem, and 2) a search for the first
1493 WCS which replace the usual tree search strategy. The probing
1514 The search restart itself is quite easy to implement in {\eclipse}, as the
1519 specifically creating a choice-point at the start of the search, in the
1537 \verb'try_one_step/2' tries out one search, with the first argument
1541 clause of \verb'do_search/2' will be tried, in which a new search is
1544 have been generated. To allow for the search of more solutions, this
1582 new nogood constraint can be added for the restarted search,
1623 If a variable had been labelled in the previous search, the labelled value
1684 value can be propagated. This increase the efficiency of the search in many