2024年5月11日发(作者：怎么设置定时关机)
深度优先搜索和广度优先搜索
一、深度优先搜索和广度优先搜索的深入讨论
(一)深度优先搜索的特点是
无论问题的内容和性质以及求解要求如何不同，它们的程序结构都是相同
的，即都是深度优先算法(一)和深度优先算法(二)中描述的算法结构，不相同
的仅仅是存储结点数据结构和产生规则以及输出要求。
(2)深度优先搜索法有递归以及非递归两种设计方法。一般的，当搜索深度
较小、问题递归方式比较明显时，用递归方法设计好，它可以使得程序结构更
简捷易懂。当搜索深度较大时，当数据量较大时，由于系统堆栈容量的限制，
递归容易产生溢出，用非递归方法设计比较好。
(3)深度优先搜索方法有广义和狭义两种理解。广义的理解是，只要最新产
生的结点(即深度最大的结点)先进行扩展的方法，就称为深度优先搜索方法。
在这种理解情况下，深度优先搜索算法有全部保留和不全部保留产生的结点的
两种情况。而狭义的理解是，仅仅只保留全部产生结点的算法。本书取前一种
广义的理解。不保留全部结点的算法属于一般的回溯算法范畴。保留全部结点
的算法，实际上是在数据库中产生一个结点之间的搜索树，因此也属于图搜索
算法的范畴。
(4)不保留全部结点的深度优先搜索法，由于把扩展望的结点从数据库中弹
出删除，这样，一般在数据库中存储的结点数就是深度值，因此它占用的空间
较少，所以，当搜索树的结点较多，用其他方法易产生内存溢出时，深度优先
搜索不失为一种有效的算法。
(5)从输出结果可看出，深度优先搜索找到的第一个解并不一定是最优解.
如果要求出最优解的话，一种方法将是后面要介绍的动态规划法，另一种
方法是修改原算法：把原输出过程的地方改为记录过程，即记录达到当前目标
的路径和相应的路程值，并与前面已记录的值进行比较，保留其中最优的，等
全部搜索完成后，才把保留的最优解输出。
二、广度优先搜索法的显著特点是：
(1)在产生新的子结点时，深度越小的结点越先得到扩展，即先产生它的子
结点。为使算法便于实现，存放结点的数据库一般用队列的结构。
(2)无论问题性质如何不同，利用广度优先搜索法解题的基本算法是相同的，
但数据库中每一结点内容，产生式规则，根据不同的问题，有不同的内容和结
构，就是同一问题也可以有不同的表示方法。
(3)当结点到跟结点的费用(有的书称为耗散值)和结点的深度成正比时，特
别是当每一结点到根结点的费用等于深度时，用广度优先法得到的解是最优解，
但如果不成正比，则得到的解不一定是最优解。这一类问题要求出最优解，一
种方法是使用后面要介绍的其他方法求解，另外一种方法是改进前面深度(或广
度)优先搜索算法：找到一个目标后，不是立即退出，而是记录下目标结点的路
径和费用，如果有多个目标结点，就加以比较，留下较优的结点。把所有可能
的路径都搜索完后，才输出记录的最优路径。
(4)广度优先搜索算法，一般需要存储产生的所有结点，占的存储空间要比
深度优先大得多，因此程序设计中，必须考虑溢出和节省内存空间得问题。
(5)比较深度优先和广度优先两种搜索法，广度优先搜索法一般无回溯操作，
即入栈和出栈的操作，所以运行速度比深度优先搜索算法法要快些。
总之，一般情况下，深度优先搜索法占内存少但速度较慢，广度优先搜索
算法占内存多但速度较快，在距离和深度成正比的情况下能较快地求出最优解。
因此在选择用哪种算法时，要综合考虑。决定取舍。
二、基本搜索算法比较和搜索算法的优化
搜索算法是利用计算机的高性能来有目的的穷举一个问题的部分或所有的
可能情况，从而求出问题的解的一种方法。搜索过程实际上是根据初始条件和
扩展规则构造一棵解答树并寻找符合目标状态的节点的过程。所有的搜索算法
发布者：admin，转转请注明出处：http://www.yc00.com/xitong/1715384133a2609922.html
评论列表（0条）