CSPTreeSover documentation improved.
@@ -5,11 +5,10 @@ import java.util.*;
import aima.core.util.Util;
/**
- *
* Artificial Intelligence A Modern Approach (3rd Ed.): Figure 6.11, Page
* 224.<br>
* <br>
- *
+ * <p>
* <pre>
* <code>
* function TREE-CSP-SOLVER(csp) returns a solution, or failure
@@ -31,12 +30,11 @@ import aima.core.util.Util;
*
* 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. Comment to (*). If no empty domain was found in the
- * previous loop, this will never happen. (RL)
+ * detect a contradiction. Comment to (*) (RL): If no empty domain was found in the
+ * previous loop, this will never happen.
*
* @author Ruediger Lunde
* @author Anurag Rai
- *
*/
public class TreeCSPSolver<VAR extends Variable, VAL> extends SolutionStrategy<VAR, VAL> {
@@ -53,6 +51,7 @@ public class TreeCSPSolver<VAR extends Variable, VAL> extends SolutionStrategy<V
if (orderedVars.size() < csp.getVariables().size())
return null; // CSP is not tree-structured or not connected or has no solution!
+ // Establish arc consistency from top to bottom (starting at the bottom).
for (int i = orderedVars.size() - 1; i >= 1; i--) {
VAR var = orderedVars.get(i);
Constraint<VAR, VAL> constraint = parentConstraints.get(var);
@@ -62,6 +61,8 @@ public class TreeCSPSolver<VAR extends Variable, VAL> extends SolutionStrategy<V
return null; // CSP has no solution!
}
}
+
+ // Assign values to variables from top to bottom.
for (int i = 0; i < orderedVars.size(); i++) {
VAR var = orderedVars.get(i);
for (VAL value : csp.getDomain(var)) {
@@ -73,11 +74,10 @@ public class TreeCSPSolver<VAR extends Variable, VAL> extends SolutionStrategy<V
return assignment;
}
- // Since the graph is a tree, topologicalSort is:
- // Level order traversal of the tree OR BFS on tree OR Pre-oder
/**
* Computes an explicit representation of the tree structure and a total order which is consistent with the
* parent-child relations.
+ *
* @param csp A CSP
* @param root A root variable
* @param vars The computed total order (initially empty)
@@ -94,14 +94,14 @@ public class TreeCSPSolver<VAR extends Variable, VAL> extends SolutionStrategy<V
while (currParentIdx < vars.size() - 1) {
currParentIdx++;
VAR currParent = vars.get(currParentIdx);
- int upReferenceCount = 0;
+ int arcsPointingUpwards = 0;
for (Constraint<VAR, VAL> constraint : csp.getConstraints(currParent)) {
VAR neighbor = csp.getNeighbor(currParent, constraint);
if (neighbor == null)
return; // this constraint is not binary!
if (parentConstraints.containsKey(neighbor)) {
- upReferenceCount++;
- if (upReferenceCount > 1)
+ arcsPointingUpwards++;
+ if (arcsPointingUpwards > 1)
return; // CSP is not a tree!
} else {
parentConstraints.put(neighbor, constraint);
