minicp.search

Class DFSearch

java.lang.Object

minicp.search.DFSearch

public class DFSearch
extends Object

Depth First Search Branch and Bound implementation

Constructor Summary

Constructors

Constructor and Description
DFSearch(StateManager sm, Supplier<Procedure[]> branching) Creates a Depth First Search object with a given branching that defines the search tree dynamically.

Method Summary

Modifier and Type	Method and Description
void	onFailure(Procedure listener) Adds a listener that is called whenever a failure occurs and the search backtracks.
void	onSolution(Procedure listener) Adds a listener that is called on each solution.
SearchStatistics	optimize(Objective obj) Effectively start a branch and bound depth first search with a given objective.
SearchStatistics	optimize(Objective obj, Predicate<SearchStatistics> limit) Effectively start a branch and bound depth first search with a given objective and with a given predicate called at each node to stop the search when it becomes true.
SearchStatistics	optimizeSubjectTo(Objective obj, Predicate<SearchStatistics> limit, Procedure subjectTo) Executes a closure prior to effectively starting a branch and bound depth first search with a given objective to optimize and a given predicate called at each node to stop the search when it becomes true.
SearchStatistics	solve() Effectively start a depth first search looking for every solution.
SearchStatistics	solve(Predicate<SearchStatistics> limit) Effectively start a depth first search with a given predicate called at each node to stop the search when it becomes true.
SearchStatistics	solveSubjectTo(Predicate<SearchStatistics> limit, Procedure subjectTo) Executes a closure prior to effectively starting a depth first search with a given predicate called at each node to stop the search when it becomes true.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

DFSearch

public DFSearch(StateManager sm,
                Supplier<Procedure[]> branching)

Creates a Depth First Search object with a given branching that defines the search tree dynamically.

Parameters:

sm - the state manager that will be saved and restored at each node of the search tree

branching - a generator of closures in charge of defining the ordered children nodes at each node of the depth-first-search tree. When it returns an empty array, a solution is found. A backtrack occurs when a InconsistencyException is thrown.

Method Detail

onSolution

public void onSolution(Procedure listener)

Adds a listener that is called on each solution.

Parameters:

listener - the closure to be called whenever a solution is found

onFailure

public void onFailure(Procedure listener)

Adds a listener that is called whenever a failure occurs and the search backtracks. This happensthat when a InconsistencyException is thrown when executing the closure generated by the branching.

Parameters:

listener - the closure to be called whenever a failure occurs and the search need to backtrack

solve

public SearchStatistics solve()

Effectively start a depth first search looking for every solution.

Returns:

an object with the statistics on the search

solve

public SearchStatistics solve(Predicate<SearchStatistics> limit)

Effectively start a depth first search with a given predicate called at each node to stop the search when it becomes true.

Parameters:

limit - a predicate called at each node that stops the search when it becomes true

Returns:

an object with the statistics on the search

solveSubjectTo

public SearchStatistics solveSubjectTo(Predicate<SearchStatistics> limit,
                                       Procedure subjectTo)

Executes a closure prior to effectively starting a depth first search with a given predicate called at each node to stop the search when it becomes true. The state manager saves the state before executing the closure and restores it after the search. Any InconsistencyException that may be throw when executing the closure is also catched.

Parameters:

limit - a predicate called at each node that stops the search when it becomes true

subjectTo - the closure to execute prior to the search starts

Returns:

an object with the statistics on the search

optimize

public SearchStatistics optimize(Objective obj)

Effectively start a branch and bound depth first search with a given objective.

Parameters:

obj - the objective to optimize that is tightened each time a new solution is found

Returns:

an object with the statistics on the search

optimize

public SearchStatistics optimize(Objective obj,
                                 Predicate<SearchStatistics> limit)

Effectively start a branch and bound depth first search with a given objective and with a given predicate called at each node to stop the search when it becomes true.

Parameters:

obj - the objective to optimize that is tightened each time a new solution is found

limit - a predicate called at each node that stops the search when it becomes true

Returns:

an object with the statistics on the search

optimizeSubjectTo

public SearchStatistics optimizeSubjectTo(Objective obj,
                                          Predicate<SearchStatistics> limit,
                                          Procedure subjectTo)

Executes a closure prior to effectively starting a branch and bound depth first search with a given objective to optimize and a given predicate called at each node to stop the search when it becomes true. The state manager saves the state before executing the closure and restores it after the search. Any InconsistencyException that may be throw when executing the closure is also catched.

Parameters:

obj - the objective to optimize that is tightened each time a new solution is found

limit - a predicate called at each node that stops the search when it becomes true

subjectTo - the closure to execute prior to the search starts

Returns:

an object with the statistics on the search