级人工智能原理-10-1853.pptx

前面讨论的各种搜索方法都没有用到问题本身的特性信息，只是按照事先设定的线路进行搜索，具有较大的盲目性。事实上，如果能够利用搜索过程所得到的问题自身的一些特性信息来指导搜索过程，则对搜索将是十分有益的。这种利用问题自身的特性信息来引导搜索过程的搜索方法称为启发式搜索。由于启发式搜索方法具有较强的针对性，因此，可以缩小搜索范围，提高搜索效率。; 启发式搜索方法所依据的是问题自身的启发性信息，而启发性信息又是通过估价函数作用到搜索过程中的。; 2．估价函数;例： 八数码难题。设问题的初始状态S0和目标状态 Sg 如前所述，且估价函数为: f（n）=d（n）＋W（n）其中，d（n）表示节点 n在搜索树中的深度； w（n）表示节点 n中“不在位”的数码个数。请计算初始状态S0的估价函数值f（S0）。 解：在本例的估价函数中，取g（n）=d（n），h（n）=W（n）。它说明是用从S0到n的路径上的单位代价表示实际代价，用n中“不在位”的数码个数作为启发信息。一般来说，某节点中的“不在位”的数码个数越多，说明它离目标节点越远。 对初始节点 S0，由于 d（S0）= 0， W（S0）= 3，因此有 f（S0）=0＋3=3? 这个例子仅是为了说明估价函数的含义及估价函数值的计算。在问题搜索过程中，除了需要计算初始节点的估价函数之外，更多的是要计算新生成节点的估价函数值。 ;二. A算法; 每当需要扩展节点时，总是从Open表的所有节点中选择一个估价函数值最小的节点进行扩展。其搜索过程可描述如下： （1）把S0放入Open表中，f(s0)=g（So）＋h（So）； （2）如果Open表为空，则问题无解，失败退出； （3）把Open表的第一个节点取出放入Closed表，记该节点为n； （4）考察节点n是否为目标节点。若是，则找到了问题的解，成功退出； （5）若节点n不可扩展，则转第（2）步； （6）扩展节点n，生成其子节点ni（i=1,2,……），计算每一个子节点的估价值f(ni) （i=1,2,……），并为每一个子节点设置指向父节点的指针，然后将这些子节点放入 Open表中； （7）根据各节点的估价函数值，对Open表中的全部节点按从小到大的顺序重新进行排序； （8）转第（2）步。; 由于上述算法的第（7）步要对Open表中的全部节点按其估价函数值从小到大重新进行排序，这样在算法第（3）步取出的节点就一定是Open表的所有节点中估价函数值最小的一个节点。因此，它是一种全局择优的搜索方式。 对上述算法进一步分析还可以发现：如果取估价函数f(n)=g（n），则它将退化为代价树的广度优先搜索；如果取估价函数f(n)=d（n），则它将退化为广度优先搜索。可见，广度优先搜索和代价树的广度优先搜索是全局择优搜索的两个特例。;例： 八数码难题。; 在局部择优搜索中，每当需要扩展节点时，总是从刚生成的子节点中选择一个估价函数值最小的节点进行扩展。其搜索过程可描述如下： （1）把初始节点S0放入 Open表中，f(S0)=g(S0)+h(S0) ; （2）如果Open表为空，则问题无解，失败退出；（3）把Open表的第一个节点取出放入Closed表，并记该节点为n；（4）考察节点n是否为目标节点。若是，则找到了问题的解，成功退出；（5）若节点n不可扩展，则转第（2）步；（6）扩展节点n，生成其子节点ni(i=1，2，…)，计算每一个子节点的估价值f（ni） （i=1，2，…），并按估价值从小到大的顺序依次放入Open表的首部，并为每一个子节点设置指向父节点的指针，然后转第（2）步。; 由于这一算法的第（6）步仅是把刚生成的子节点按其估价函数值从小到大放入 Open表的首都，这样在算法第（3）步取出的节点仅是刚生成的子节点中估价函数值最小的一个节点。因此，它是一种局部择优的搜索方式。 对这一算法进一步分析也可以发现：如果取估价函数f（ n）=g（n），则它将退化为代价树的深度优先搜索；如果取估价函数f（n）=d（n），则它将退化为深度优先搜索。可见，深度优先搜索和代价树的深度优先搜索是局部择优搜索的两个特例。;三. A*算法; 假设f*(n)为从初始节点S0出发，约束经过节点n到达目标节点的最小代价值。估价函数f(n)是f*(n)的估计值。显然，f*（n）应由以下两部分所组成：一部分是从初始节点到节点n的最小代价，记为g*（n）；另一部分是从节点n到目标节点的最小代价，记为h*（n），当问题有多个目标节点时，应取其中代价最小的一个。因此有