用貪心法求解船舶裝卸問題(python版)

1、1、 課題名稱 用貪心法求解船舶裝卸問題二、課題內(nèi)容和要求 設(shè)計(jì)要求：學(xué)習(xí)算法設(shè)計(jì)中貪心法的思想，設(shè)計(jì)算法編程解決如下現(xiàn)實(shí)問題：碼頭上有n艘船舶同時(shí)等待裝卸，而碼頭每次只能裝卸一艘船舶。船舶i需要裝卸的時(shí)間為ti，1in。應(yīng)如何安排這n艘船舶的裝卸次序才能使得總的等待時(shí)間達(dá)到最小？（總的等待時(shí)間是每艘船舶的等待時(shí)間的總和） （1）給出求解此問題的貪心算法； （2）說明你所給出的算法的時(shí)間復(fù)雜性。三、需求分析功能分析: 貪心算法是指，在對(duì)問題求解時(shí)，總是做出在當(dāng)前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解。貪心算法不是對(duì)所有問題都能得到整體最優(yōu)解，

2、但對(duì)范圍相當(dāng)廣泛的許多問題他能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解。1. 本程序要求使用的算法為貪心法，那么我們就要對(duì)它有一定的認(rèn)識(shí)和了解。因求解問題是總是要做出當(dāng)前看來是最好的選擇，所以我們就要有一個(gè)約束條件來對(duì)符合要求的解進(jìn)行甄選。2.尋找最優(yōu)解：假設(shè)有n條船停在碼頭，每艘船的編號(hào)分別是1i(1=i t2 t3 . tn-2 tn-1下面證明上面的猜測(cè)：（用反證法）如果讓t1 和 t2 的位置互換，即T總 1= n*0 + (n-1)*t2 + (n-2)*t1 + (n-3)*t3 + . + 2*tn-2 + tn-1 + 0*tn此時(shí) 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總 ，所以可以證明猜測(cè)成立。所以可以得到篩選函數(shù)的算法，即：每次挑選需要卸載時(shí)間ti最短的船進(jìn)行卸載，此時(shí)全部船舶的總等待時(shí)間最短。4、 概要設(shè)計(jì)(使用Python語言實(shí)現(xiàn))1.定義船舶類：class Boat(object): def _init_(self,bNum,tNeed,tWait): self.boatNum = bNum self.timeNeed = tNeed self.timeWait

4、= tWait2.等待船舶列表初始化為空： boatWaitList = 3.結(jié)束卸貨船舶列表初始化為空： boatFinishList = 開始4.算法流程圖：初始化船舶信息，其中船舶卸貨需要的時(shí)間tn為隨機(jī)產(chǎn)生for i in range(NUM): boatWaitList.append(Boat(i,randint(1,MAXTIME),0)i = 0遍歷NUM次boatWaitList，每次找出最小卸貨時(shí)間,并添加到boatFinishList中。然后刪除此船舶信息，并把等待的船舶加上此船的卸貨時(shí)間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遍歷結(jié)束卸貨列表boatFinishList，求出每艘船的等待時(shí)間和所有穿的總等待時(shí)間for i in range(NUM): timeSum += boatFinishListi.timeWait結(jié)束五、詳細(xì)設(shè)計(jì)#-*- coding:gbk -*-from random import randint#給出船舶總數(shù)NUM = 20#預(yù)

6、定一個(gè)最大卸貨時(shí)間MAXTIME = 20#總等待時(shí)間初始值為零timeSum = 0#-初始化船舶信息-#定義Boat類，它有三個(gè)成員變量，分別為：船舶編號(hào)boatNum，卸貨需要的時(shí)間timeNeed，#卸貨前需要等待的時(shí)間timeWaitclass Boat(object): def _init_(self,bNum,tNeed,tWait): self.boatNum = bNum self.timeNeed = tNeed self.timeWait = tWait#定義正在正待的船舶列表boatWait = #定義已經(jīng)完成卸貨的船舶列表boatFinish = print n全部%

7、s艘船需要的時(shí)間分別為：%NUM#初始化所有船舶的信息，編號(hào)從0到NUM-1，需要時(shí)間從1到MAXTIME中間隨機(jī)，等待時(shí)間設(shè)為0for i in range(NUM): boatWait.append(Boat(i,randint(1,MAXTIME),0) print 第%s艘船需要%s分鐘.%(boatWaiti.boatNum+1,boatWaiti.timeNeed) #-開始卸貨-#print n船舶卸貨的順序?yàn)椋?遍歷NUM次等待船舶列表boatWaitfor i in range(NUM): #temp值為記錄當(dāng)前等待船舶列表boatWait中，卸貨需要的時(shí)間最短的船舶在當(dāng)前b

8、oatWait中的位置 temp = NUM + 1 #minTime記錄當(dāng)前boatWait列表中，卸貨所需的最短時(shí)間 minTime = MAXTIME #遍歷當(dāng)前第i次遍歷的等待船舶列表boatWait for j in range(len(boatWait): #從0號(hào)船舶開始，如果當(dāng)前船舶卸貨所需的時(shí)間小于minTime，則把它的時(shí)間值賦給minTime #同時(shí)記錄下此船在當(dāng)前boatWait中的位置 if boatWaitj.timeNeed = minTime: minTime = boatWaitj.timeNeed temp = j #第i次遍歷boatWait后，把卸貨時(shí)間

9、最短的船舶boatWaittemp加到完成卸貨船舶列表boatFinish中 boatFinish.append(boatWaittemp) #在第i次遍歷的bootWait列表中刪除上面找出的最短時(shí)間船舶 del boatWaittemp #對(duì)等待船舶列表中的所有船舶，加上上面找出的最短等待時(shí)間minTime for k in range(len(boatWait): boatWaitk.timeWait += minTime #-卸貨完成-# #遍歷卸貨完成船舶列表boatFinish，求出船舶總等待時(shí)間for i in range(NUM): timeSum += boatFinishi

10、.timeWait print 第%s艘船，它等待了%s分鐘.%(boatFinishi.boatNum+1,boatFinishi.timeWait)print n所有船舶的總等待時(shí)間為：%s分鐘,平均等待時(shí)間為%s分鐘%(timeSum,timeSum/NUM)六、測(cè)試數(shù)據(jù)及其結(jié)果分析對(duì)NUM和MAXTIME去不同的值，可以獲得不同級(jí)別的模擬結(jié)果： 1.設(shè)置NUM = 20，MAXTIME = 20 2.設(shè)置NUM = 20，MAXTIME = 10 3.設(shè)置NUM = 10，MAXTIME = 20 4.設(shè)置NUM = 10， MAXTIME = 10七、調(diào)試過程中的問題最初的想法很簡(jiǎn)單，既然每次都要找到卸貨時(shí)間最短的船，那不如在程序開始之前，就把船的序號(hào)按照卸貨時(shí)間的長(zhǎng)短進(jìn)行排序，這樣一來只用遍歷這個(gè)有序列表即可。后來在做的過程中發(fā)現(xiàn)這樣并不是很簡(jiǎn)單，因?yàn)檫@樣做只是在每次取值的時(shí)候變得簡(jiǎn)便，如果需要計(jì)算每艘船