aima.core.search.csp

Class AC3Strategy

java.lang.Object

aima.core.search.csp.AC3Strategy

public class AC3Strategy
extends java.lang.Object

Artificial Intelligence A Modern Approach (3rd Ed.): Figure 6.3, Page 209.

 
 function AC-3(csp) returns false if an inconsistency is found and true otherwise
    inputs: csp, a binary CSP with components (X, D, C)
    local variables: queue, a queue of arcs, initially all the arcs in csp
    while queue is not empty do
       (Xi, Xj) = REMOVE-FIRST(queue)
       if REVISE(csp, Xi, Xj) then
          if size of Di = 0 then return false
             for each Xk in Xi.NEIGHBORS - {Xj} do
                add (Xk, Xi) to queue
    return true
 
 function REVISE(csp, Xi, Xj) returns true iff we revise the domain of Xi
    revised = false
    for each x in Di do
       if no value y in Dj allows (x ,y) to satisfy the constraint between Xi and Xj then
          delete x from Di
          revised = true
    return revised
 
 

Figure 6.3 The arc-consistency algorithm AC-3. After applying AC-3, either every arc is arc-consistent, or some variable has an empty domain, indicating that the CSP cannot be solved. The name "AC-3" was used by the algorithm's inventor (Mackworth, 1977) because it's the third version developed in the paper.

Author:

Ruediger Lunde

Constructor Summary

Constructors

Constructor and Description
AC3Strategy()

Method Summary

Modifier and Type	Method and Description
DomainRestoreInfo	reduceDomains(CSP csp) Makes a CSP consisting of binary constraints arc-consistent.
DomainRestoreInfo	reduceDomains(Variable var, java.lang.Object value, CSP csp) Reduces the domain of the specified variable to the specified value and reestablishes arc-consistency.

Methods inherited from class java.lang.Object

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

Constructor Detail

AC3Strategy

public AC3Strategy()

Method Detail

reduceDomains

public DomainRestoreInfo reduceDomains(CSP csp)

Makes a CSP consisting of binary constraints arc-consistent.

Returns:

An object which indicates success/failure and contains data to undo the operation.

reduceDomains

public DomainRestoreInfo reduceDomains(Variable var,
                                       java.lang.Object value,
                                       CSP csp)

Reduces the domain of the specified variable to the specified value and reestablishes arc-consistency. It is assumed that the provided CSP is arc-consistent before the call.

Returns:

An object which indicates success/failure and contains data to undo the operation.