/
AbstractBacktrackingSolver.java
111 lines (103 loc) · 4.58 KB
/
AbstractBacktrackingSolver.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
package aima.core.search.csp.solver;
import aima.core.search.csp.Assignment;
import aima.core.search.csp.CSP;
import aima.core.search.csp.Variable;
import aima.core.search.csp.solver.inference.InferenceLog;
import aima.core.util.Tasks;
import java.util.Optional;
/**
* Artificial Intelligence A Modern Approach (3rd Ed.): Figure 6.5, Page 215.<br>
* <br>
* <p>
* <pre>
* <code>
* function BACKTRACKING-SEARCH(csp) returns a solution, or failure
* return BACKTRACK({ }, csp)
*
* function BACKTRACK(assignment, csp) returns a solution, or failure
* if assignment is complete then return assignment
* var = SELECT-UNASSIGNED-VARIABLE(csp)
* for each value in ORDER-DOMAIN-VALUES(var, assignment, csp) do
* if value is consistent with assignment then
* add {var = value} to assignment
* inferences = INFERENCE(csp, var, value)
* if inferences != failure then
* add inferences to assignment
* result = BACKTRACK(assignment, csp)
* if result != failure then
* return result
* remove {var = value} and inferences from assignment
* return failure
* </code>
* </pre>
* <p>
* Figure 6.5 A simple backtracking algorithm for constraint satisfaction
* problems. The algorithm is modeled on the recursive depth-first search of
* Chapter 3. By varying the functions SELECT-UNASSIGNED-VARIABLE and
* ORDER-DOMAIN-VALUES, we can implement the general-purpose heuristic discussed
* in the text. The function INFERENCE can optionally be used to impose arc-,
* path-, or k-consistency, as desired. If a value choice leads to failure
* (noticed wither by INFERENCE or by BACKTRACK), then value assignments
* (including those made by INFERENCE) are removed from the current assignment
* and a new value is tried.
*
* @param <VAR> Type which is used to represent variables
* @param <VAL> Type which is used to represent the values in the domains
*
* @author Ruediger Lunde
*/
public abstract class AbstractBacktrackingSolver<VAR extends Variable, VAL> extends CspSolver<VAR, VAL> {
/** Applies a recursive backtracking search to solve the CSP. */
public Optional<Assignment<VAR, VAL>> solve(CSP<VAR, VAL> csp) {
Assignment<VAR, VAL> result = backtrack(csp, new Assignment<>());
return result != null ? Optional.of(result) : Optional.empty();
}
/**
* Template method, which can be configured by overriding the three
* primitive operations below.
* @return An assignment (possibly incomplete if task was cancelled) or null if no solution was found.
*/
private Assignment<VAR, VAL> backtrack(CSP<VAR, VAL> csp, Assignment<VAR, VAL> assignment) {
Assignment<VAR, VAL> result = null;
if (assignment.isComplete(csp.getVariables()) || Tasks.currIsCancelled()) {
result = assignment;
} else {
VAR var = selectUnassignedVariable(csp, assignment);
for (VAL value : orderDomainValues(csp, assignment, var)) {
assignment.add(var, value);
fireStateChanged(csp, assignment, var);
if (assignment.isConsistent(csp.getConstraints(var))) {
InferenceLog<VAR, VAL> log = inference(csp, assignment, var);
if (!log.isEmpty())
fireStateChanged(csp, null, null);
if (!log.inconsistencyFound()) {
result = backtrack(csp, assignment);
if (result != null)
break;
}
log.undo(csp);
}
assignment.remove(var);
}
}
return result;
}
/**
* Primitive operation, selecting a not yet assigned variable.
*/
protected abstract VAR selectUnassignedVariable(CSP<VAR, VAL> csp, Assignment<VAR, VAL> assignment);
/**
* Primitive operation, ordering the domain values of the specified variable.
*/
protected abstract Iterable<VAL> orderDomainValues(CSP<VAR, VAL> csp, Assignment<VAR, VAL> assignment, VAR var);
/**
* Primitive operation, which tries to optimize the CSP representation with respect to a new assignment.
*
* @param var The variable which just got a new value in the assignment.
* @return An object which provides information about
* (1) whether changes have been performed,
* (2) possibly inferred empty domains, and
* (3) how to restore the original CSP.
*/
protected abstract InferenceLog<VAR, VAL> inference(CSP<VAR, VAL> csp, Assignment<VAR, VAL> assignment, VAR var);
}