《AI课件01章第1章启发式搜索1章节》由会员分享，可在线阅读，更多相关《AI课件01章第1章启发式搜索1章节（34页珍藏版）》请在金锄头文库上搜索。
1、1.4 启发式图搜索,启发式搜索,定义：为减小搜索范围而需要利用某些已知的、有关具体问题领域的特性信息。此种信息叫做启发信息。利用启发信息的搜索方法叫做启发式搜索方法。 特点：重排OPEN表，选择最有希望的节点加以扩展 种类：最佳优先搜索、A*算法等,启发式搜索策略,有关具体问题领域的信息常常可以用来简化搜索。一个比较灵活(但代价也较大)的利用启发信息的方法是应用某些准则来重新排列每一步OPEN表中所有节点的顺序。然后，搜索就可能沿着某个被认为是最有希望的边缘区段向外扩展。应用这种排序过程，需要某些估算节点“希望”的量度，这种量度叫做估价函数(evalution function),估价函数
2、为获得某些节点“希望”的启发信息，提供一个评定侯选扩展节点的方法，以便确定哪个节点最有可能在通向目标的最佳路径上 。 f(n)表示节点n的估价函数值,建立估价函数的一般方法： 试图确定一个处在最佳路径上的节点的概率；提出任意节点与目标集之间的距离量度或差别量度；或者在棋盘式的博弈和难题中根据棋局的某些特点来决定棋局的得分数。这些特点被认为与向目标节点前进一步的希望程度有关。 应用节点“希望”程度（估价函数值）重排OPEN表。,均一代价搜索,是横向搜索的一种推广，不是沿着等长度路径断层进行扩展，而是沿着均一代价路径断层进行扩展。 搜索树中每条连接弧线上的有关代价,表示时间、距离等花费。 若所有连
3、接弧线具有相等代价，则简化为横向搜索算法。,均一代价搜索中的几个记号：,起始节点记为S； 从节点i到它的后继节点j的连接弧线代价记为c(i，j)； 从起始节点S到任一节点i的路径代价记为g(i)。,开始,把S放入OPEN表,OPEN表为空表？,把第一个节点(n)从OPEN表移至CLOSED表,扩展n，把n的后继节点放入OPEN表的末端，提供返回节点n的指针,失败,均一代价搜索算法框图,是,否,把第一个节点(n)从OPEN表移至CLOSED表,n为目标节点吗？,成功,是,否,按g(i)值由小到大的顺序重排OPEN表,均一代价搜索法思路：,1、 从A点开始依次展开得到AB（7）、AC（3）、AD（
4、10）、AE（15）四个新结点，把第一层结点A标记为已展开，并且每个新结点要记录下其距离（括号中的数字）； 2、 把未展开过的AB、AC、AD、AE四个结点中距离最小的一个展开，即展开AC（3）结点，得到ACB（8）、ACD（16）、ACE（13）三个结点，并把结点AC标记为已展开； 3、 再从未展开的所有结点中找出距离最小的一个展开，即展开AB（7）结点，得到ABC（12）、ABD（20）、ABE（19）三个结点，并把结点AB标记为已展开； 4、 再次从未展开的所有结点中找出距离最小的一个展开，即展开ACB（8）结点； 5、 每次展开所有未展开的结点中距离最小的那个结点，直到展开的新结点中出
5、现目标情况（结点含有5个字母）时，即得到了结果。,算法分析：,由上可见，均一代价搜索法并没有象横向搜索一样展开所有结点，只是根据代价最小的原则，每次展开距离A点最近的那个结点，反复下去即可最终得到答案。虽然中途有时也展开了一些并不是答案的结点，但这种展开并不是大规模的，不是全部展开，因而耗时要比横向搜索小得多。,迷宫问题如下，F是入口，B是出口，试采用均一代价搜索算法进行求解。,举例：迷宫问题,0,1,2,3,x,1,2,3,y,F,G,H,E,C,A,D,B,2,2,2,4,1,1,1,1,注：每个节点小括号内的数值表示走到该节点所需付出的代价。,F(0),G(1),H(3),E(2),C(
6、3),A(64),D(5),B(6),1,2,3,4,5,6,7,8,搜索到的路径为黄线所示,登山法和最佳优先搜索,登山法的引入 瞎子在山上某点，想要爬到山顶，怎么办？从立足处用明杖向前一试，觉得高些，就向前一步，如果前面不高，向左一试，高就向左一步，不高再试后面，高就退一步，不高再试右面，高就向右走一步，四面都不高，就原地不动.总之，高了就走一步，就这样一步一步地走，就走上了山顶。 这个向各方向的测试“步”，就是“登山法”的估价函数f(n)。,登山法算法步骤：,设定初始节点n； 如果n是目标，则成功退出； 扩展n，得到其子节点集合； 从该集合中选取f(n)为最小的节点n； 将n设为n，返回第
7、步。,最佳优先搜索算法,是“登山法”的推广，但它是对OPEN表中所有节点的f(n)进行比较，按从小到大的顺序重排OPEN表。 其算法效率类似于纵向搜索算法，但使用了与问题特性相关的估价函数来确定下一步待扩展的节点，因此是一种启发式搜索方法。,开始,把S放入OPEN表，计算估价函数 f (s),OPEN表为空表？,把OPEN表中的第一个节点n放入CLOSED表,n为目标节点吗？,扩展n，计算所有子节点的估价函数值，并提供它们返回节点n的指针。,失败,成功,最佳优先搜索算法框图,是,否,是,否,把子节点送入OPEN表，并对其中的所有节点按估价函数值由小到大重排。,迷宫问题如下，F是入口，B是出口，
8、试采用最佳优先搜索算法进行求解。,举例：迷宫问题,0,1,2,3,x,1,2,3,y,F,G,H,E,C,A,D,B,2,2,2,4,1,1,1,1,解：估价函数f(n)采用每个节点与目标节点在坐标系上的距离来表示。例如，E点与目标节点B之间的空间距离是2+2=4，两个2分别是E与B在x轴及y轴上的距离。,注：每个节点小括号内的数值表示该节点到目标的空间距离，即该点的估价函数值。搜索得到的路径如黄线所示。,F(6),G(5),H(3),E(4),A(2),B(0),1,2,3,4,5,C(3),6,举例：,八数码魔方（8-puzzle problem）,5,7,(3),(5),(5),(4),
9、(3),(3),(2),(4),(3),(4),(1),(0),(2),八数码魔方的最佳优先搜索树,1,2,3,8,4,6,(4),7,5,搜索得到的路径如黄线所示,本题采用了简单的估价函数 f(n)=W(n) 其中：W(n)用来计算对应于节点n的数据库中错放的棋子个数。因此，初始节点棋局 的f(n)值等于4。,第步有三种情况,我们选择其中f(n)最小的: 其它依次类推.最后用了7步得出了结果.,(3),(5),(5),A算法,最佳优先算法有时无法得到最优解，因为它的估价函数f的选取时，忽略了从初始节点到目前节点的代价值。所以，可考虑每个节点n的估价函数f(n)分为两个分量：从起始节点到节点n
10、的代价g(n)以及从节点n到达目标节点代价的估算值h(n)。 f(n)=g(n)+h(n),f(n)节点n的估价函数； g(n)评价函数，从初始节点S到n节点的实际代价； h(n)启发函数，从n到目标节点Sg最佳路径的估计 代价。 这里h(n)体现了搜索的启发信息，因为g(n)是已知的。如果说详细点，g(n)代表了搜索的宽度优先趋势。但是当h(n)g(n) 时，可以省略g(n),而提高效率。,A算法的引入：,g(n)的计算方法：,g(n)就是在搜索树中从S到n这段路径的代价，这一代价可以由从n到S寻找指针时，把所遇到的各段弧线的代价加起来给出(这条路径就是到目前为止用搜索算法找到的从S到n的最
11、小代价路径)。,h(n)的计算方法：,h(n)依赖于有关问题的领域的启发信息。这种信息可能与八数码魔方问题中的函数W(n)所用的那种信息相似。把h(n)叫做启发函数。,举例：,八数码魔方（8-puzzle problem）,5,7,(1+3=4),(1+5=6),(1+5=6),(2+4=6),(2+3=5),(2+3=5),(3+2=5),(3+4=7),(3+3=6),(3+4=7),(4+1=5),(5+0=5),(5+2=7),八数码魔方的A算法搜索树,1,2,3,8,4,6,(0+4=4),7,5,搜索得到的路径如黄线所示,本题采用的估价函数为： f (n)=g (n)+W (n)
12、其中：W (n)用来计算对应于节点n的数据库中错放的棋子个数；g (n)为从起点到n的代价值。因此，第二层的棋局 的f (n)= 1 + 5 = 6。,1,2,3,8,4,5,6,7,g (n),h (n),4.最佳图搜索算法A*（A*算法）,在A算法中，如果满足条件： h(n)h*(n) 则A算法称为A*算法。,对节点n定义f*(n)=g*(n)+h*(n) ,表示从S开始通过节点n的一条最佳路径的代价。 估价函数f 定义为：f(n)=g(n)+h(n) g是g*的估计 ，h是h*的估计 定义1 在图搜索过程中，如果重排OPEN表是依据f(x)=g(x)+h(x)进行的，则称该过程为A算法。 定义2 在A算法中，如果对所有的x存在h(x)h*(x),则称h(x)为h*(x)的下界，它表示某种偏于保守的估计。 定义3 采用h*(x)的下界h(x)为启发函数的A算法，称为A*算法。,A*条件举例,8数码问题 h1(n) = “不在位”的将牌数 h2(n) = 将牌“不在位”的距离和,5,7,(1+4=5),(1+6=7),(1+6=7),(2+5=7),(2+5=7),(2+3=5),(3+2=5),(3+4=7),(4+1=5),(5+0=5),(5+2=7),1,2,3,8,4,6,(0+5=5),7,八数码魔方的A*算法搜索树,
