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

文章目录

* 状态空间的盲目搜索 <https://blog.csdn.net/hjc256/article/details/91357937#_1>
* 广度优先算法 <https://blog.csdn.net/hjc256/article/details/91357937#_7>
* 算法描述： <https://blog.csdn.net/hjc256/article/details/91357937#_13>
* 总结 <https://blog.csdn.net/hjc256/article/details/91357937#_23>
* 深度优先算法 <https://blog.csdn.net/hjc256/article/details/91357937#_28>
* 总结 <https://blog.csdn.net/hjc256/article/details/91357937#_32>


<>状态空间的盲目搜索

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

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

<>广度优先算法

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

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

<>算法描述：

* 把初始节点$S_0$放入Open表中
* 如果Open表为空，则问题无解，失败退出
* 把Open表的第一个节点取出，放入Closed表，并记该节点为n
* 考察节点n是否为目标节点，若是，则得到问题的解，成功退出
* 若节点n不可扩展，则转第二步
* 扩展节点n，将其子节点放入Open表的尾部，并未每一个子节点设置指向父节点的指针，然后转到第二步。


<>总结

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

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

<>深度优先算法

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

<>总结

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

• « 上一篇：【物联网】物联网平台开发全栈教程
• » 下一篇：月薪一万在西安能过什么样的生活？