总结

常见的三个启发式:

  1. 最小剩余值(此变量仍然有多少个有效值)
  2. 度启发式(此变量影响多少其他变量)
  3. 最小约束值(什么值将为其他变量留下最多其他值)

以澳大利亚地图为例

CSP

题目要求: 对澳大利亚地图的每个州进行着色,每个区域可以涂上红色、绿色或者蓝色,要求是相邻的区域颜色不能相同。(不需要考虑T,因为T可以涂任意颜色)

分析:
->根据启发式1,NTNSW的剩余有效值数量都相同。
->根据启发式2,NSW影响1个变量,但是NT影响0个,所以下一步应该给NSW涂色。

评论