AI Rookies

CSP — Constraint Satisfaction Problem(约束满足问题)

事实

在给定约束下寻找可行解的问题。

人话

像排喜宴座位表:这俩有过节不能同桌、长辈得坐主桌、伴娘要挨着新娘,所有规矩都迁就到,人人落座不闹掰就算成。

常见于安排和调度,重点是先找到满足条件的解。

相关概念

Optimization
约束满足先求满足条件,优化问题还会继续追求更优。

Heuristic Search
很多约束问题会靠启发式搜索更快找到可行解。

Graph Search
把部分解看成状态节点,就能转成搜索问题。

Knowledge Representation
约束得先被清楚表示,系统才知道哪些解合法。