《人工智能发展历史 (49).pdf》由会员分享，可在线阅读，更多相关《人工智能发展历史 (49).pdf（8页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、有界深度搜索和迭代加深搜索有界深度搜索和迭代加深搜索有界深度搜索和迭代加深搜索有界深度优先搜索过程总体上按深度优先算法方法进行，但对搜索深度需要给出一个深度限制dm当深度达到了dm的时候，如果还没有找到解答，就停止对该分支的搜索，换到另外一个分支进行搜索。有限深度优先搜索的搜索过程如下：(1)把初始节点S0放入OPEN表中，置S0的深度d(S0)=0。(2)如果OPEN表为空，则问题无解，失败并退出。(3)把OPEN表中的首节点取出放入CLOSE表中。并按顺序冠以编号n。(4)考察节点n是否为目标节点。若是，则求得了问题的解，成功并退出。(5)如果节点n的深度d(n)=dm，则转第(2)步。(
2、6)如果节点n不可扩展，则转第(2)步。(7)扩展节点n。将其子节点放入OPEN表的首部，并为其配置指向父节点的指针。然后转第(2)步。策略说明:（1）深度限制dm很重要。当问题有解，且解的路径长度小于或等于dm时，则搜索过程一定能够找到解，但是和深度优先搜索一样这并不能保证最先找到的是最优解。当dm取得太小，解的路径长度大于dm时，则搜索过程中就找不到解，即这时搜索过程甚至是不完备的。（2）深度限制dm不能太大。当dm太大时，搜索过程会产生过多的无用节点，既浪费了计算机资源，又降低了搜索效率。（3）有界深度搜索的主要问题是深度限制值dm的选取。改进方法：（迭代加深搜索）先任意给定一个较小的数
3、作为dm，然后按有界深度算法搜索，若在此深度限制内找到了解，则算法结束；如在此限制内没有找到问题的解，则增大深度限制dm，继续搜索。改进方法：（迭代加深搜索）迭代加深搜索，试图尝试所有可能的深度限制：首先深度为0，然后深度为1，然后为2，等等。如果初始深度为0，则该算法只生成根节点，并检测它。如果根节点不是目标，则深度加1，通过典型的深度优先算法，生成深度为1的树。当深度限制为m 时，树的深度为m。改进方法：（迭代加深搜索）迭代加深搜索看起来会很浪费，因为很多节点都可能扩展多次。然而对于很多问题，这种多次的扩展负担实际上很小，直觉上可以想象，如果一棵树的分支系数很大，几乎所有的节点都在最底层上，则对于上面各层节点扩展多次对整个系统来说影响不是很大。人工智能基础人工智能基础