Constraint Satisfaction Problem

定义 Definition

约束满足问题：在给定一组变量及其取值范围（域）的情况下，寻找一种赋值，使其同时满足所有约束条件。常用于排课、地图着色、数独、资源分配等。常缩写为 CSP。（也可与“约束优化问题”区分：后者通常还要最小化/最大化某个目标。）

发音 Pronunciation (IPA)

/kənˈstreɪnt ˌsætɪsˈfækʃən ˈprɑːbləm/

例句 Examples

A Sudoku puzzle is a constraint satisfaction problem.
数独谜题就是一种约束满足问题。

The planner modeled the timetable as a constraint satisfaction problem so that no teacher was double-booked and every class fit the available rooms.
规划系统把课表建模为约束满足问题，从而确保没有老师被重复安排，并且每节课都能匹配到可用教室。

词源 Etymology

该术语由三部分构成：constraint（约束/限制）+ satisfaction（满足）+ problem（问题）。其含义直观：寻找能“满足约束”的解。作为计算机科学与人工智能中的术语，20世纪后期随搜索与约束编程的发展而广泛使用。

相关词 Related Words

• Backtracking
• Constraint
• Constraint Programming
• Domain
• Heuristic
• Optimization
• SAT
• Search
• Variable

文学与经典著作 Literary Works

• Artificial Intelligence: A Modern Approach（Stuart Russell, Peter Norvig）——在问题求解与搜索章节系统介绍CSP框架与算法。
• Constraint Processing（Rina Dechter）——以“constraint satisfaction problem”等核心概念组织约束推理与复杂度分析。
• Principles of Constraint Programming（Krzysztof Apt）——将CSP作为约束编程的基础模型与方法论。