- 1、本文档共26页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
《算法分析与设计》
解答题
机器调度问题。
问题描述:现在有n件任务和无限多台的机器,任务可以在机器上得到处理。每件任务的开始时间为si,完成时间为fi,sifi 。[si,fi]为处理任务i的时间范围。两个任务i,j重叠指两个任务的时间范围区间有重叠,而并非指i,j的起点或终点重合。例如:区间[1,4]与区间[2,4]重叠,而与[4,7]不重叠。一个可行的任务分配是指在分配中没有两件重叠的任务分配给同一台机器。因此,在可行的分配中每台机器在任何时刻最多只处理一个任务。最优分配是指使用的机器最少的可行分配方案。
问题实例:若任务占用的时间范围是{[1,4],[2,5],[4,5],[2,6],[4,7]},则按时完成所有任务最少需要几台机器?(提示:使用贪心算法)
画出工作在对应的机器上的分配情况。
2. 已知非齐次递归方程: ,其中,b、c是常数,g(n)是n的某一个函数。则f(n)的非递归表达式为:。
现有Hanoi塔问题的递归方程为: ,求h(n)的非递归表达式。
解:利用给出的关系式,此时有:b=2, c=1, g(n)=1, 从n递推到1,有:
3. 单源最短路径的求解。
问题的描述:给定带权有向图(如下图所示)G =(V,E),其中每条边的权是非负实数。另外,还给定V中的一个顶点,称为源。现在要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。
解法:现采用Dijkstra算法计算从源顶点1到其它顶点间最短路径。请将此过程填入下表中。
4. 请写出用回溯法解装载问题的函数。
装载问题:有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船,其中集装箱i的重量为wi,且。装载问题要求确定是否有一个合理的装载方案可将这n个集装箱装上这2艘轮船。如果有,找出一种装载方案。
解:void backtrack (int i)
{// 有哪些信誉好的足球投注网站第i层结点
if (i n) // 到达叶结点
更新最优解bestx,bestw;return;
r -= w[i];
if (cw + w[i] = c) {// 有哪些信誉好的足球投注网站左子树
x[i] = 1;
cw += w[i];
backtrack(i + 1);
cw -= w[i]; }
if (cw + r bestw) {
x[i] = 0; // 有哪些信誉好的足球投注网站右子树
backtrack(i + 1); }
r += w[i];
}
5. 用分支限界法解装载问题时,对算法进行了一些改进,下面的程序段给出了改进部分;试说明斜线部分完成什么功能,以及这样做的原因,即采用这样的方式,算法在执行上有什么不同。
解答:斜线标识的部分完成的功能为:提前更新bestw值;
这样做可以尽早的进行对右子树的剪枝。具体为:算法Maxloading初始时将bestw设置为0,直到有哪些信誉好的足球投注网站到第一个叶结点时才更新bestw。因此在算法有哪些信誉好的足球投注网站到第一个叶子结点之前,总有bestw=0,r0 故Ew+rbestw总是成立。也就是说,此时右子树测试不起作用。
为了使上述右子树测试尽早生效,应提早更新bestw。又知算法最终找到的最优值是所求问题的子集树中所有可行结点相应重量的最大值。而结点所相应得重量仅在有哪些信誉好的足球投注网站进入左子树是增加,因此,可以在算法每一次进入左子树时更新bestw的值。
7. 最长公共子序列问题:给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn},找出X和Y的最长公共子序列。
由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用c[i][j]记录序列Xi和Yj的最长公共子序列的长度。其中, Xi={x1,x2,…,xi};Yj={y1,y2,…,yj}。当i=0或j=0时,空序列是Xi和Yj的最长公共子序列。故此时C[i][j]=0。其它情况下,由最优子结构性质可建立递归关系如下:
在程序中,b[i][j]记录C[i][j]的值是由哪一个子问题的解得到的。
请填写程序中的空格,以使函数LCSLength完成计算最优值的功能。
函数LCS实现根据b的内容打印出Xi和Yj的最长公共子序列。请填写程序中的空格,以使函数LCS完成构造最长公共子序列的功能(请将b[i][j]的取值与(1)中您填写的取值对应,否则视为错误)。
8.对下面的递归算法,写出调用f(4)的执行结果。
二、复杂性分析
MERGE
文档评论(0)