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>
public class PrioritySearch<T extends Var> extends DepthFirstSearch<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 comparators. 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.7
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description (package private) class
PrioritySearch.LinkingSearch<T extends Var>
(package private) static class
PrioritySearch.SolutionsLimitReached
-
Field Summary
Fields Modifier and Type Field Description (package private) T[]
allVars
(package private) ComparatorVariable<T>
comparator
(package private) static boolean
debugAll
(package private) int
n
(package private) int
noSolutions
(package private) T[]
priority
(package private) DepthFirstSearch[]
search
(package private) int
solutionsLimit
(package private) boolean
solutionsReached
(package private) java.util.BitSet
visited
-
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
Constructors Constructor Description PrioritySearch(T[] priority, ComparatorVariable<T> comparator, DepthFirstSearch<T>[] dfs)
It constructs a PrioritySearch variable ordering.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description void
addRestartCalculator(DepthFirstSearch s, Calculator calc)
int
getBacktracks()
It returns number of backtracks performed by the search.int
getDecisions()
It returns number of decisions performed by the search.int
getMaximumDepth()
It returns the maximum depth reached by a search.int
getNodes()
It returns number of search nodes explored by the search.DepthFirstSearch[]
getSearchSeq()
void
getStatistics()
(package private) int
getSubSearch()
T[]
getVariables(PrioritySearch ps)
int
getWrongDecisions()
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
labeling(Store store)
boolean
labeling(Store store, Var costVar)
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
lastSearch(DepthFirstSearch dfs)
int
noSolutions()
void
setCostVariable(Var cost)
void
setSolutionLimit(int no)
(package private) java.lang.String
statistics()
java.lang.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 Detail
-
debugAll
static final boolean debugAll
- See Also:
- Constant Field Values
-
n
int n
-
comparator
ComparatorVariable<T extends Var> comparator
-
search
DepthFirstSearch[] search
-
visited
java.util.BitSet visited
-
noSolutions
int noSolutions
-
solutionsLimit
int solutionsLimit
-
solutionsReached
boolean solutionsReached
-
-
Constructor Detail
-
PrioritySearch
public PrioritySearch(T[] priority, ComparatorVariable<T> comparator, DepthFirstSearch<T>[] dfs)
It constructs a PrioritySearch variable ordering.- Parameters:
priority
- prority variables used to select a sub-vector of vars (row)dfs
- vector of depth first searches to be selected from; they must have SelectChoicePoint set.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.
-
-
Method Detail
-
lastSearch
DepthFirstSearch lastSearch(DepthFirstSearch dfs)
-
labeling
public boolean labeling(Store store, SelectChoicePoint<T> select)
Description copied from interface:Search
It performs search using supplied choice point selection heuristic.
-
labeling
public boolean labeling(Store store)
-
labeling
public boolean labeling(Store store, SelectChoicePoint<T> select, Var costVar)
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
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
java.lang.String statistics()
-
setCostVariable
public void setCostVariable(Var cost)
-
getSubSearch
int getSubSearch()
-
getVariables
public T[] getVariables(PrioritySearch ps)
-
addRestartCalculator
public void addRestartCalculator(DepthFirstSearch s, Calculator calc)
-
setSolutionLimit
public void setSolutionLimit(int no)
-
getSearchSeq
public DepthFirstSearch[] getSearchSeq()
-
toString
public java.lang.String toString()
-
noSolutions
public int noSolutions()
-
-