总结
常见的三个启发式:
- 最小剩余值(此变量仍然有多少个有效值)
- 度启发式(此变量影响多少其他变量)
- 最小约束值(什么值将为其他变量留下最多其他值)
以澳大利亚地图为例
题目要求: 对澳大利亚地图的每个州进行着色,每个区域可以涂上红色、绿色或者蓝色,要求是相邻的区域颜色不能相同。(不需要考虑T
,因为T
可以涂任意颜色)
分析:
->根据启发式1,NT
和NSW
的剩余有效值数量都相同。
->根据启发式2,NSW
影响1个变量,但是NT
影响0个,所以下一步应该给NSW
涂色。