湖南大学复习算法分析期末答案大题..doc

解答题 机器调度问题。 问题描述：现在有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]}，则按时完成所有任务最少需要几台机器？（提示：使用贪心算法） 画出工作在对应的机器上的分配情况。 3. 单源最短路径的求解。 问题的描述：给定带权有向图（如下图所示）G =(V,E)，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。 解法：现采用Dijkstra算法计算从源顶点1到其它顶点间最短路径。请将此过程填入下表中。 4 4 3 2 1 100 30 maxint 10 - {1} 初始 dist[5] dist[4] dist[3] dist[2] u S 迭代 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]的值是由哪一个子问题的解得到的。 三、算法理解 1、写出多段图最短路经动态规划算法求解下列实例的过程，并求出最优值。 52 5 2 8631 8 6 3 1 74 7 4 各边的代价如下： C(1,2)=3， C(1,3)=5 ，C(1,4)=2 C(2,6)=8 ，C(2,7)=4 ，C(3,5)=5 ，C(3,6)=4， C(4,5)=2，C(4,6)=1 C(5,8)=4， C(6,8)=5 ，C(7,8)=6 解：Cost(4,8)=0 Cost(3,7)= C(7,8)+0=6 ，D[5]=8 Cost(3,6)= C(6，8)+0=5, D[6]=8 Cost(3,5)= C(5，8)+0=4 D[7]=8 Cost(2,4)= min{C(4，6)+ Cost(3,6), C(4，5)+ Cost(3,5)} = min{1+ 5, 2+4}=6 D[4]=6 Cost(2,3)= min{C(3，6)+ Cost(3,6) } = min{4+5}=9 D[3]=5 Cost(2,2)= min{C(2，6)+ Cost(3,6), C(2，7)+ Cost(3,7)} = min{8+5, 4+6}=10 D[2]=7 Cost(1,1)= min{C(1,2)+ Cost(2,2), C(1,3)+ Cost(2,3), C(1,4)+ Cost(2,4)} = min{3+10, 5+9,2+6}= 8 D[1]=4 1→4→6→8 写出maxmin算法对下列实例中找最大数和最小数的过程。 数组 A=(48,12,61,3,5,19,32,7) 解：写出maxmin算法对下列实例中找最大数和最小数的过程。 数组 A=() 1、 48,12,61,3, 5,19,32,7 2、48,12 61,3 5,19 32,7 3、 48～61, 12～3 19～32，5～7 4、 61～32 3～5 5、 61 3 快速排序算法对下列实例排序，算法执行过程中，写出数组A第一次被分割的过程。 A=(65,70,75,80,85,55,50,2) 解：第一个分割元素为65 (1) (2) (3) (4) (5) (6) (7) (8) i p (1) (2) (3) (4) (5) (6) (7) (8) i p 65 70 75 80 85 55 50 2 2 8 65 2