aima.core.search.csp

Class ImprovedBacktrackingStrategy

java.lang.Object

aima.core.search.csp.SolutionStrategy

aima.core.search.csp.BacktrackingStrategy

aima.core.search.csp.ImprovedBacktrackingStrategy

public class ImprovedBacktrackingStrategy
extends BacktrackingStrategy

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	ImprovedBacktrackingStrategy.Inference
static class	ImprovedBacktrackingStrategy.Selection

Field Summary

Fields

Modifier and Type	Field and Description
protected ImprovedBacktrackingStrategy.Inference	inferenceStrategy
protected boolean	isLCVHeuristicEnabled
protected ImprovedBacktrackingStrategy.Selection	selectionStrategy

Constructor Summary

Constructors

Constructor and Description
ImprovedBacktrackingStrategy() Creates a strategy which is by default equivalent to plain backtracking.
ImprovedBacktrackingStrategy(boolean enableMRV, boolean enableDeg, boolean enableAC3, boolean enableLCV) Creates a backtracking strategy with the specified features.

Method Summary

Modifier and Type	Method and Description
void	enableLCV(boolean state) Selects the least constraining value heuristic as implementation for ORDER-DOMAIN-VALUES.
protected DomainRestoreInfo	inference(Variable var, Assignment assignment, CSP csp) Primitive operation, which tries to prune out values from the CSP which are not possible anymore when extending the given assignment to a solution.
protected java.lang.Iterable<?>	orderDomainValues(Variable var, Assignment assignment, CSP csp) Primitive operation, ordering the domain values of the specified variable.
protected Variable	selectUnassignedVariable(Assignment assignment, CSP csp) Primitive operation, selecting a not yet assigned variable.
void	setInference(ImprovedBacktrackingStrategy.Inference iStrategy) Selects the algorithm for INFERENCE.
void	setVariableSelection(ImprovedBacktrackingStrategy.Selection sStrategy) Selects the algorithm for SELECT-UNASSIGNED-VARIABLE
Assignment	solve(CSP csp) Starts with a constraint propagation if AC-3 is enabled and then calls the super class implementation.

Methods inherited from class aima.core.search.csp.SolutionStrategy

addCSPStateListener, fireStateChanged, fireStateChanged, removeCSPStateListener

Methods inherited from class java.lang.Object

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

Field Detail

selectionStrategy

protected ImprovedBacktrackingStrategy.Selection selectionStrategy

inferenceStrategy

protected ImprovedBacktrackingStrategy.Inference inferenceStrategy

isLCVHeuristicEnabled

protected boolean isLCVHeuristicEnabled

Constructor Detail

ImprovedBacktrackingStrategy

public ImprovedBacktrackingStrategy()

Creates a strategy which is by default equivalent to plain backtracking.

ImprovedBacktrackingStrategy

public ImprovedBacktrackingStrategy(boolean enableMRV,
                                    boolean enableDeg,
                                    boolean enableAC3,
                                    boolean enableLCV)

Creates a backtracking strategy with the specified features.

Method Detail

setVariableSelection

public void setVariableSelection(ImprovedBacktrackingStrategy.Selection sStrategy)

Selects the algorithm for SELECT-UNASSIGNED-VARIABLE

setInference

public void setInference(ImprovedBacktrackingStrategy.Inference iStrategy)

Selects the algorithm for INFERENCE.

enableLCV

public void enableLCV(boolean state)

Selects the least constraining value heuristic as implementation for ORDER-DOMAIN-VALUES.

solve

public Assignment solve(CSP csp)

Starts with a constraint propagation if AC-3 is enabled and then calls the super class implementation.

Overrides:

solve in class BacktrackingStrategy

Parameters:

csp - a CSP to solve

Returns:

a solution to the specified CSP, which specifies values for all the variables such that the constraints are satisfied.

selectUnassignedVariable

protected Variable selectUnassignedVariable(Assignment assignment,
                                            CSP csp)

Primitive operation, selecting a not yet assigned variable.

Overrides:

selectUnassignedVariable in class BacktrackingStrategy

orderDomainValues

protected java.lang.Iterable<?> orderDomainValues(Variable var,
                                                  Assignment assignment,
                                                  CSP csp)

Primitive operation, ordering the domain values of the specified variable.

Overrides:

orderDomainValues in class BacktrackingStrategy

inference

protected DomainRestoreInfo inference(Variable var,
                                      Assignment assignment,
                                      CSP csp)

Primitive operation, which tries to prune out values from the CSP which are not possible anymore when extending the given assignment to a solution.

Overrides:

inference in class BacktrackingStrategy

Returns:

An object which provides informations about (1) whether changes have been performed, (2) possibly inferred empty domains , and (3) how to restore the domains.