用贪心法求解船舶装卸问题(python版)

一、课题名称用贪心法求解船舶装卸问题二、课题内容和要求设计要求：学习算法设计中贪心法的思想，设计算法编程解决如下现实问题：码头上有n艘船舶同时等待装卸，而码头每次只能装卸一艘船舶。船舶i需要装卸的时间为ti，1≤i≤n。应如何安排这n艘船舶的装卸次序才能使得总的等待时间达到最小？（总的等待时间是每艘船舶的等待时间的总和）（1）给出求解此问题的贪心算法；（2）说明你所给出的算法的时间复杂性。三、需求分析功能分析:贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。1.本程序要求使用的算法为贪心法，那么我们就要对它有一定的认识和了解。因求解问题是总是要做出当前看来是最好的选择，所以我们就要有一个约束条件来对符合要求的解进行甄选。2.寻找最优解：假设有n条船停在码头，每艘船的编号分别是1~i(1=i=n),装卸时间都是t[i],因为每次只能装卸1艘船，那么在装卸的时候剩余船的等待时间就是t[i]。每艘船的等待时间就是如下的关系式：Boat1：0Boat2：0+t[1]Boat3：0+t[1]+t[2]Boat4：0+t[1]+t[2]+t[3]Boat5：0+t[1]+t[2]+t[3]+t[4]Boat6：0+t[1]+t[2]+t[3]+t[4]+t[5]Boat7：0+t[1]+t[2]+t[3]+t[4]+t[5]+t[6]…………Boatn:0+t[1]+t[2]+t[3]+t[4]+t[5]+t[6]+......+t[n-1]所以，所有船舶的总等待时间:T总=n*0+(n-1)*t[1]+(n-2)*t[2]+(n-3)*t[3]+...+2*t[n-2]+t[n-1]+0*t[n]上式的含义是：当第一艘船在卸货的时候，剩下的n-1艘船都要等待时长t[1],第二艘船在卸货的时候，剩下的n-2艘船都要继续等待时长t[2]，...,剩下的情况以此类推。此时我们可以得出，让需要被等待时间最多的t[1]如果越短，所有船舶等待的总时间就会越短，所以猜测，t[1]t[2]t[3]...t[n-2]t[n-1]下面证明上面的猜测：（用反证法）如果让t[1]和t[2]的位置互换，即T总1=n*0+(n-1)*t[2]+(n-2)*t[1]+(n-3)*t[3]+...+2*t[n-2]+t[n-1]+0*t[n]此时T总1-T总=（(n-1)*t[2]+(n-2)*t[1]）-（(n-1)*t[1]+(n-2)*t[2]）=t[2]-t[1]0所以T总1-T总0,即T总1T总同理：任意交换t[i]和t[j],总能得到T总1T总，所以可以证明猜测成立。所以可以得到筛选函数的算法，即：每次挑选需要卸载时间t[i]最短的船进行卸载，此时全部船舶的总等待时间最短。四、概要设计(使用Python语言实现)1.定义船舶类：classBoat(object):def__init__(self,bNum,tNeed,tWait):self.boatNum=bNumself.timeNeed=tNeedself.timeWait=tWait2.等待船舶列表初始化为空：boatWaitList=[]3.结束卸货船舶列表初始化为空：boatFinishList=[]4.算法流程图：开始初始化船舶信息，其中船舶卸货需要的时间tn为随机产生foriinrange(NUM):boatWaitList.append(Boat(i,randint(1,MAXTIME),0))i=0遍历NUM次boatWaitList，每次找出最小卸货时间,并添加到boatFinishList中。然后删除此船舶信息，并把等待的船舶加上此船的卸货时间foriinrange(NUM):temp=NUM+1minTime=MAXTIMEforjinrange(len(boatWaitList)):ifboatWaitList[j].timeNeedminTime:minTime=boatWaitList[j].timeNeedtemp=jiNUMYESNO遍历结束卸货列表boatFinishList，求出每艘船的等待时间和所有穿的总等待时间foriinrange(NUM):timeSum+=boatFinishList[i].timeWait结束五、详细设计#-*-coding:gbk-*-fromrandomimportrandint#给出船舶总数NUM=20#预定一个最大卸货时间MAXTIME=20#总等待时间初始值为零timeSum=0#----------------------------------初始化船舶信息----------------------------------##定义Boat类，它有三个成员变量，分别为：船舶编号boatNum，卸货需要的时间timeNeed，#卸货前需要等待的时间timeWaitclassBoat(object):def__init__(self,bNum,tNeed,tWait):self.boatNum=bNumself.timeNeed=tNeedself.timeWait=tWait#定义正在正待的船舶列表boatWait=[]#定义已经完成卸货的船舶列表boatFinish=[]print\n全部%s艘船需要的时间分别为：%NUM#初始化所有船舶的信息，编号从0到NUM-1，需要时间从1到MAXTIME中间随机，等待时间设为0foriinrange(NUM):boatWait.append(Boat(i,randint(1,MAXTIME),0))print第%s艘船需要%s分钟.%(boatWait[i].boatNum+1,boatWait[i].timeNeed)#-------------------------------------开始卸货-------------------------------------#print\n船舶卸货的顺序为：#遍历NUM次等待船舶列表boatWaitforiinrange(NUM):#temp值为记录当前等待船舶列表boatWait中，卸货需要的时间最短的船舶在当前boatWait中的位置temp=NUM+1#minTime记录当前boatWait列表中，卸货所需的最短时间minTime=MAXTIME#遍历当前第i次遍历的等待船舶列表boatWaitforjinrange(len(boatWait)):#从0号船舶开始，如果当前船舶卸货所需的时间小于minTime，则把它的时间值赋给minTime#同时记录下此船在当前boatWait中的位置ifboatWait[j].timeNeed=minTime:minTime=boatWait[j].timeNeedtemp=j#第i次遍历boatWait后，把卸货时间最短的船舶boatWait[temp]加到完成卸货船舶列表boatFinish中boatFinish.append(boatWait[temp])#在第i次遍历的bootWait列表中删除上面找出的最短时间船舶delboatWait[temp]#对等待船舶列表中的所有船舶，加上上面找出的最短等待时间minTimeforkinrange(len(boatWait)):boatWait[k].timeWait+=minTime#-------------------------------------卸货完成-------------------------------------##遍历卸货完成船舶列表boatFinish，求出船舶总等待时间foriinrange(NUM):timeSum+=boatFinish[i].timeWaitprint第%s艘船，它等待了%s分钟.%(boatFinish[i].boatNum+1,boatFinish[i].timeWait)print\n所有船舶的总等待时间为：%s分钟,平均等待时间为%s分钟%(timeSum,timeSum/NUM)六、测试数据及其结果分析对NUM和MAXTIME去不同的值，可以获得不同级别的模拟结果：1.设置NUM=20，MAXTIME=202.设置NUM=20，MAXTIME=103.设置NUM=10，MAXTIME=204.设置NUM=10，MAXTIME=10七、调试过程中的问题最初的想法很简单，既然每次都要找到卸货时间最短的船，那不如在程序开始之前，就把船的序号按照卸货时间的长短进行排序，这样一来只用遍历这个有序列表即可。后来在做的过程中发现这样并不是很简单，因为这样做只是在每次取值的时候变得简便，如果需要计算每艘船的等待时间和所有穿的等待时间之和的时候，还是会很费事，所以后来改用每次遍历等待船舶列表，取出最小值，同时顺带着就把其它船的等待时间加了上去，最后求总等待时间也很简单。八、程序设计总结这次程序设计很简单，主要在算法的正确性证明上发了些功夫，具体实现起来很简单。加上Python语言强大的列表功能，所以只用了30多行代码即完成。