Package org.jacop.search
Class PrioritySearch<T extends Var>
java.lang.Object
org.jacop.search.DepthFirstSearch<T>
org.jacop.search.PrioritySearch<T>
- Type Parameters:
T
- type of variable being used in the Search.
- All Implemented Interfaces:
Search<T>
PrioritySearch selects first a row in the matrix based on metric of
the variable at the pririty vector. As soon as a row is choosen,
variables are selected for indomain method. The row selection is
done with the help of pririty variable comparatos. Two comparators
can be employed main and tiebreaking one. If two are not sufficient
to differentiate two rows than the lexigraphical ordering is used.
Based on paper "Priority Search with MiniZinc" by Thibaut Feydy,
Adrian Goldwaser, Andreas Schutt, Peter J. Stuckey,and Kenneth
D. Young, in ModRef'2017: The Sixtenth International Workshop on
Constraint Modelling and Reformulation at CP 2017.
- Version:
- 4.10
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescription(package private) class
PrioritySearch.LinkingSearch<T extends Var>
(package private) static final class
-
Field Summary
FieldsModifier and TypeFieldDescription(package private) T[]
(package private) ComparatorVariable
<T> (package private) static final boolean
(package private) int
(package private) int
(package private) T[]
(package private) DepthFirstSearch<T>[]
(package private) int
(package private) boolean
(package private) ComparatorVariable
<T> (package private) BitSet
Fields inherited from class org.jacop.search.DepthFirstSearch
assignSolution, backtracksOut, backtracksOutCheck, check, childSearches, consistencyListener, cost, costValue, costValueFloat, costVariable, currentChildSearch, decisions, decisionsOut, decisionsOutCheck, depth, depthExcludePaths, einAinleftTree, exitChildListener, exitListener, heuristic, id, initializeListener, masterSearch, maxDepth, maxDepthExcludePaths, no, nodes, nodesOut, nodesOutCheck, numberBacktracks, optimize, printInfo, respectSolutionListenerAdvice, solutionListener, store, timeOut, timeOutCheck, timeOutListener, timeOutOccured, tOut, wrongDecisions, wrongDecisionsOut, wrongDecisionsOutCheck
-
Constructor Summary
ConstructorsConstructorDescriptionPrioritySearch
(T[] priority, ComparatorVariable<T> comparator, ComparatorVariable<T> tieBreak, DepthFirstSearch<T>[] dfs) It constructs a PrioritySearch.PrioritySearch
(T[] priority, ComparatorVariable<T> comparator, DepthFirstSearch<T>[] dfs) It constructs a PrioritySearch. -
Method Summary
Modifier and TypeMethodDescriptionvoid
addRestartCalculator
(DepthFirstSearch<T> s, Calculator calc) int
It returns number of backtracks performed by the search.int
It returns number of decisions performed by the search.int
It returns the maximum depth reached by a search.int
getNodes()
It returns number of search nodes explored by the search.void
(package private) int
T[]
getVariables
(PrioritySearch<T> ps) int
It returns number of wrong decisions performed by the search.boolean
label
(int n) This function is called recursively to assign variables one by one.boolean
labeling()
It is a labeling function called if the search is a sub-search being called from the parent search.boolean
boolean
boolean
labeling
(Store store, SelectChoicePoint<T> select) It performs search using supplied choice point selection heuristic.boolean
labeling
(Store store, SelectChoicePoint<T> select, Var costVar) It performs search using supplied choice point selection heuristic, as well as costVariable as aim at finding an optimal solution.(package private) DepthFirstSearch
<T> lastSearch
(DepthFirstSearch<T> dfs) int
void
setCostVariable
(Var cost) void
setSolutionLimit
(int no) (package private) String
toString()
Methods inherited from class org.jacop.search.DepthFirstSearch
addChildSearch, assignSolution, assignSolution, getConsistencyListener, getCostValue, getCostValueFloat, getCostVariable, getExitChildListener, getExitListener, getInitializeListener, getSolution, getSolution, getSolutionListener, getTimeOutListener, getVariables, id, printAllSolutions, setAssignSolution, setBacktracksOut, setChildSearch, setConsistencyListener, setCostVar, setDecisionsOut, setExitChildListener, setExitListener, setID, setInitializeListener, setMasterSearch, setNodesOut, setOptimizationForChildSearches, setOptimize, setPrintInfo, setSelectChoicePoint, setSolutionListener, setStore, setTimeOut, setTimeOutListener, setTimeOutMilliseconds, setWrongDecisionsOut, toStringFull
-
Field Details
-
debugAll
static final boolean debugAll- See Also:
-
n
int n -
priority
-
comparator
ComparatorVariable<T extends Var> comparator -
tieBreak
ComparatorVariable<T extends Var> tieBreak -
search
DepthFirstSearch<T extends Var>[] search -
visited
BitSet visited -
allVars
-
noSolutions
int noSolutions -
solutionsLimit
int solutionsLimit -
solutionsReached
boolean solutionsReached
-
-
Constructor Details
-
PrioritySearch
It constructs a PrioritySearch.- Parameters:
priority
- prority variables used to select a sub-vector of vars (row)comparator
- the variable comparator to choose the proper sub.search. // * @param indomain variable ordering value to be used to determine value for a given variable.dfs
- vector of depth first searches to be selected from; they must have SelectChoicePoint set.
-
PrioritySearch
public PrioritySearch(T[] priority, ComparatorVariable<T> comparator, ComparatorVariable<T> tieBreak, DepthFirstSearch<T>[] dfs) It constructs a PrioritySearch.- Parameters:
priority
- prority variables used to select a sub-vector of vars (row)comparator
- the variable comparator to choose the proper sub.search.tieBreak
- the variable tie breaking comparator to choose the proper sub.search.dfs
- vector of depth first searches to be selected from; they must have SelectChoicePoint set.
-
-
Method Details
-
lastSearch
-
labeling
Description copied from interface:Search
It performs search using supplied choice point selection heuristic. -
labeling
-
labeling
Description copied from interface:Search
It performs search using supplied choice point selection heuristic, as well as costVariable as aim at finding an optimal solution.- Specified by:
labeling
in interfaceSearch<T extends Var>
- Overrides:
labeling
in classDepthFirstSearch<T extends Var>
- Parameters:
store
- constraint store which will be used by labeling.select
- the selection choice point heuristic.costVar
- variable to specify cost.- Returns:
- true if the solution was found.
-
labeling
-
labeling
public boolean labeling()Description copied from class:DepthFirstSearch
It is a labeling function called if the search is a sub-search being called from the parent search. It never assigns a solution as it will be immediately retracted by search calling this one. -
label
public boolean label(int n) Description copied from class:DepthFirstSearch
This function is called recursively to assign variables one by one. -
getNodes
public int getNodes()Description copied from class:DepthFirstSearch
It returns number of search nodes explored by the search. -
getDecisions
public int getDecisions()Description copied from class:DepthFirstSearch
It returns number of decisions performed by the search.- Specified by:
getDecisions
in interfaceSearch<T extends Var>
- Overrides:
getDecisions
in classDepthFirstSearch<T extends Var>
- Returns:
- the number of decisions.
-
getWrongDecisions
public int getWrongDecisions()Description copied from class:DepthFirstSearch
It returns number of wrong decisions performed by the search.- Specified by:
getWrongDecisions
in interfaceSearch<T extends Var>
- Overrides:
getWrongDecisions
in classDepthFirstSearch<T extends Var>
- Returns:
- number of wrong decisions.
-
getBacktracks
public int getBacktracks()Description copied from class:DepthFirstSearch
It returns number of backtracks performed by the search.- Specified by:
getBacktracks
in interfaceSearch<T extends Var>
- Overrides:
getBacktracks
in classDepthFirstSearch<T extends Var>
- Returns:
- the number of backtracks.
-
getMaximumDepth
public int getMaximumDepth()Description copied from class:DepthFirstSearch
It returns the maximum depth reached by a search.- Specified by:
getMaximumDepth
in interfaceSearch<T extends Var>
- Overrides:
getMaximumDepth
in classDepthFirstSearch<T extends Var>
- Returns:
- the maximum depth.
-
getStatistics
public void getStatistics() -
statistics
String statistics() -
setCostVariable
-
getSubSearch
int getSubSearch() -
getVariables
-
addRestartCalculator
-
setSolutionLimit
public void setSolutionLimit(int no) -
getSearchSeq
-
toString
-
noSolutions
public int noSolutions()
-