4. 常见约束求解算法概览：回溯搜索、前向检查、弧一致性、冲突驱动子句学习（CDCL）

在智能寻源场景中，约束求解器需要从海量供应商组合中快速找到满足所有业务约束（如价格、交期、产能、合规）的可行解。不同的求解算法在搜索效率、内存消耗和可扩展性上差异显著。本节将系统梳理四种核心算法：回溯搜索、前向检查、弧一致性和冲突驱动子句学习（CDCL），并对比其适用场景。

4.1 算法演进关系与核心思想

四种算法并非孤立存在，而是沿着“搜索 + 推理”的轴线逐步增强。下表从核心机制、剪枝能力和典型应用三个维度进行对比：

4.2 回溯搜索：最基础的搜索框架

回溯搜索是约束求解的“地基”。它按顺序为变量赋值，每次赋值后检查当前部分赋值是否违反约束。若违反则撤销当前赋值（回溯），尝试下一个值；若所有值都尝试失败，则回溯到上一个变量。

// 回溯搜索伪代码
function backtrack(assignment, csp):
    if assignment is complete:
        return assignment
    var = selectUnassignedVariable(csp)
    for value in orderDomainValues(var, assignment, csp):
        if isConsistent(var, value, assignment, csp):
            assignment[var] = value
            result = backtrack(assignment, csp)
            if result != failure:
                return result
            delete assignment[var]
    return failure

局限性： 回溯搜索不进行任何前瞻性推理，当遇到“死胡同”时只能回退，容易陷入指数级搜索空间。在寻源场景中，若供应商数量超过 20 家且约束超过 5 条，纯回溯往往不可接受。

4.3 前向检查：在赋值时提前预警

前向检查在回溯的基础上增加了一步：每次为变量 X 赋值后，立即检查所有与 X 相关的未赋值变量 Y，从 Y 的域中删除与当前赋值冲突的值。若某个 Y 的域变为空，则立即回溯，避免无效搜索。

前向检查的剪枝效果取决于约束图的密度。在稀疏约束图中，其优势不明显；在密集约束图中，可减少 30%~60% 的搜索节点。

4.4 弧一致性：通过约束传播全局剪枝

弧一致性是一种更强的推理机制。它不等待赋值发生，而是在搜索开始前和搜索过程中反复检查所有二元约束，删除任何不可能出现在任何解中的值。一个约束网络是弧一致的，当且仅当对于每个变量 X 和每个约束 C(X, Y)，X 域中的每个值都在 Y 的域中有至少一个支持值。

最经典的弧一致性算法是 AC-3，其时间复杂度为 O(d³)（d 为域大小），在寻源问题中通常作为预处理步骤使用。

// AC-3 算法核心逻辑
function AC-3(csp):
    queue = all arcs (X, Y) in csp
    while queue not empty:
        (X, Y) = queue.pop()
        if revise(csp, X, Y):
            if domain[X] is empty:
                return failure
            for each Z in neighbors[X] except Y:
                queue.push(Z, X)
    return success

function revise(csp, X, Y):
    removed = false
    for each x in domain[X]:
        if no y in domain[Y] satisfies constraint(X, Y):
            delete x from domain[X]
            removed = true
    return removed

4.5 冲突驱动子句学习（CDCL）：现代 SAT/SMT 求解器的核心

CDCL 是目前工业级约束求解器（如 Z3、MiniSat、Glucose）的基石。它结合了回溯搜索和冲突分析，核心流程如下：

1. 决策（Decision）： 选择一个未赋值变量并赋予一个值。
2. 布尔约束传播（BCP）： 利用当前赋值和已学习子句推导出必然成立的赋值。
3. 冲突检测： 若发现矛盾（如同时要求 A=true 和 A=false），则进入冲突分析。
4. 冲突分析： 通过蕴含图（Implication Graph）找出导致冲突的最小原因集，生成一个新的学习子句。
5. 智能回溯： 根据学习子句跳回到冲突原因之前的决策层，而非简单回退一层。
6. 重启（Restart）： 定期清空当前赋值，但保留已学习子句，避免陷入局部搜索陷阱。

4.6 算法在智能寻源 API 中的调用策略

在实际的寻源 API 设计中，通常不会只使用单一算法，而是采用分层调用策略：

4.7 算法选择决策树

在智能寻源 API 的接口调用中，可根据以下决策树快速选择算法：

• 约束类型以算术不等式为主（如价格、交期范围）： 优先使用弧一致性预处理 + 前向检查搜索。算术约束的传播效率高，弧一致性可快速缩小域。
• 约束包含大量布尔逻辑（如条件选择、互斥规则）： 直接使用 CDCL。逻辑约束的冲突分析能力是 CDCL 的核心优势。
• 问题规模极小（变量 < 30，约束 < 10）： 使用纯回溯搜索即可，避免算法本身的额外开销。
• 需要快速响应（API 延迟 < 100ms）： 使用前向检查 + 时间限制，配合 max_backtracks 参数控制搜索深度。