《算法分析与设计》
学习中心： 专 业： 学 号： 姓 名：
作业练习三
一、名词解释 1、多机调度问题
多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。同时约定每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。
2、优先队列式分支限界法
分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。 在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。 此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止
二、简答题
1、简述回溯法的基本思想。
答：回溯法的基本做法是搜索，在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。
2、简要分析分支限界法与回溯法的异同。 答：
1)求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。
2)搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。
3、常见的分支限界法有哪些？简述之。 答：
1)队列式(FIFO)分支限界法
按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。 2)优先队列式分支限界法
按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。
三、算法编写及算法应用分析题
1、分派问题一般陈述如下：给n 个人分派n 件工作，把工作j 分派给第i 个人的代价是COST(i,j)（非负实数）。要求设计一个回溯算法，在给每个人分派一件不同工作的前提下使得总代价最小。按照回溯法求解问题的基本步骤，请你完成几个任务：
① 给出解的一般形式，写出解空间。
② 以 n=4 为例画出表示解空间的状态空间树。并指出树中哪些结点是解结点？ ③ 提出一个在深度优先搜索状态空间树时用于剪枝的剪枝函数（用文字描述）。
2、设计一个回溯算法来求解k-着色问题：给定无向图G=
① 给出解向量的形式，并画出当n=3,k=3 时的搜索树。 ② 给出剪枝操作。
③ 最坏情况下你的算法在搜索树上会生成多少个结点？分析算法的时间复杂度。
3、对于下图使用Dijkstra算法求由顶点a到其他各个顶点的最短路径。并给出求各个顶点对之间的最短路径的算法思想。
be2g2ad21cf2121433h
4、设计一个求解下列最大完全子图问题的回溯算法。只要求叙述清楚算法的主要要素，并 指出算法的最坏时间复杂度。
最大完全子图问题：给定无向图G，求出G中顶点个数最多的完全子图。