北大公开课-人工智能基础 37 约束满足问题之CSP的回溯搜索

CSP约束满足的回溯搜索，本质上也是一中深度优先搜索算法

但是增加了类似剪枝的功能，如果回溯时发现部分后续节点不是最优的，则抛弃这些后续节点

用约束满足问题来解决四皇后问题

CSP回溯算法的逻辑：

对于回溯问题的优化三个思路

回溯搜索不仅仅搜索的是最优策略，也要搜索约束条件

如澳大利亚的地图上色问题

一方面是约束问题（相邻省份不能用相同的颜色）

通过回溯，组合搜索（一个省份的颜色赋值，取决于所有相邻省份的已确定的颜色赋值）

启发式函数

智能回溯

回到上一步，查看上一步如果可能赋值得到的群体不同后续策略

并倾向于选择上一步能获得最多后续可能策略的步骤