人工智能原理第2章搜索技术（下）本章内容2.1搜索与问题求解2.2无信息搜索策略2.3启发式搜索策略2.4局部搜索算法2.5约束满足问题2.6博弈搜索参考书目附录A*算法可采纳性的证明2.4局部搜索算法2.4.1局部搜索与最优化2.4.2爬山法搜索2.4.3模拟退火搜索2.4.4局部剪枝搜索2.4.5遗传算法局部搜索算法局部搜索算法的应用状态空间地形图(2)局部搜索算法2.4.2爬山法搜索爬山法搜索的局限爬山法搜索的变形2.4.3模拟退火搜索模拟退火的解决思路(1)模拟退火的解决思路(2)2.4.4局部剪枝搜索随机剪枝搜索2.4.5遗传算法遗传算法的操作遗传算法简要描述遗传算法的特点遗传算法的模式2.5约束满足问题2.5.1约束满足问题的定义2.5.2CSP的回溯搜索2.5.3变量赋值次序的启发式2.5.4变量约束的启发式2.5.5关于失败变量的启发式2.5.1约束满足问题的定义CSP问题的解从搜索角度看待CSP问题例1：澳大利亚地图染色问题(1)对应于澳大利亚地图的约束图,相互关联的节点用边连接例2：密码算术问题(1)各算式约束CSP问题的分类CSP问题求解的复杂度2.5.2CSP的回溯搜索简单回溯法生成的搜索树回溯搜索的通用算法2.5.3变量赋值次序的启发式MRV启发式度启发式2.5.4变量约束的启发式前向检验约束传播—弧相容弧相容(1)弧相容(2)特殊约束2.5.5关于失败变量的启发式冲突集后向跳转冲突指导的后向跳转2.6博弈搜索2.6.1极大极小决策2.6.2-剪枝博弈搜索问题与方法博弈游戏的描述井字棋的博弈树2.6.1极大极小决策极大极小值(1)极大极小值(2)极大极小值(3)极大极小值(4)极大极小值算法说明极大极小值算法2.6.2-剪枝博弈树的剪枝(1)博弈树的剪枝(2)博弈树的剪枝(3)-剪枝算法(1)-剪枝算法(2)-剪枝算法(3)-剪枝算法的说明-剪枝的效率本章复习提示参考书目附录A*算法可采纳性的证明A*算法可采纳性证明的步骤定理1的证明(1)定理1的证明(2)引理1的证明(1)引理1的证明(2)引理2的证明(1)引理2的证明(2)定理2的证明定理3的证明(1)定理3的证明(2)推论2