约束满足问题

约束满足问题旨在为一组变量分配值，同时满足它们之间的所有约束，为许多组合问题提供统一的表示。

Definition

约束满足问题由一组变量、每个变量可能值的域以及一组指定允许值组合的约束组成；解决方案是满足所有约束的完整赋值。

Scope

本主题涵盖约束满足问题（CSP）的形式化（变量、域、约束）及其求解算法：带有变量和值排序启发式方法的反向追踪搜索、约束传播和一致性技术（节点、弧和路径一致性，例如AC-3算法），以及问题结构的利用（树形CSP、割集条件化）。它与CSP的局部搜索以及更广泛的约束编程实践相关。类似问题的连续优化和基于学习的公式不在此范围之内。

Core questions

• 如何将各种问题（调度、地图着色、谜题）统一表示为变量、域和约束？
• 约束传播如何在搜索之前和期间修剪值以减少回溯？
• 哪些变量和值排序启发式方法能使回溯搜索更高效？
• 如何利用约束图的结构（例如，树形结构）进行高效求解？

Key concepts

• 变量、域、约束
• 约束图
• 回溯搜索
• 前向检查
• 弧一致性和AC-3
• 最小剩余值启发式
• 约束传播
• 树形CSP和割集条件化

Key theories

弧一致性和约束传播

当每个变量的每个值在其每个相邻变量中都有一个一致的伙伴时，CSP就是弧一致的；AC-3等算法通过重复移除不支持的值来强制执行此操作，通常在搜索之前或期间大幅缩小域。

带启发式方法的反向追踪搜索

CSP通过带有回溯的深度优先赋值来解决，通过启发式方法（例如选择约束最多的变量（最小剩余值）、约束最少的值）以及通过交错前向检查或传播来及早发现死胡同，从而使其变得实用。

结构利用

当约束图是树形结构时，CSP可以在与变量数量成线性关系的时间内解决，并且可以通过割集条件化或树分解将接近树形的结构简化为这种情况。

Clinical relevance

CSP技术是调度和排班、资源分配、产品配置、硬件和软件验证以及数独等谜题求解器的核心；基于这些思想构建的约束编程语言和求解器广泛应用于工业规划和运筹学。

History

约束网络起源于20世纪70年代的场景标注和关系一致性研究，Mackworth在1977年的论文中正式提出了节点、弧和路径一致性。在20世纪80年代至90年代，该领域发展成为约束编程，并在2006年的《约束编程手册》中得到巩固，至今仍是人工智能的标准主题。

Key figures

• Alan K. Mackworth
• Rina Dechter
• Eugene C. Freuder
• Ugo Montanari

Seminal works

• mackworth1977
• dechter2003
• rossi2006

Frequently asked questions

约束满足问题与一般搜索问题有何不同？

一般搜索问题将状态视为黑箱，但CSP将状态的内部结构暴露为受约束的变量赋值。这种结构使得CSP求解器能够利用通用搜索无法利用的约束传播和排序启发式方法。

弧一致性有什么作用？

弧一致性从变量的域中移除那些在相邻变量中没有兼容值的值，考虑到它们之间的约束。在搜索之前和期间强制执行弧一致性可以修剪搜索空间，有时甚至无需回溯即可直接解决问题。