優(yōu)先隊(duì)列最小重量機(jī)器設(shè)計(jì)問(wèn)題.docx

《優(yōu)先隊(duì)列最小重量機(jī)器設(shè)計(jì)問(wèn)題.docx》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、最小重量機(jī)器設(shè)計(jì)問(wèn)題1.問(wèn)題描述：設(shè)某機(jī)器由n個(gè)部件組成，每一種部件都可以從m個(gè)不同的供應(yīng)商處購(gòu)得。設(shè)wij是從供應(yīng)商j處購(gòu)得的部件i的重量，cij是相應(yīng)的價(jià)格。設(shè)計(jì)一個(gè)優(yōu)先隊(duì)列式分支限界法，給出總價(jià)格不超過(guò)d的最小重量機(jī)器設(shè)計(jì)。2.算法設(shè)計(jì)問(wèn)題的解空間為一棵排列樹，采用優(yōu)先隊(duì)列式分支限界法找出所給的最小重量機(jī)器設(shè)計(jì)。開始時(shí)，將排列樹的根節(jié)點(diǎn)置為當(dāng)前擴(kuò)展結(jié)點(diǎn)。在初始擴(kuò)展結(jié)點(diǎn)處還設(shè)有選定部件是哪個(gè)供應(yīng)商提供的，故level=0，source=0，value=0，weight=0。MinLeaf記錄滿足條件的節(jié)點(diǎn)即供應(yīng)商的選擇。while完成對(duì)排列樹內(nèi)部結(jié)點(diǎn)的有序擴(kuò)展。循環(huán)體內(nèi)依次從活結(jié)點(diǎn)優(yōu)先隊(duì)

2、列中取出具有最小重量的結(jié)點(diǎn)，依次為當(dāng)前擴(kuò)展結(jié)點(diǎn)。并且花費(fèi)不超過(guò)d并加以擴(kuò)展，隊(duì)列為空時(shí)則結(jié)束循環(huán)。當(dāng)fartherNode->level等于n時(shí)，此時(shí)擴(kuò)展結(jié)點(diǎn)是葉節(jié)點(diǎn)，判斷是否最優(yōu)，若最優(yōu)則記錄節(jié)點(diǎn)。當(dāng)fartherNode->level