1、第三章第三章 PartIIPartII有信息的搜索策略有信息的搜索策略内容提要 最佳优先搜索 贪婪最佳优先搜索 A* 搜索 启发式函数 松弛问题 一种搜索策略实际上就是根据树结点扩张的顺序来决定的基本思路：通过对每一个结点设置一个评价函数f(n),找到一个代价最低的未扩散的结点实现：根据结点的评价函数值从低到高在队列中对结点进行排序 大多数评价函数由启发函数h构成h(n):结点到目标结点的最小代价路径的代价估计值最佳优先搜索 vs.一致代价搜索？代价函数的定义不同算法实例贪婪最佳优先搜索A*树评价函数f(n)=h(n)从结点n到目标结点的代价估测值罗马尼亚问题：贪婪最佳优先搜索首先扩展与目标结
2、点估测距离最近的结点罗马尼亚问题中使用直线距离为估测距离完备性？最优性？时间复杂度：O(bm)空间复杂度: O(bm)评价函数f(n) = g(n) + h(n)g(n)=到达结点n已经花费的代价h(n)=结点n到目标节点的评估代价f(n)=通过结点n到达目标结点的总评估代价启发函数h(n)是可采纳的条件：如果对于每个结点n, h(n)=h2(n) (两个函数都是可采纳的)，我们说h2(n)比h1(n)有优势。典型的搜索代价(平均结点扩展数)：d=12 IDS = 3,644,035 nodesA*(h1) = 227 nodesA*(h2) = 73 nodesd=24 IDS = too many nodesA*(h1) = 39,135 nodesA*(h2) = 1,641 nodes减少了行动限制的问题称为松弛问题松弛问题。松弛问题增加了状态空间的边原有问题的任一最优解同样也是松弛问题的最优解，但松弛问题可能存在更好的解。八数码问题行动描述棋子可以从方格A移动到方格B如果A与B水平或者垂直相邻并且B是空的三个松弛问题：去掉条件B的空的： h2将给出最短解的确切步数去掉条件AB相邻上述两者都去掉： h1将给出最短解的确切步数 最佳优先搜索 贪婪最佳优先搜索贪婪最佳优先搜索 A A* * 搜索搜索 启发式函数 松弛问题QA？
