《高级算法设计与分析》试卷3答案

PAGEPAGE6《高级算法设计与分析》期末试卷答案（试卷3）姓名：___________________学号：___________________要求：所有题目的解答均写在答题纸上，需写清楚题目序号。每张答题纸都要写上姓名和学号一、选择题（每题3分，共45分）BDAAACDDADDBCBC二、计算、建模题（共40分）设某指派问题的效率矩阵为：其中第i行表示第i个人被指派各个任务的效率，而第j列第j个任务被分配到各个人的效率。试用匈牙利法求最大效率指派，以及在最大效率指派下的总费用。（10分）解：某市下设八个区,下表给出救护车从一个区到另外一个区的车程时间(min)。该市拟建救护中心，要求各区离救护中心的车程时间必须在8min之内（包括8min），问至少建多少个救护中心，建于何处？解：参考答案1:根据上表，如救护中心建在某区，其能覆盖的区域如下：1：1，2，72：1，23：3，4，5，64：3，4，5，65：3，4，5，66：3，4，5，6，87：1，78：6，8设：其中1表示设在某区，0表示不设则建模为：参考答案2:建立图：每个区域为一个顶点，如果区域之间的车程小于等于8min，则两个顶点之间有边，否则无边，建立图如下则原问题建模为求解最小覆盖集问题证明0-1整数规划问题是NPC问题（提示可以用3合取范式的可满足性问题归约为0-1整数规划问题，需要描述一个具体的3合取范式实例转换为具体的0-1整数规划问题实例）。（10分）证:1.0-1整数规划是NP问题:给定某个0-1整数规划的解，很容易在二项式时间内验证这个解是否是0-1整数规划的解，即只要验证每个限制条件即可.2.归约证明简单描述如何用遗传算法对下面优化问题进行求解，要求精度达到小数点后5位，描述要包含个体（染色体）设置，适应度函数定义，选择算子，交叉和变异操作（10分）解：a)需要将区间[-2,2]划分4×105等份，因为218<4×105<219，所以编码的长度应该设置为m=19比特，染色体x如下所示：b)适应度函数f(x)为目标函数c)采用轮盘的方式进行选择，即pd)单点交叉和随机选择一个基因进行变异即可，但可能会产生非法解，对非法解可以直接去除。三、算法设计题（共15分）1.斯坦纳最小树的定义如下：给定无向连通图G=(V,E)和边的权重w:E→R。同时，给出集合R为V的子集，R⊆V，要求在图中寻找一棵子树T=(V′,E′)，其中V′⊆V，E′⊆E，使得R⊆V′，且∑e∈E′w(e)最小。在下面的左图中，顶点（a,b,c,d）的斯坦纳最小树如右图所示。斯坦纳最小树是NP难问题，请设计一个近似算法求解（10分），并计算近似因子（5分）。解：近似算法：1）基于原图G，生成R={a,b,c,d}的一个完全图GR，其中任意一条边的权重为原图G中的最短路径；2）基于GR，生成最小生成树TMST3）将TMST中的边替换成原来的最短路径T’MST4）如果替换成最短路径后生成的图不是树，则需进一步生成最小生成树，结果为近似算法的斯坦纳树TSMT。上面得出的近似算法是2-近似算法。由上面的流程可得：TSMT<T’MST<TMST<GR上的旅行商回路；设T*SMT是最优斯坦纳树，根据此树生成完全图GSMT，则