Arc Consistency

释义 Definition

（约束满足问题 CSP 中的）弧一致性：对每一条有向约束（从变量 \(X\) 指向变量 \(Y\)），要求 \(X\) 的每个可能取值，都能在 \(Y\) 的取值域中找到至少一个与之相容的取值；否则就把该取值从 \(X\) 的域中删除，以达到剪枝/约束传播的目的。（常见算法如 AC-3）

发音 Pronunciation (IPA)

/rk knsstnsi/

例句 Examples

Arc consistency removes values that cannot be part of any solution.
弧一致性会删除那些不可能出现在任何解中的取值。

After enforcing arc consistency on the network, several domains shrink, making backtracking much faster.
在对约束网络施加弧一致性之后，多个变量的取值域变小，从而使回溯搜索快得多。

词源 Etymology

arc 原意为“弧、弓形”，在图论/网络语境中常借指“边/有向边”；consistency 表示“一致性”。合在一起，“arc consistency”强调的是：沿着约束图中的“弧（有向约束）”检查并维持取值的相容一致，通过删除不相容取值来缩小搜索空间。

相关词 Related Words

• Constraint
• CSP
• Domain
• Pruning
• Constraint Propagation
• Backtracking
• Node Consistency
• Path Consistency
• AC-3
• Inference

文学与经典著作 Literary Works

• Artificial Intelligence: A Modern Approach（Russell & Norvig）在约束满足与推理章节中介绍弧一致性与 AC-3 等传播方法。
• Constraint Processing（Rina Dechter）系统讨论一致性技术（包括弧一致性）及其理论与算法。
• Foundations of Constraint Satisfaction（Edward Tsang）涵盖 CSP 基础概念与一致性维护方法（含 arc consistency）。