最小重量機(jī)器設(shè)計(jì).doc

《最小重量機(jī)器設(shè)計(jì).doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、算法分析與設(shè)計(jì)實(shí)驗(yàn)報(bào)告——最小重量機(jī)器設(shè)計(jì)回溯法解決一、實(shí)驗(yàn)?zāi)康慕⑺惴◤?fù)雜度的理論分析與實(shí)驗(yàn)分析的聯(lián)系，深刻體會(huì)算法復(fù)雜度作為算法的好壞評(píng)價(jià)指標(biāo)的本質(zhì)含義。二、實(shí)驗(yàn)要求1、用c++語(yǔ)言實(shí)現(xiàn)最小重量機(jī)器設(shè)計(jì)的回溯算法。2、分析算法的計(jì)算復(fù)雜性三、實(shí)驗(yàn)原理回溯法的基本思想：首先，應(yīng)該明確的確定問(wèn)題的解空間。確定了解空間的組織結(jié)構(gòu)后，觳觫發(fā)從開(kāi)始節(jié)點(diǎn)（根節(jié)點(diǎn)）出發(fā)，以深度優(yōu)先方式搜索整個(gè)解空間。這個(gè)開(kāi)始結(jié)點(diǎn)成為活結(jié)點(diǎn)，同時(shí)也成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)。在當(dāng)前的擴(kuò)展結(jié)點(diǎn)處，向縱深方向搜索移至一個(gè)新的結(jié)點(diǎn)。這個(gè)新結(jié)點(diǎn)成為新的活結(jié)點(diǎn)，并成為新的擴(kuò)展結(jié)點(diǎn)。如果在當(dāng)前的擴(kuò)

2、展結(jié)點(diǎn)處不能再向縱深方向移動(dòng)，則當(dāng)前擴(kuò)展結(jié)點(diǎn)成為死結(jié)點(diǎn)。此時(shí)，應(yīng)往回移動(dòng)（回溯）至最近的活結(jié)點(diǎn)，并使這個(gè)活結(jié)點(diǎn)成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)。回溯以這種工作方式遞歸的在解空間中搜索，直至找到所要求的解或解空間中已無(wú)活結(jié)點(diǎn)為止。四、實(shí)驗(yàn)過(guò)程(步驟)解題思路：由于題目已經(jīng)給出總價(jià)格的上限，因此算法通過(guò)使用回溯來(lái)選擇合適的機(jī)器使得在總價(jià)格不超過(guò)d時(shí)得到的機(jī)器重量最小。首先初始化當(dāng)前價(jià)格cp=0,當(dāng)前重量cw=0,此外，還要設(shè)置一個(gè)變量sum表示選擇機(jī)器的總重量，初始化其為每個(gè)部件從1號(hào)供應(yīng)商購(gòu)買(mǎi)的重量。在循環(huán)選擇i號(hào)機(jī)器時(shí)，判斷從j號(hào)供應(yīng)商購(gòu)買(mǎi)機(jī)器后的價(jià)格是否大于總價(jià)

3、格，如果不大于則選擇，否則不選，繼續(xù)選擇下一供應(yīng)商進(jìn)行判斷。在得到一個(gè)合適的供應(yīng)商后，繼續(xù)選擇下一機(jī)器的供應(yīng)商，從第一個(gè)選到最后一個(gè)供應(yīng)商。當(dāng)所有機(jī)器選擇結(jié)束后，判斷得到的總重量是否比之前的sum小，如果小就賦給sum，然后從這一步開(kāi)始，回溯到上一機(jī)器，選擇下一合適供應(yīng)商，繼續(xù)搜索可行解，直到將整個(gè)排列樹(shù)搜索完畢。這樣，最終得到的sum即為最優(yōu)解。數(shù)據(jù)說(shuō)明：N：零件數(shù)量m：不同的零件商W[][]:是從供應(yīng)商j處購(gòu)得的部件i的重量c[][]：相應(yīng)的價(jià)值算法設(shè)計(jì)：a.部件有n個(gè)，供應(yīng)商有m個(gè)，分別用w[i][j]和c[i][j]存儲(chǔ)從供應(yīng)商j處購(gòu)得的部件

4、i的重量和相應(yīng)價(jià)格，d為總價(jià)格的上限。b.用遞歸函數(shù)backtrack(i)來(lái)實(shí)現(xiàn)回溯法搜索排列樹(shù)（形式參數(shù)i表示遞歸深度）。①若cp>d，則為不可行解，剪去相應(yīng)子樹(shù)，返回到i-1層繼續(xù)執(zhí)行。②若cw>=sum，則不是最優(yōu)解，剪去相應(yīng)子樹(shù)，返回到i-1層繼續(xù)執(zhí)行。③若i>n，則算法搜索到一個(gè)葉結(jié)點(diǎn)，用sum對(duì)最優(yōu)解進(jìn)行記錄，返回到i-1層繼續(xù)執(zhí)行；④用for循環(huán)對(duì)部件i從m個(gè)不同的供應(yīng)商購(gòu)得的情況進(jìn)行選擇(1≤j≤m）。c.主函數(shù)調(diào)用一次Knapsack(1)即可完成整個(gè)回溯搜索過(guò)程，最終得到的sum即為所求最小總重量。五、運(yùn)行結(jié)果六、實(shí)驗(yàn)分析與討論

5、計(jì)算復(fù)雜性性分析：七、實(shí)驗(yàn)心得通過(guò)這次試驗(yàn)我明白了回溯法的思想，回溯法借助想象出來(lái)的樹(shù)的結(jié)構(gòu)，把問(wèn)題簡(jiǎn)單化，使得解問(wèn)題更方便。通過(guò)剪枝函數(shù)和約束函數(shù)對(duì)于求問(wèn)題的解有很大的幫助，但要把一些限制條件把剪枝函數(shù)抽象化。