| 论文摘要：本论文就宽度搜索与剪枝展开讨论。首先以图的深度优先展开始，分析了深度优先的一般方法以及优先规则，然后分别举了四个例子说明了常用的剪枝方法。“骑士游历”是一道典型的权的引入；“钢板分割”也是一道深度搜索的问题，但它是否正确还未被证明；“最短连线”是一个需要综合性剪枝的问题；“平分资源”从理论上不符合深度优先搜索的题目，但还是很好地使用深度搜索解决了。最后一部分是从理论上分析了深度搜索的适用范围。 一提到搜索，就会联想到惊人的时间复杂度与空间复杂度，给我们的印象一直就很一般。但实际上，搜索是一种基本而又有效的方法，当遇到一个没有很好解决方法的时候想到的还是搜索。搜索就是把可能的出现的方法依照其搜索标准一一列出，找出需要的解。基本的搜索方法大致有穷举、贪心、深度搜索、宽度搜索[1]。下面我们讨论的就是深度搜索与剪枝。 一、从图的深度搜索开始 搜索的门类很多，我个人观点是无论怎样的搜索，其根本还是穷举，只是对搜索的先后、取舍不同而已。谈到深度搜索首先要谈谈图的深度搜索。 图的深度优先搜索（depth_first search）类似于树的先序遍历，是树先序遍历的推广[2]。假设初始状态所有的顶点未被访问过，则深度优先可从图中某个顶点v0出发，访问此顶点，然后依次从v0的未被访问过的邻接点出发深度优先遍历图，直至图中所有和v0有路径相通的顶点都被访问过；若此时图中还剩余顶点未访问，则从其中某个顶点出发，重复以上过程，直至所有顶点都被访问过。深度优先的根本思想就是对已访问到的顶点先出发进行访问。 |
- 上一篇：论我国电子商务发展趋势
- 下一篇：基于j2ee的网络开发
查看评论
已有0位网友发表了看法