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