人工智能第3章通过搜索进行问题的求解

1、PPT模板下载： 要进行问题求解，首先要讨论的是对问题以及其解的精确定义，我们将通过一些实例来说明如何去描述一个问题及其解。搜索，是指从问题出发寻找解的过程。PPT模板下载： 例子： 罗马尼亚 Agent在罗马尼亚城市Arad度假，假设她有张第二天飞往Bucharest的机票，而且是不能退票。目标：前往Bucharest任务：找到能够使它到达目标的动作序列Q: 决策所要考虑的行动和状态的种类？ a:在开车从一个主要城镇到另一个城镇的层次上考虑行动。Agent设计三个步骤：形式化、搜索、执行。形式化形式化执行执行搜索搜索行动序列行动序列（问题的解）（问题的解）PPT模板下载： 问题的形式化定义初

2、始状态:智能体的起始状态对Agent可能行动的描述:给定一个特殊状态s，ACTION(s)返回状态s下可以执行的动作集合。如，In(Arad)可应用行动为Go(S)Go(T)Go(Z)对每个动作的描述：转移模型，RESULT(s,a)表示，状态s下执行行动a后达到状态.目标测试：确定给定的状态是不是目标状态路径耗散：为每条路径分配一个数值化的耗散值问题的解：从初始状态到目标状态的路径最优解：路径耗散最小的解PPT模板下载： 环境特性静态的 -完成问题形式化和求解的时候不在考虑环境可能的变化确定性的 -问题的解是行动的单一序列 -在问题求解的过程中感知信息不起作用可观察的PPT模板下载： PPT

3、模板下载： 问题的解解释从初始值到目标状态的路径解的质量由路径耗散函数值最小的解PPT模板下载： 玩具问题状态：8个可能的状态PPT模板下载： 玩具问题状态：由Agent位置和灰尘位置确定初始状态：任何形态都可能被设计为初始。后续函数：用来产生通过左移、右移、吸尘能够到达的合法状态目标测试：用来检测是否所有的方格都干净路径耗散：假设每一步的耗散值为1PPT模板下载： 玩具问题PPT模板下载： 八角数码的游戏状态：8个棋子以及空格在9格棋盘初始：任意状态都可以作为初始，但要达到一特定的目标态，只有一半的状态可以作为起点。后继函数：产生4个行动（上，下，左，右）可以到达合法状态目标测试：用来检测是

4、否匹配右图。路径耗散：每一步耗散值1PPT模板下载： 八皇后问题皇后可以攻击和她在同一行，同一列，同一斜对角线的任何棋子。有专用的算法，这里是搜索的测试用例分为两类： -增量形式化：每次行动添加一个皇后到状态中去。 -完整状态形式化：8个皇后都在棋盘上并且不断移动。状态：0-8个皇后任意摆放都是一个状态初始状态：空棋盘后续函数：将增加皇后的棋盘返回目标测试：8个皇后都在棋盘上，并且无 法相互攻击。PPT模板下载： 现实世界寻径问题寻径问题旅游时面临飞机航行问题旅游时面临飞机航行问题状态：位置和当前时间初始状态：用户在咨询时确定后续函数： 乘坐的航班、飞行时间、候机时间状态目标测试：是否在预定时

5、间到达目的地路径耗散：等待时间、飞行时间、座位的质量、费用旅行商问题等等PPT模板下载： 搜索树在对问题进行格式化之后，我们现在需要对问题求解。第一步，检测该节点是不是否为目标状态，如In(Arad),选择各种行动。生成一个状态集，In(Sibiu),In(T),In(Z)。接着从其中选择一个考虑，等发现不能求解在选择其他的。PPT模板下载： 搜索树PPT模板下载： 搜索树你会发现有回路产生，回路是冗余的特殊情况。有些问题的冗余是无法避免，所以要避免探索的冗余就是记住曾经走过的路。探索集：记录每一个以探索的节点PPT模板下载： 搜索算法基础一个状态空间可以有无数条路径，即搜索树可有无数个节点。

