人工智能--状态空间的盲目搜索，

文章目录

• 状态空间的盲目搜索
• 广度优先算法
• 算法描述：
• 总结
• 深度优先算法
• 总结

状态空间的盲目搜索

根据状态空间所采用的数据结构的不同，可分为图搜索算法和树搜索算法。由于图搜索算法且一般问题都可用树搜索算法解决，于是主要讨论树搜索算法，包括一般和代价树。

一般树的盲目搜索主要包括深度优先和广度优先两种搜索算法。

广度优先算法

也称为宽度优先算法，是一种先生成的节点先扩展的策略。

算法精髓：从初始节点$S_0$开始逐层向下扩展，在第n层还没有完全搜索完之前不会进入第n+1层的搜索。Open表中的节点总是按进入的先后排序，先进入的节点排在前面。

算法描述：

总结

广度优先搜索是一种完备策略，即只要问题有解，算法就一定可以找到解。并且，广度优先算法找到的解还一定是路径最短的解。

缺点是盲目性较大，特别是当目标节点与初始节点距离较远时，将产生许多无用的节点，效率较低。

深度优先算法

算法步骤基本与广度优先算法相同，只是Open表中的排序不同，在深度优先算法中，后进入Open表的节点总是排在最前面。即后生成的节点先扩展。

总结

深度优先算法是一种非完备策略，即某些本身有解的问题，该算法可能找不到最优解，甚至找不到解。常见做法是增加一个深度限制，当达到一定深度时，停止深度搜索，转向宽度搜索。这种算法也叫有界深度优先算法。