aima.core.search.csp

Class TreeCSPSolver

java.lang.Object

aima.core.search.csp.SolutionStrategy

aima.core.search.csp.TreeCSPSolver

public class TreeCSPSolver
extends SolutionStrategy

Artificial Intelligence A Modern Approach (3rd Ed.): Figure 6.11, Page 224.

 
 function TREE-CSP-SOLVER(csp) returns a solution, or failure
                inputs: csp, a CSP with components X, D, C
                n ← number of variables in X
                assignment ← an empty assignment
                root  ← any variable in X
                X ← TOPOLOGICALSORT(X, root )
                for j = n down to 2 do
                        MAKE-ARC-CONSISTENT(PARENT(Xj),Xj )
                        if it cannot be made consistent then return failure
                for i = 1 to n do
                        assignment[Xi] ← any consistent value from Di
                        if there is no consistent value then return failure
                return assignment
 
 
 
 
 Figure 6.11 The TREE-CSP-SOLVER algorithm for solving tree-structured CSPs.
 If the CSP has a solution, we will find it in linear time; if not, we will
 detect a contradiction.

Author:

Anurag Rai

Field Summary

Fields

Modifier and Type	Field and Description
protected int[]	parent

Constructor Summary

Constructors

Constructor and Description
TreeCSPSolver()

Method Summary

Modifier and Type	Method and Description
protected boolean	makeArcConsistent(Variable xi, Variable xj, Constraint constraint, CSP csp, DomainRestoreInfo info)
Assignment	solve(CSP csp) Returns a solution to the specified CSP, which specifies values for all the variables such that the constraints are satisfied.
protected java.util.List<Variable>	topologicalSort(CSP csp, java.util.List<Variable> l, Variable root)

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

parent

protected int[] parent

Constructor Detail

TreeCSPSolver

public TreeCSPSolver()

Method Detail

solve

public Assignment solve(CSP csp)

Description copied from class: SolutionStrategy

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

Specified by:

solve in class SolutionStrategy

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.

topologicalSort

protected java.util.List<Variable> topologicalSort(CSP csp,
                                                   java.util.List<Variable> l,
                                                   Variable root)

makeArcConsistent

protected boolean makeArcConsistent(Variable xi,
                                    Variable xj,
                                    Constraint constraint,
                                    CSP csp,
                                    DomainRestoreInfo info)