度为:O(eloge) (1分)Р3.(15分)考虑n=3的批处理作业调度实例:РtjiР机器1Р机器2Р作业1Р1Р10Р作业2Р3Р1Р作业3Р2Р1Р其中tji是作业Ji需要在机器j上处理的时间。对于给定的3个作业,制定一个最佳作业调度方案,使其完成时间和达到最小。Р要求:Р(1)画出该问题的解空间树; (5分)Р(2)写出该问题的剪枝策略(即限界条件),要求只保留第一个最优解;(2分)Р(3)按优先队列式分支限界法搜索解空间树,并用剪枝策略对解空间树中该剪枝的位置打Р´; (5分)Р(4)给出最优解及最优值。(3分)Р参考解答(1)5分Р2Р1Р1Р3Р2Р3Р1Р2Р3Р1Р3Р2Р3РV0Р2Р1Р11Р3Р4Р9Р16Р18Р23Р23Р25Р30Р33Р36Р36Р10Р26※Р Р(2)若当前代价f >= 当前最优解代价bestf,则剪枝。2分Р(3)见(1)中所画的图。5分Р(4)最优解为{3,1,2},最优值为25。3分Р4.【Gray码构造问题】(8分)——提示:此题可采用分治递归算法实现Р问题描述:“格雷码”是一个长度为的序列,满足:Р(a)每个元素都是长度为n比特的串Р(b)序列中无相同元素Р(c)连续的两个元素恰好只有1个比特不同Р例如:n=2时,格雷码为{00,01,11,10}。РGray码是一种编码,这种编码可以避免在读取时,因各数据位时序上的差异造成的误读。格雷码在工程上有广泛应用。但格雷码不便于运算,请你设计一种构造方法,输入长度序列n,输出格雷码(你只要做出一种构造方案即可,格雷码并不唯一)。Р参考解答:此题可用分治法解决。Р当n=1时,输出格雷码{0, 1}Р当n>1时,格雷码的长度为,即共有个码序列。此时,将问题一分为二,即上半部分和下半部分。上半部分最高位设为0,下半部分最高位设为1。剩下n-1位的格雷码的构造采用递归的思路。
全文预览
