資源描述：
《分支限界法實驗(最優(yōu)裝載問題)》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。
1、算法分析與設(shè)計實驗報告第八次附加實驗姓名學(xué)號班級時間12.26上午地點工訓(xùn)樓309實驗名稱分支限界法實驗(最優(yōu)裝載問題)實驗?zāi)康?.掌握分支限界法求解問題的思想2.學(xué)會利用隊列求解最優(yōu)裝載問題實驗原理問題描述：有一批共個集裝箱要裝上2艘載重量分別為C1和C2的輪船，其中集裝箱i的重量為Wi，且裝載問題要求確定是否有一個合理的裝載方案可將這個集裝箱裝上這2艘輪船。如果有，找出一種裝載方案。容易證明：如果一個給定裝載問題有解，則采用下面的策略可得到最優(yōu)裝載方案。(1)首先將第一艘輪船盡可能裝滿；(2)將剩余的集裝箱裝上第二艘輪船。實驗步驟(1)在算法的循環(huán)體中，首先檢測當(dāng)前擴展結(jié)點的左
2、兒子結(jié)點是否為可行結(jié)點；(2)如果是則將其加入到活結(jié)點隊列中。然后將其右兒子結(jié)點加入到活結(jié)點隊列屮(右兒子結(jié)點一定是可行結(jié)點)。2個兒子結(jié)點都產(chǎn)生后，當(dāng)前擴展結(jié)點被舍棄；(3)活結(jié)點隊列中的隊首元素被取岀作為當(dāng)前擴展結(jié)點，由于隊列中每一層結(jié)點之后都有一個尾部標(biāo)記-1，故在取隊首元素時，活結(jié)點隊列一定不空；(4)當(dāng)取出的元素是-1時，再判斷當(dāng)前隊列是否為空。如果隊列非空，則將尾部標(biāo)記-1加入活結(jié)點隊列，算法開始處理下一層的活結(jié)點。算法分析與設(shè)計實驗報告第八次附加實驗姓名學(xué)號班級時間12.26上午地點工訓(xùn)樓309實驗名稱分支限界法實驗(最優(yōu)裝載問題)實驗?zāi)康?.掌握分支限界法求解問題的
3、思想2.學(xué)會利用隊列求解最優(yōu)裝載問題實驗原理問題描述：有一批共個集裝箱要裝上2艘載重量分別為C1和C2的輪船，其中集裝箱i的重量為Wi，且裝載問題要求確定是否有一個合理的裝載方案可將這個集裝箱裝上這2艘輪船。如果有，找出一種裝載方案。容易證明：如果一個給定裝載問題有解，則采用下面的策略可得到最優(yōu)裝載方案。(1)首先將第一艘輪船盡可能裝滿；(2)將剩余的集裝箱裝上第二艘輪船。實驗步驟(1)在算法的循環(huán)體中，首先檢測當(dāng)前擴展結(jié)點的左兒子結(jié)點是否為可行結(jié)點；(2)如果是則將其加入到活結(jié)點隊列中。然后將其右兒子結(jié)點加入到活結(jié)點隊列屮(右兒子結(jié)點一定是可行結(jié)點)。2個兒子結(jié)點都產(chǎn)生后，當(dāng)前擴
4、展結(jié)點被舍棄；(3)活結(jié)點隊列中的隊首元素被取岀作為當(dāng)前擴展結(jié)點，由于隊列中每一層結(jié)點之后都有一個尾部標(biāo)記-1，故在取隊首元素時，活結(jié)點隊列一定不空；(4)當(dāng)取出的元素是-1時，再判斷當(dāng)前隊列是否為空。如果隊列非空，則將尾部標(biāo)記-1加入活結(jié)點隊列，算法開始處理下一層的活結(jié)點。關(guān)鍵代碼voidMaxloading(intw[],intc,intn,intbestx[])//K-中w[]為重量數(shù)組1{//c為船的總載重量，n為節(jié)點數(shù)//初始化queueQ;//活節(jié),6:隊列Q.PtiSh(O);//將第一個節(jié)點加入隊列中，并用0表示同層節(jié)點的尾部標(biāo)志inti=l;//當(dāng)
5、前擴展節(jié)點的層數(shù)，此時為intEw=O;//擴展節(jié)點相應(yīng)的載重量intbestw=O;//當(dāng)前最優(yōu)載重量intr=0;//剩余集裝箱的重量for(intj=2;j<=n;j++)//求得最初的剩余載重量r+=w[j];QNode*E=0;//當(dāng)前擴展節(jié)點QNode*bestE;//當(dāng)前最優(yōu)擴展節(jié)點//搜索子集空間樹while(true){//首先檢查左兒子節(jié)點intwt二Ew+w[i];if(wt<=c)//左兒子節(jié)點為可行結(jié)點{if(wt>bcstw)bestw=wt;Enqueue(Q,wt,i,n,bestw,E,bestE,bestx,true);//將左節(jié)點加入隊列}//
6、檢査右兒子節(jié)點，利用上屆函數(shù)if(Ew+r>=bestw)Enqueue(Q,Ew,i,n,bestw,E,bestE,bestx,false);//將右節(jié)點加入隊列E=Q.front();//取出當(dāng)前擴展節(jié)點Q.pop()；if(!E)//到達(dá)同層的最末，此時需耍更新剩余裝箱載重量{if(Q.empty())break;//此時隊列為空Q.push(0);//加入0，表示該層結(jié)束E=Q.front();Q.pop();i++；//進入下一層r_=w[i];//更新剩余集裝箱的值}Ew=E->wcight;//新擴展的節(jié)點對應(yīng)的載重量}//構(gòu)造當(dāng)前最優(yōu)解for(intj:n-l;j
7、>0;j—){bestx[j]=bestE->LChiId;bcstE=bcstE->parcnt;}cout〈〈〃最優(yōu)載重量為：〃〈〈bestw〈〈endl;cout<〈"最優(yōu)載重方式：〃<〈"("；for(inti=l;i
