public class MinConflictsStrategy extends SolutionStrategy
function MIN-CONFLICTS(csp, max-steps) returns a solution or failure
inputs: csp, a constraint satisfaction problem
max-steps, the number of steps allowed before giving up
current = an initial complete assignment for csp
for i = 1 to max steps do
if current is a solution for csp then return current
var = a randomly chosen conflicted variable from csp.VARIABLES
value = the value v for var that minimizes CONFLICTS(var, v, current, csp)
set var = value in current
return failure
Figure 6.8 The MIN-CONFLICTS algorithm for solving CSPs by local search. The
initial state may be chosen randomly or by a greedy assignment process that
chooses a minimal-conflict value for each variable in turn. The CONFLICTS
function counts the number of constraints violated by a particular value,
given the rest of the current assignment.| Constructor and Description |
|---|
MinConflictsStrategy(int maxSteps)
Constructs a min-conflicts strategy with a given number of steps allowed
before giving up.
|
| Modifier and Type | Method and Description |
|---|---|
Assignment |
solve(CSP csp)
Returns a solution to the specified CSP, which specifies values for all
the variables such that the constraints are satisfied.
|
addCSPStateListener, fireStateChanged, fireStateChanged, removeCSPStateListenerpublic MinConflictsStrategy(int maxSteps)
maxSteps - the number of steps allowed before giving uppublic Assignment solve(CSP csp)
SolutionStrategysolve in class SolutionStrategycsp - a CSP to solve