对应课程:点击查看
起止时间:2019-09-20到2019-10-21
更新状态:已完结
作业6 分支限界法 分支限界法作业
1、 简述分支限界支法的搜索策略
评分规则: 分支限界法首先确定一个合理的限界函数，并根据限界函数确定目标函数的界[down, up] 。然后，按照广度优先策略遍历问题的解空间树，在分支结点上，依次搜索该结点的所有孩子结点，分别估算这些孩子结点的目标函数的可能取值，如果某孩子结点的目标函数可能取得的值超出目标函数的界，则将其丢弃，因为从这个结点生成的解不会比目前已经得到的解更好；否则，将其加入待处理结点表（以下简称表PT）中。依次从表PT中选取使目标函数的值取得极值的结点成为当前扩展结点，重复上述过程，直到找到最优解。
2、 假设有4个物品，其重量分别为(4, 7, 5, 3)，价值分别为(40, 42, 25, 12)，背包容量W=10。
评分规则: 
3、 •在下图所给的有向图G中，每一边都有一个非负边权。要求图G的从源顶点s到目标顶点t之间的最短路径。
评分规则: 
下图是用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树。其中，每一个结点旁边的数字表示该结点所对应的当前路长。
4、 
给定一个图G,使用优先队列式分支限界法求解这个图的最大团。
评分规则: 
作业1 算法概述 算法概述作业
小提示:本节包含奇怪的同名章节内容
1、 请解释大O表示法 、大W 表示法、q表示法的区别。
评分规则: 
2、 某厂商A新研制的处理器运行速度为B公司同类产品的81倍。对于计算复杂性分别为
的各算法，若用B公司的计算机在1小时内能解输入规模为的问题，那么用A公司的计算机在同样的时间内分别能解输入规模为多大的问题？
评分规则: 1求解正确无误
3、 
评分规则: 
作业2 分治与递归 分治与递归作业题
小提示:本节包含奇怪的同名章节内容
1、 请分析对比不同排序算法的时间复杂度（至少对比分5种以上的排序算法）
评分规则: 1、内容阐述正确2、逻辑结构清晰
2、 一个递归算法的递归公式如下： 
请分析该算法的时间复杂度。
评分规则: 求解过程清晰、无误
3、 假设数组A包含有n个不同正整数（已经按升序排列），给定正整数L和U（L 1、可执行正确的代码2、代码逻辑结构清晰，执行效率高，输出结果正确
4、 假设K是含有m个不同数的数组，请设计算法找出该数组的中位数。（1）给出描述算法的伪代码。（2）分析并给出该算法的时间复杂性上界O。
评分规则: 1、可执行正确的代码2、代码逻辑结构清晰，执行效率高，输出结果正确
5、 现有n枚外观相同的硬币和一架天平，已知硬币中有一枚重量较轻的硬币是假币，要求设计一个高效的算法来检测出这枚假币。请写出分治法求解该问题的详细步骤，并分析其时间复杂性。
评分规则: 
1、内容阐述正确2、逻辑结构清晰
6、 一个递归算法的递归公式如下： 请分析该算法的时间复杂度。
评分规则: 
为了方便下次阅读，建议在浏览器添加书签收藏本网页
添加书签方法：
1.电脑按键盘的Ctrl键+D键即可收藏本网页
2.手机浏览器可以添加书签收藏本网页
获取更多MOOC答案，欢迎在浏览器访问我们的网站：http://mooc.mengmianren.com
注：请切换至英文输入法输入域名，如果没有成功进入网站，请输入完整域名：http://mooc.mengmianren.com/
我们的公众号
打开手机微信，扫一扫下方二维码，关注微信公众号：萌面人APP
本公众号可查看各种网课答案，还可免费查看大学教材答案
点击这里，可查看公众号功能介绍
一键领取淘宝，天猫，京东，拼多多无门槛优惠券，让您购物省省省，点击这里，了解详情