



下載本文檔
版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
1、1 按分治策略求解棋盤覆蓋問題時,對于如圖所示的24×24的特殊棋盤,共需要多少個L型骨牌;并在棋盤上填寫L型骨牌的覆蓋情況。物品ABCDEFG重量35305060401025價值104030503540302 假設(shè)有7個物品,給出重量和價值。若這些物品均不能被分割,且背包容量M140,使用回溯方法求解此0-1背包問題。請畫出狀態(tài)空間搜索樹。3 假設(shè)有7個物品,它們的重量和價值如下表所示。若這些物品均可以被分割,且背包容量M140,使用貪心算法求解此背包問題。請寫出求解策略和求解過程。W(35,30,50,60,40,10,25)p(10,40,30,50,35,40,30)4 在給
2、出的電路板中,陰影部分是已作了封鎖標(biāo)記的方格,請按照隊(duì)列式分支限界法在圖中確定a到b的最短布線方案,要求布線時只能沿直線或直角進(jìn)行,在圖中標(biāo)出求得最優(yōu)解時各方格情況。5 畫出字符表的哈夫曼編碼對應(yīng)的二叉樹。6 已知,k=1,2,3,4,5,6,r1=5,r2=10,r3=3,r4=8,r5=5,r6=20,r7=6,求矩陣鏈積A1×A2×A3×A4×A5×A6的最佳求積順序。7 給出城市網(wǎng)絡(luò)圖,售貨員要從城市1出發(fā),經(jīng)過所有城市回到城市1,畫出該問題的解空間樹,描述出用優(yōu)先隊(duì)列式分支限界法求解時的搜索情況。表示出優(yōu)先隊(duì)列、當(dāng)前擴(kuò)展結(jié)點(diǎn)等的變化情
3、況。8 依據(jù)優(yōu)先隊(duì)列式分支限界法,求從s點(diǎn)到t點(diǎn)的單源最短路徑,畫出求得最優(yōu)解的解空間樹。一、 假設(shè)有7個物品,它們的重量和價值如下表所示。若這些物品均不能被分割,且背包容量M150,使用回溯方法求解此背包問題。請寫出狀態(tài)空間搜索樹(20分)。 物品ABCDEFG重量35306050401025價值10403050354030答:按照單位效益從大到小依次排列這7個物品為:FBGDECA。將它們的序號分別記為17。則可生產(chǎn)如下的狀態(tài)空間搜索樹。其中各個節(jié)點(diǎn)處的限界函數(shù)值通過如下方式求得:【排序1分】【狀態(tài)空間搜索樹及其計算過程17分,每個節(jié)點(diǎn)1分】a b. c d. e. f. g. h. i.
4、j. 在Q1處獲得該問題的最優(yōu)解為,背包效益為170。即在背包中裝入物品F、B、G、D、A時達(dá)到最大效益,為170,重量為150?!窘Y(jié)論2分】一、 已知,k=1,2,3,4,5,6,r1=5,r2=10,r3=3,r4=12,r5=5,r6=50,r7=6,求矩陣鏈積A1×A2×A3×A4×A5×A6的最佳求積順序。(要求:給出計算步驟)(20分)答:使用動態(tài)規(guī)劃算法進(jìn)行求解。求解矩陣為:【每個矩陣18分】1234561015033040516552010203603302430195030180930177040300018605015006
5、0123456101224220222230344404450560因此,最佳乘積序列為(A1A2)(A3A4)(A5A6),共執(zhí)行乘法2010次?!窘Y(jié)論2分】二、 假設(shè)有7個物品,它們的重量和價值如下表所示。若這些物品均可以被分割,且背包容量M150,如果使用貪心方法求解此背包問題,請回答:(20分)。(1) 對各個物品進(jìn)行排序時,依據(jù)的標(biāo)準(zhǔn)都有哪些?(2) 使用上述標(biāo)準(zhǔn)分別對7個物品進(jìn)行排序,并給出利用各個順序進(jìn)行貪心求解時獲得解。(3) 上述解中哪個是最優(yōu)的? 物品ABCDEFG重量35306050401025價值10403050354030答:(1)標(biāo)準(zhǔn):重量、價值和單位價值。【3分,
6、每個1分】(2)使用重量從小到大:FGBAEDC。得到貪心解為:FGBAE全部放入,而D放入20%,得到價值為165?!?分】使用價值從大到?。篋FBEGCA,得到貪心解為:DFBE全部放入,而G放入80%,得到價值為:189。【5分】使用單位價值從大到?。篎BGDECA,得到貪心解為:FBGD全部放入,而E放入87.5%,得到價值為190.625?!?分】(3)顯然使用單位價值作為標(biāo)準(zhǔn)得到的是最優(yōu)解。【2分】三、 對于下圖使用Dijkstra算法求由頂點(diǎn)a到其他各個頂點(diǎn)的最短路徑。并給出求各個頂點(diǎn)對之間的最短路徑的算法思想。(20分)。答:三、用V1表示已經(jīng)找到最短路徑的頂點(diǎn),V2表示與V1中某個頂點(diǎn)相鄰接且不在V1中的頂點(diǎn);E1表示加入到最短路徑中的邊,E2為與V1中的頂點(diǎn)相鄰接且距離最短的路徑。【1分】步驟 V1 V2 E1 E21. ab ab2. a,bd ab bd3. a,b,d c,f ab,bd dc,df4. a,b,d,c f ab,bd df5. a,b,c,d,f e ab,bd,dc,df fe6. a,b,c,d,e,fg ab,bd,dc,df,fe eg7. a,b,c,d,e,f,gh ab,bd,dc,df,fe,eggh8. a,b,c,d,e,f,g,h ab,bd,de,df,fe,eg,gh 【以上每步
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 藥品銷售儲存管理制度
- 藥店倉庫發(fā)貨管理制度
- 藥店店員交易管理制度
- 萊昂納德負(fù)荷管理制度
- 設(shè)備臨床準(zhǔn)入管理制度
- 設(shè)備公司安全管理制度
- 設(shè)備安全連鎖管理制度
- 設(shè)備標(biāo)準(zhǔn)機(jī)臺管理制度
- 設(shè)備狀態(tài)評價管理制度
- 設(shè)備維護(hù)部門管理制度
- 2025年小學(xué)語文期末考試試題及答案
- 2024年浙江省《輔警招聘考試必刷500題》考試題庫附答案【綜合題】
- 200以內(nèi)加減法-2000題(帶答案)
- 第五單元《面積》(教學(xué)設(shè)計)-【大單元教學(xué)】三年級數(shù)學(xué)下冊同步備課系列(人教版)
- 閱讀認(rèn)知策略的跨學(xué)科研究框架構(gòu)建
- 廣東省廣州市越秀區(qū)2022-2023學(xué)年七年級下學(xué)期期末考試英語試題(含答案)
- 嬰兒領(lǐng)養(yǎng)協(xié)議10篇
- 摜蛋考試試題及答案
- 肝癌中西醫(yī)治療
- GA/T 2159-2024法庭科學(xué)資金數(shù)據(jù)清洗規(guī)程
- DB63-T 2129-2023 鹽湖資源開發(fā)標(biāo)準(zhǔn)體系
評論
0/150
提交評論