算法設(shè)計(jì)與分析試題及答案

1、1 按分治策略求解棋盤覆蓋問題時(shí)，對(duì)于如圖所示的24×24的特殊棋盤，共需要多少個(gè)L型骨牌；并在棋盤上填寫L型骨牌的覆蓋情況。物品ABCDEFG重量35305060401025價(jià)值104030503540302 假設(shè)有7個(gè)物品，給出重量和價(jià)值。若這些物品均不能被分割，且背包容量M140，使用回溯方法求解此0-1背包問題。請(qǐng)畫出狀態(tài)空間搜索樹。3 假設(shè)有7個(gè)物品，它們的重量和價(jià)值如下表所示。若這些物品均可以被分割，且背包容量M140，使用貪心算法求解此背包問題。請(qǐng)寫出求解策略和求解過程。W（35,30,50,60,40,10,25）p（10,40,30,50,35,40,30）4 在給

2、出的電路板中，陰影部分是已作了封鎖標(biāo)記的方格，請(qǐng)按照隊(duì)列式分支限界法在圖中確定a到b的最短布線方案，要求布線時(shí)只能沿直線或直角進(jìn)行，在圖中標(biāo)出求得最優(yōu)解時(shí)各方格情況。5 畫出字符表的哈夫曼編碼對(duì)應(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ì)列式分支限界法求解時(shí)的搜索情況。表示出優(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個(gè)物品，它們的重量和價(jià)值如下表所示。若這些物品均不能被分割，且背包容量M150，使用回溯方法求解此背包問題。請(qǐng)寫出狀態(tài)空間搜索樹（20分）。 物品ABCDEFG重量35306050401025價(jià)值10403050354030答：按照單位效益從大到小依次排列這7個(gè)物品為：FBGDECA。將它們的序號(hào)分別記為17。則可生產(chǎn)如下的狀態(tài)空間搜索樹。其中各個(gè)節(jié)點(diǎn)處的限界函數(shù)值通過如下方式求得：【排序1分】【狀態(tài)空間搜索樹及其計(jì)算過程17分，每個(gè)節(jié)點(diǎn)1分】a b. c d. e. f. g. h. i.

4、j. 在Q1處獲得該問題的最優(yōu)解為，背包效益為170。即在背包中裝入物品F、B、G、D、A時(shí)達(dá)到最大效益，為170，重量為150。【結(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的最佳求積順序。（要求：給出計(jì)算步驟）（20分）答：使用動(dòng)態(tài)規(guī)劃算法進(jìn)行求解。求解矩陣為：【每個(gè)矩陣18分】1234561015033040516552010203603302430195030180930177040300018605015006

5、0123456101224220222230344404450560因此，最佳乘積序列為（A1A2）（A3A4）（A5A6），共執(zhí)行乘法2010次?！窘Y(jié)論2分】二、 假設(shè)有7個(gè)物品，它們的重量和價(jià)值如下表所示。若這些物品均可以被分割，且背包容量M150，如果使用貪心方法求解此背包問題，請(qǐng)回答：（20分）。（1） 對(duì)各個(gè)物品進(jìn)行排序時(shí)，依據(jù)的標(biāo)準(zhǔn)都有哪些？（2） 使用上述標(biāo)準(zhǔn)分別對(duì)7個(gè)物品進(jìn)行排序，并給出利用各個(gè)順序進(jìn)行貪心求解時(shí)獲得解。（3） 上述解中哪個(gè)是最優(yōu)的？ 物品ABCDEFG重量35306050401025價(jià)值10403050354030答：（1）標(biāo)準(zhǔn)：重量、價(jià)值和單位價(jià)值?！?分，

6、每個(gè)1分】（2）使用重量從小到大：FGBAEDC。得到貪心解為：FGBAE全部放入，而D放入20%，得到價(jià)值為165。【5分】使用價(jià)值從大到?。篋FBEGCA，得到貪心解為：DFBE全部放入，而G放入80%，得到價(jià)值為：189。【5分】使用單位價(jià)值從大到小：FBGDECA，得到貪心解為：FBGD全部放入，而E放入87.5%，得到價(jià)值為190.625?！?分】（3）顯然使用單位價(jià)值作為標(biāo)準(zhǔn)得到的是最優(yōu)解。【2分】三、 對(duì)于下圖使用Dijkstra算法求由頂點(diǎn)a到其他各個(gè)頂點(diǎn)的最短路徑。并給出求各個(gè)頂點(diǎn)對(duì)之間的最短路徑的算法思想。（20分）。答：三、用V1表示已經(jīng)找到最短路徑的頂點(diǎn)，V2表示與V1中某個(gè)頂點(diǎn)相鄰接且不在V1中的頂點(diǎn)；E1表示加入到最短路徑中的邊，E2為與V1中的頂點(diǎn)相鄰接且距離最短的路徑?！?分】步驟 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 【以上每步