算法分析与设计线下作业三_第1页
算法分析与设计线下作业三_第2页
算法分析与设计线下作业三_第3页
算法分析与设计线下作业三_第4页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、算法分析与设计学习中心：专 业：学 号：姓 名：作业练习三一、名词解释1、多机调度问题多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。同时约定每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。2、优先队列式分支限界法分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点， 就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中

2、取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时 为止二、简答题1、简述回溯法的基本思想。答：回溯法的基本做法是搜索，在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树， 继续按深度优先策略搜索。2、简要分析分支限界法与回溯法的异同。答：1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某

3、种意义下的最优解。2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。3、常见的分支限界法有哪些？简述之。答：1）队列式（FIFO）分支限界法按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。2）优先队列式分支限界法按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。三、算法编写及算法应用分析题1、分派问题一般陈述如下：给 n个人分派n件工作，把工作j分派给第i个人的代价是 COST（i,j）（非负实数）。要求设计一个回溯算法，在给每个人分派一件不同工作的前提下使 得总代价最小。按照回溯法求解问题的基本步骤，请

4、你完成几个任务：给出解的一般形式，写出解空间。以n=4为例画出表示解空间的状态空间树。并指出树中哪些结点是解结点？提出一个在深度优先搜索状态空间树时用于剪枝的剪枝函数（用文字描述）。2、设计一个回溯算法来求解 k-着色问题：给定无向图 G=,要求使用k种颜色来给图 中每个结点着色（每个结点使用k种颜色之一），使得没有两个相邻的结点颜色相同。给出解向量的形式，并画出当 n=3,k=3时的搜索树。给出剪枝操作。最坏情况下你的算法在搜索树上会生成多少个结点？分析算法的时间复杂度。3、对于下图使用 3、对于下图使用 Dijkstra算法求由顶点a到其他各个顶点的最短路径。并给出求各个顶点对之间的最短路径的算法思想。4、设计一个求解下列最大完全子图问题的回溯算

人人文库> 全部分类> 行业资料 > 信息产业

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论