6、例如，从Arad到Sibiu的路径可包括重复出现的节点。节点的数据结构：-State：状态空间-Parent-Node：搜索树中产生节点的节点 （父节点）-Action ：父节点生成节点是所采取的行动-Path-Cost：从初始状态到达该节点消耗PPT模板下载： 搜索算法基础PPT模板下载： 问题求解算法性能完备性：有解时能否保证找到解最优性：是否有找到最优解时间复杂度：根据搜索过程中产生的节点数目来度量空间复杂度：在执行搜索的过程中需要的内存，取决于储存的最大节点数。时间与空间的复杂度往往要与问题难度的某种度量一起考虑PPT模板下载： 广度优先搜索当b有限时，搜索是完备的如果路径耗散是节点深

7、度的非递减函数，则解是最优的。假设每个状态都有b个后继，解的深度是d，则找到解时，所访问过的节点数为O(bd+1)。PPT模板下载： 代价一致搜索-bfs算法的引伸：扩展路径消耗最低的节点-有可能陷入无限循环-如果规定每一步的耗散都大等于某个小的正值常数，那么就能保证完备性和最优性。-复杂度与b和最优解的耗散值有关。PPT模板下载： 代价一致搜索PPT模板下载： 深度优先搜索对内存的需求很少有可能错误地选择一条分支而且沿着一条很长的路径（甚至是无限）走下去。-非最优-非完备-在最坏情况下，dfs所生成的节点数是O(bm)PPT模板下载： 深度优先搜索PPT模板下载： 深度受限搜索当b有限时，搜

8、索是完备的如果路径耗散是节点深度的非递减函数，则解是最优的。空间需求是O(bd)PPT模板下载： 迭代加深的深度优先搜索不断增大深度限制，直到找到目标节点。PPT模板下载： 迭代加深的深度优先搜索不断增大深度限制，直到找到目标节点。PPT模板下载： 迭代加深的深度优先搜索结合了深度优先和广度有限的优点：空间需求和深度优先一样小完备的当路径耗散是节点深度的非递减函数时是最优的当搜索空间很大且解的深度未知，迭代深入搜索是首先。PPT模板下载： 代价一致搜索的迭代搜索代价一致搜索的迭代搜索:不断增加的路径耗散限双向搜索双向搜索:运行两个同时的搜索：-向前搜索从初始状态向前搜索-向后搜索-从目标状态向

9、后搜索-扩展节点前检查该节点是否在另一棵树的边缘空间需求大当两个搜索都是广度优先搜索时是完备的和最优的PPT模板下载： q前面讨论的方法都是无信息的搜索方法,即都没有利用问题本身的特性信息,在决定要被扩展的节点时,都没有考虑该节点在解的路径上的可能性有多大,它是否有利于问题求解以及求出的解是否为最优。q启发式搜索要用到问题自身的某些特性信息,以指导搜索朝着最有希望的方向前进。启发信息的强度强：降低搜索工作量，但可能导致找不到最优解弱：一般导致工作量加大，极限情况下变为无信息搜索，但可能可以找到最优解PPT模板下载： q状态空间状态空间状态空间：在求解一个问题时，从初始状态到目标状态寻找一条解的

10、过程，这个过程会可能产生很多的解，进而构成了一个图。启发式搜索就是在状态空间对每一个位置行进评估进而找到一个最优解。PPT模板下载： q启发性信息和估价函数用于指导搜索过程,且与具体问题有关的控制性信息称为为启发性信息用于评价节点重要性的函数称为估价函数.记为 f(x) = g(x) + h(x)g(x)为从初始节点S0到节点x已经实际付出的代价h(x)是从节点x到目标节点Sg的最优路径的估价代价,体现了问题的启发性信息,称为启发函数f(x)表示从初始节点经过节点x到达目标节点的最优路径的代价估价值。PPT模板下载： q最佳优先搜索最佳优先搜索 思想:对每个节点使用估价函数,估计希望: 扩展最有希望未扩展的节点 主要包括: - 贪婪最佳优先搜索 - A*算法PPT模板下载： q最佳优先搜索最佳优先搜索 思想:对每个节点使用估价函数,估计希望: 扩展最有希望未扩展的节点 主要包括: - 贪婪最佳优先搜索 - A*算法PPT模板下载： 启发失函数 f(n)=h(n) :从n到最近的目标节点代价的估计 这里采用hSLD(n): 从n到Bucharest的直线距离贪婪算法扩展看来与目标最近的节点PPT模板下载： q 思想: 避免对已经扩展的路径进行再扩展q 评价函数为: f(x) = g(x) + h(x) g(x)到达节点以花费的代价