《用贪心法求解船舶装卸问题(python版).doc》由会员分享，可在线阅读，更多相关《用贪心法求解船舶装卸问题(python版).doc（10页珍藏版）》请在金锄头文库上搜索。
1、一、 课题名称 用贪心法求解船舶装卸问题二、课题内容和要求 设计要求：学习算法设计中贪心法的思想，设计算法编程解决如下现实问题：码头上有n艘船舶同时等待装卸，而码头每次只能装卸一艘船舶。船舶i需要装卸的时间为ti，1in。应如何安排这n艘船舶的装卸次序才能使得总的等待时间达到最小？（总的等待时间是每艘船舶的等待时间的总和） （1）给出求解此问题的贪心算法； （2）说明你所给出的算法的时间复杂性。三、需求分析功能分析: 贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，
2、但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。1. 本程序要求使用的算法为贪心法，那么我们就要对它有一定的认识和了解。因求解问题是总是要做出当前看来是最好的选择，所以我们就要有一个约束条件来对符合要求的解进行甄选。2.寻找最优解：假设有n条船停在码头，每艘船的编号分别是1i(1=i t2 t3 . tn-2 tn-1下面证明上面的猜测：（用反证法）如果让t1 和 t2 的位置互换，即T总 1= n*0 + (n-1)*t2 + (n-2)*t1 + (n-3)*t3 + . + 2*tn-2 + tn-1 + 0*tn此时 T总 1 - T总 =（(n-1)*t2 +
3、(n-2)*t1）- （(n-1)*t1 + (n-2)*t2） = t2 - t1 0所以 T总 1 - T总 0 ,即 T总 1 T总 同理：任意交换ti和tj,总能得到 T总 1 T总 ，所以可以证明猜测成立。所以可以得到筛选函数的算法，即：每次挑选需要卸载时间ti最短的船进行卸载，此时全部船舶的总等待时间最短。四、 概要设计(使用Python语言实现)1.定义船舶类：class Boat(object): def _init_(self,bNum,tNeed,tWait): self.boatNum = bNum self.timeNeed = tNeed self.timeWait
4、= tWait2.等待船舶列表初始化为空： boatWaitList = 3.结束卸货船舶列表初始化为空： boatFinishList = 开始4.算法流程图：初始化船舶信息，其中船舶卸货需要的时间tn为随机产生for i in range(NUM): boatWaitList.append(Boat(i,randint(1,MAXTIME),0)i = 0遍历NUM次boatWaitList，每次找出最小卸货时间,并添加到boatFinishList中。然后删除此船舶信息，并把等待的船舶加上此船的卸货时间for i in range(NUM): temp = NUM + 1 minTime
5、 = MAXTIME for j in range(len(boatWaitList): if boatWaitListj.timeNeed minTime: minTime = boatWaitListj.timeNeed temp = ji NUMYESNO遍历结束卸货列表boatFinishList，求出每艘船的等待时间和所有穿的总等待时间for i in range(NUM): timeSum += boatFinishListi.timeWait结束五、详细设计#-*- coding:gbk -*-from random import randint#给出船舶总数NUM = 20#预
6、定一个最大卸货时间MAXTIME = 20#总等待时间初始值为零timeSum = 0#-初始化船舶信息-#定义Boat类，它有三个成员变量，分别为：船舶编号boatNum，卸货需要的时间timeNeed，#卸货前需要等待的时间timeWaitclass Boat(object): def _init_(self,bNum,tNeed,tWait): self.boatNum = bNum self.timeNeed = tNeed self.timeWait = tWait#定义正在正待的船舶列表boatWait = #定义已经完成卸货的船舶列表boatFinish = print n全部%
7、s艘船需要的时间分别为：%NUM#初始化所有船舶的信息，编号从0到NUM-1，需要时间从1到MAXTIME中间随机，等待时间设为0for i in range(NUM): boatWait.append(Boat(i,randint(1,MAXTIME),0) print 第%s艘船需要%s分钟.%(boatWaiti.boatNum+1,boatWaiti.timeNeed) #-开始卸货-#print n船舶卸货的顺序为：#遍历NUM次等待船舶列表boatWaitfor i in range(NUM): #temp值为记录当前等待船舶列表boatWait中，卸货需要的时间最短的船舶在当前b
8、oatWait中的位置 temp = NUM + 1 #minTime记录当前boatWait列表中，卸货所需的最短时间 minTime = MAXTIME #遍历当前第i次遍历的等待船舶列表boatWait for j in range(len(boatWait): #从0号船舶开始，如果当前船舶卸货所需的时间小于minTime，则把它的时间值赋给minTime #同时记录下此船在当前boatWait中的位置 if boatWaitj.timeNeed = minTime: minTime = boatWaitj.timeNeed temp = j #第i次遍历boatWait后，把卸货时间
9、最短的船舶boatWaittemp加到完成卸货船舶列表boatFinish中 boatFinish.append(boatWaittemp) #在第i次遍历的bootWait列表中删除上面找出的最短时间船舶 del boatWaittemp #对等待船舶列表中的所有船舶，加上上面找出的最短等待时间minTime for k in range(len(boatWait): boatWaitk.timeWait += minTime #-卸货完成-# #遍历卸货完成船舶列表boatFinish，求出船舶总等待时间for i in range(NUM): timeSum += boatFinishi
10、.timeWait print 第%s艘船，它等待了%s分钟.%(boatFinishi.boatNum+1,boatFinishi.timeWait)print n所有船舶的总等待时间为：%s分钟,平均等待时间为%s分钟%(timeSum,timeSum/NUM)六、测试数据及其结果分析对NUM和MAXTIME去不同的值，可以获得不同级别的模拟结果： 1.设置NUM = 20，MAXTIME = 20 2.设置NUM = 20，MAXTIME = 10 3.设置NUM = 10，MAXTIME = 20 4.设置NUM = 10， MAXTIME = 10七、调试过程中的问题最初的想法很简单，既然每次都要找到卸货时间最短的船，那不如在程序开始之前，就把船的序号按照卸货时间的长短进行排序，这样一来只用遍历这个有序列表即可。后来在做的过程中发现这样并不是很简单，因为这样做只是在每次取值的时候变得简便，如果需要计算每艘船的等待时间和所有穿的等待时间之和的时候，还是会很费事，所以后来改用每次遍历等待船舶列表，取出最小值，同时顺带着就把其它船的等待时间加了上去，最后求总等待时间也很简单。八、程序设计总结 这次程序设计很简单，主要在算法的正确性证明上发了些功夫，具体实现起来很简单。加上Python语言强大的列表功能，所以只用了30多行代码即完成。
