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

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)記的方格，請按照隊列式分支限界法在圖中確定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)先隊列式分支限界法求解時的搜索情況。表示出優(yōu)先隊列、當(dāng)前擴(kuò)展結(jié)點等的變化情

3、況。8 依據(jù)優(yōu)先隊列式分支限界法，求從s點到t點的單源最短路徑，畫出求得最優(yōu)解的解空間樹。一、 假設(shè)有7個物品，它們的重量和價值如下表所示。若這些物品均不能被分割，且背包容量M150，使用回溯方法求解此背包問題。請寫出狀態(tài)空間搜索樹（20分）。 物品ABCDEFG重量35306050401025價值10403050354030答：按照單位效益從大到小依次排列這7個物品為：FBGDECA。將它們的序號分別記為17。則可生產(chǎn)如下的狀態(tài)空間搜索樹。其中各個節(jié)點處的限界函數(shù)值通過如下方式求得：【排序1分】【狀態(tài)空間搜索樹及其計算過程17分，每個節(jié)點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次。【結(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)：重量、價值和單位價值?！?分，

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