问题背景
约束满足问题（Constraint Satisfaction Problem, CSP）是人工智能中的核心问题之一。一个CSP由三个要素组成：
– 变量集合 $X = {X_1, X_2, …, X_n}$
– 值域集合 $D = {D_1, D_2, …, D_n}$，其中 $D_i$ 是 $X_i$ 可能的取值集合
– 约束集合 $C$，定义变量之间的允许关系
经典CSP实例包括数独、地图着色、课程表排课、数织（Nonogram）等。当问题规模增大时，暴力搜索的组合爆炸使得直接回溯求解不可行。
AC-3算法（Arc Consistency 3）由Mackworth于1977年提出，是最经典的约束传播算法。它通过反复检查变量之间的约束关系，剔除值域中不可能满足约束的值，从而大幅缩减搜索空间。
核心原理
弧一致性定义
一条弧 $(X_i, X_j)$ 是弧一致的，当且仅当对于 $D_i$ 中的每一个值 $v$，在 $D_j$ 中至少存在一个值 $w$ 使得约束 $C(X_i, X_j)$ 被满足。此时称 $w$ 是 $v$ 的支持。
AC-3算法流程
- 初始化队列：将所有有向弧 $(X_i, X_j)$ 加入队列（对于每对约束双向添加）
- 循环处理队列：
- 取出弧 $(X_i, X_j)$
- 调用
Revise(X_i, X_j)：遍历 $D_i$ 中每个值 $v$，若 $D_j$ 中没有值支持 $v$，则将 $v$ 从 $D_i$ 删除 - 若 $D_i$ 被修改（有值被删除），则将所有与 $X_i$ 相关的弧 $(X_k, X_i)$（$k \neq j$）重新加入队列
- 终止条件：队列为空，或某个值域变为空集（问题无解）
Revise操作
function Revise(Xi, Xj):
revised = false
for each v in Di:
if no w in Dj satisfies constraint(Xi=v, Xj=w):
delete v from Di
revised = true
return revised
Java实现
import java.util.*;
/**
* AC-3：弧一致性约束传播算法
* 用于求解约束满足问题（CSP），如地图着色、数独等
* 时间复杂度：O(n^2 * d^3)，其中n为变量数，d为最大值域大小
* 空间复杂度：O(n^2 + n*d)
*/
public class AC3Solver {
// 变量数量
private int numVars;
// 每个变量的值域
private List<Integer>[] domains;
// 邻接关系：var -> 与该变量有约束的变量集合
private Set<Integer>[] neighbors;
// 二元约束：constraint[var1][var2] 表示 (var1, var2) 的允许值对集合
private Set<String>[][] constraints;
// 约束名称（用于调试输出）
private String[][] constraintNames;
// 弧队列中的元素
private static class Arc {
int from; // 被修订的变量
int to; // 参考变量
Arc(int from, int to) {
this.from = from;
this.to = to;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Arc)) return false;
Arc arc = (Arc) o;
return from == arc.from && to == arc.to;
}
@Override
public int hashCode() {
return from * 131 + to;
}
@Override
public String toString() {
return "(" + from + " -> " + to + ")";
}
}
@SuppressWarnings("unchecked")
public AC3Solver(int numVars) {
this.numVars = numVars;
this.domains = new ArrayList[numVars];
this.neighbors = new Set[numVars];
this.constraints = new Set[numVars][numVars];
this.constraintNames = new String[numVars][numVars];
for (int i = 0; i < numVars; i++) {
domains[i] = new ArrayList<>();
neighbors[i] = new HashSet<>();
}
}
/**
* 设置变量的值域
*/
public void setDomain(int var, List<Integer> domain) {
domains[var] = new ArrayList<>(domain);
}
/**
* 添加二元约束：var1 和 var2 之间必须满足的关系
* @param var1 变量1
* @param var2 变量2
* @param allowedPairs 允许的值对集合，每个值对用 "v1,v2" 格式表示
* @param name 约束名称
*/
public void addConstraint(int var1, int var2, Set<String> allowedPairs, String name) {
neighbors[var1].add(var2);
neighbors[var2].add(var1);
constraints[var1][var2] = new HashSet<>(allowedPairs);
constraints[var2][var1] = new HashSet<>();
// 反向约束：交换值对
for (String pair : allowedPairs) {
String[] parts = pair.split(",");
constraints[var2][var1].add(parts[1] + "," + parts[0]);
}
constraintNames[var1][var2] = name;
constraintNames[var2][var1] = name;
}
/**
* 添加不等约束（常见约束：两个变量不能取相同值）
*/
public void addNotEqualConstraint(int var1, int var2, String name) {
// 不等约束的允许值对：所有 (v1, v2) 其中 v1 != v2
Set<String> allowed = new HashSet<>();
for (int v1 : domains[var1]) {
for (int v2 : domains[var2]) {
if (v1 != v2) {
allowed.add(v1 + "," + v2);
}
}
}
addConstraint(var1, var2, allowed, name);
}
/**
* Revise操作：检查并修订弧 (from -> to)
* @return 如果from的值域被修改则返回true
*/
private boolean revise(int from, int to) {
boolean revised = false;
List<Integer> fromDomain = domains[from];
List<Integer> toDomain = domains[to];
Set<String> constraint = constraints[from][to];
// 遍历from的值域中每个值
Iterator<Integer> it = fromDomain.iterator();
while (it.hasNext()) {
int v = it.next();
boolean hasSupport = false;
// 检查to的值域中是否存在支持v的值
for (int w : toDomain) {
if (constraint.contains(v + "," + w)) {
hasSupport = true;
break;
}
}
// 如果没有支持值，从from的值域中删除v
if (!hasSupport) {
it.remove();
revised = true;
System.out.println(" 删除 X" + from + "=" + v +
"，因为弧 (X" + from + " -> X" + to + ") 无支持");
}
}
return revised;
}
/**
* AC-3核心算法
* @return 如果所有值域非空返回true（可能仍有解），否则false（无解）
*/
public boolean ac3() {
Queue<Arc> queue = new LinkedList<>();
// 初始化：将所有弧加入队列
for (int i = 0; i < numVars; i++) {
for (int j : neighbors[i]) {
if (i != j) {
queue.offer(new Arc(i, j));
}
}
}
System.out.println("AC-3开始，初始弧数: " + queue.size());
int step = 0;
while (!queue.isEmpty()) {
Arc arc = queue.poll();
step++;
System.out.println("\n步骤 " + step + ": 处理弧 " + arc);
if (revise(arc.from, arc.to)) {
// 如果值域被修改
if (domains[arc.from].isEmpty()) {
System.out.println("X" + arc.from + " 值域为空，问题无解！");
return false; // 值域为空，问题无解
}
// 将所有指向from的弧重新加入队列（邻居的约束可能受影响）
for (int neighbor : neighbors[arc.from]) {
if (neighbor != arc.to) {
Arc newArc = new Arc(neighbor, arc.from);
if (!queue.contains(newArc)) {
queue.offer(newArc);
System.out.println(" 加入新弧: " + newArc);
}
}
}
}
}
System.out.println("\nAC-3完成，总步骤: " + step);
return true;
}
/**
* 获取当前值域状态
*/
public void printDomains() {
System.out.println("当前值域状态:");
for (int i = 0; i < numVars; i++) {
System.out.println(" X" + i + " = " + domains[i]);
}
}
/**
* 获取值域大小统计
*/
public int getTotalDomainSize() {
int total = 0;
for (int i = 0; i < numVars; i++) {
total += domains[i].size();
}
return total;
}
/**
* 深度优先搜索回溯求解（在AC-3预处理之后使用）
*/
public List<Integer> backtrackSolve() {
List<Integer> assignment = new ArrayList<>(Collections.nCopies(numVars, -1));
if (backtrack(assignment, 0)) {
return assignment;
}
return null;
}
private boolean backtrack(List<Integer> assignment, int varIndex) {
if (varIndex == numVars) {
return true; // 所有变量都已赋值
}
for (int value : new ArrayList<>(domains[varIndex])) {
assignment.set(varIndex, value);
// 检查与已赋值变量的约束
boolean consistent = true;
for (int prev = 0; prev < varIndex; prev++) {
if (assignment.get(prev) != -1) {
Set<String> cons = constraints[varIndex][prev];
if (cons != null && !cons.contains(value + "," + assignment.get(prev))) {
consistent = false;
break;
}
}
}
if (consistent) {
if (backtrack(assignment, varIndex + 1)) {
return true;
}
}
}
assignment.set(varIndex, -1);
return false;
}
/**
* 主函数：测试AC-3算法
*/
public static void main(String[] args) {
// 示例1：澳大利亚地图着色问题
// 变量：WA, NT, SA, Q, NSW, V, T (7个区域)
// 值域：{红, 绿, 蓝} (用0,1,2表示)
// 约束：相邻区域颜色不同
System.out.println("=== 示例1：澳大利亚地图着色 ===\n");
AC3Solver mapSolver = new AC3Solver(7);
List<Integer> colors = Arrays.asList(0, 1, 2);
for (int i = 0; i < 7; i++) {
mapSolver.setDomain(i, colors);
}
// 澳大利亚地图相邻关系 (简化版)
// 0=WA, 1=NT, 2=SA, 3=Q, 4=NSW, 5=V, 6=T
int[][] adjacencies = {
{0, 1}, {0, 2}, // WA-NT, WA-SA
{1, 2}, {1, 3}, // NT-SA, NT-Q
{2, 3}, {2, 4}, {2, 5}, // SA-Q, SA-NSW, SA-V
{3, 4}, // Q-NSW
{4, 5} // NSW-V
// T(6)是岛屿，不与任何区域相邻
};
for (int[] adj : adjacencies) {
mapSolver.addNotEqualConstraint(adj[0], adj[1], "Adjacent");
}
mapSolver.printDomains();
boolean solvable = mapSolver.ac3();
System.out.println("\nAC-3后值域状态:");
mapSolver.printDomains();
System.out.println("\n是否可能可解: " + solvable);
if (solvable) {
List<Integer> solution = mapSolver.backtrackSolve();
if (solution != null) {
System.out.println("\n找到解: " + solution);
String[] colorNames = {"红", "绿", "蓝"};
String[] regions = {"WA", "NT", "SA", "Q", "NSW", "V", "T"};
for (int i = 0; i < 7; i++) {
System.out.println(" " + regions[i] + " -> " + colorNames[solution.get(i)]);
}
}
}
// 示例2：无解情况演示
System.out.println("\n=== 示例2：无解情况（两个变量必须不同但值域相同且只有一个值） ===\n");
AC3Solver unsolvable = new AC3Solver(2);
unsolvable.setDomain(0, Arrays.asList(1));
unsolvable.setDomain(1, Arrays.asList(1));
unsolvable.addNotEqualConstraint(0, 1, "NotEqual");
boolean result = unsolvable.ac3();
System.out.println("可解性: " + result);
// 示例3：数独简化版（4x4）
System.out.println("\n=== 示例3：4x4数独简化版 ===\n");
// 4x4数独，16个变量，值域{1,2,3,4}
AC3Solver sudoku = new AC3Solver(16);
List<Integer> digits = Arrays.asList(1, 2, 3, 4);
for (int i = 0; i < 16; i++) {
sudoku.setDomain(i, digits);
}
// 添加约束：同行、同列、同2x2宫格内数字不同
// 变量编号：row*4 + col
for (int r = 0; r < 4; r++) {
for (int c1 = 0; c1 < 4; c1++) {
for (int c2 = c1 + 1; c2 < 4; c2++) {
sudoku.addNotEqualConstraint(r * 4 + c1, r * 4 + c2, "Row");
}
}
}
for (int c = 0; c < 4; c++) {
for (int r1 = 0; r1 < 4; r1++) {
for (int r2 = r1 + 1; r2 < 4; r2++) {
sudoku.addNotEqualConstraint(r1 * 4 + c, r2 * 4 + c, "Col");
}
}
}
// 2x2宫格约束
for (int boxR = 0; boxR < 2; boxR++) {
for (int boxC = 0; boxC < 2; boxC++) {
int[] cells = new int[4];
int idx = 0;
for (int dr = 0; dr < 2; dr++) {
for (int dc = 0; dc < 2; dc++) {
cells[idx++] = (boxR * 2 + dr) * 4 + (boxC * 2 + dc);
}
}
for (int i = 0; i < 4; i++) {
for (int j = i + 1; j < 4; j++) {
sudoku.addNotEqualConstraint(cells[i], cells[j], "Box");
}
}
}
}
// 预设一些值（模拟数独题目）
sudoku.domains[0] = new ArrayList<>(Arrays.asList(1)); // (0,0)=1
sudoku.domains[5] = new ArrayList<>(Arrays.asList(2)); // (1,1)=2
sudoku.domains[10] = new ArrayList<>(Arrays.asList(3)); // (2,2)=3
sudoku.domains[15] = new ArrayList<>(Arrays.asList(4)); // (3,3)=4
boolean sudokuSolvable = sudoku.ac3();
System.out.println("\nAC-3预处理后值域状态（部分）:");
for (int r = 0; r < 4; r++) {
System.out.print("行" + r + ": ");
for (int c = 0; c < 4; c++) {
System.out.print(sudoku.domains[r * 4 + c] + " ");
}
System.out.println();
}
System.out.println("\n是否可能可解: " + sudokuSolvable);
}
}
复杂度分析
时间复杂度
- 初始化队列：$O(n^2)$，将所有弧加入队列
- Revise操作：每次检查 $D_i$ 中每个值在 $D_j$ 中的支持，复杂度 $O(d^2)$，其中 $d$ 是值域大小
- 弧处理次数：每条弧最多被处理 $O(d)$ 次（因为值域最多被修改 $d$ 次）
- 总复杂度：$O(n^2 \cdot d^3)$，其中 $n$ 为变量数，$d$ 为最大值域大小
对于二元约束且值域大小为常数的情况（如地图着色 $d=3$），复杂度为 $O(n^2)$。
空间复杂度
- 值域存储：$O(n \cdot d)$
- 约束存储：$O(n^2 \cdot d^2)$（存储所有允许值对）
- 弧队列：$O(n^2)$
优化扩展
AC-4算法
AC-3在每次Revise时需要遍历整个值域寻找支持值。AC-4通过预处理支持计数，将Revise优化到 $O(1)$ 判断，总复杂度降至 $O(n^2 \cdot d^2)$。
MAC（Maintaining Arc Consistency）
在回溯搜索的每个节点都运行AC-3，动态维护弧一致性。虽然单次开销更大，但可以更早发现冲突，大幅减少搜索树节点数。
更高阶一致性
- 路径一致性（PC）：检查三元组约束
- k-一致性：推广到k元约束
应用场景
- 数独求解：通过约束传播快速填充确定格
- 地图着色：四色定理的实际验证与应用
- 课程表排课：教师、教室、时间段的约束满足
- 数织（Nonogram）：行列约束的交叉传播
- 规划与调度：资源分配、任务调度中的约束处理
