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

1、按分治策略求解棋盤覆蓋問(wèn)題時(shí)，對(duì)于如圖所示的24X24的特殊棋盤，共需要多少個(gè)L型骨牌；并在棋盤上填寫L型骨牌的覆蓋情況。假設(shè)有7個(gè)物品，給出重量和價(jià)值。若這些物品均不能被分割，且背包容量M=140,使用回溯方法求解此0-1背包問(wèn)題。請(qǐng)畫出狀態(tài)空間搜索樹。假設(shè)有7個(gè)物品，它們的重量和價(jià)值如下表所示。若這些物品均可以被分割，且背包容量M=140,使用貪心算法求解此背包問(wèn)題。請(qǐng)寫出求解策略和求解過(guò)程。W(35,30,50,60,40,10,25)p(10,40,30,50,35,40,30)在給出的電路板中，陰影部分是已作了封鎖標(biāo)記的方格，請(qǐng)按照隊(duì)列式分支限界法在圖中確定a到b的最短布線方案，要求

2、布線時(shí)只能沿直線或直角進(jìn)行，在圖中標(biāo)出求得最優(yōu)解時(shí)各方格情況。畫出字符表的哈夫曼編碼對(duì)應(yīng)的二叉樹。已知A(a(k)，k=1，2，3，4，5，6，r=5，r=10，r=3，r=8，r=5，r=20，r=6，求k*k1234567矩陣鏈積a,xa2xa3xa4xa5xa6的最佳求積順序。123456給出城市網(wǎng)絡(luò)圖，售貨員要從城市1出發(fā)，經(jīng)過(guò)所有城市回到城市1，畫出該問(wèn)題的解空間樹，描述出用優(yōu)先隊(duì)列式分支限界法求解時(shí)的搜索情況。表示出優(yōu)先隊(duì)列、當(dāng)前擴(kuò)展結(jié)點(diǎn)等的變化情況。依據(jù)優(yōu)先隊(duì)列式分支限界法，求從s點(diǎn)到t點(diǎn)的單源最短路徑，畫出求得最優(yōu)解的解空間樹。一、假設(shè)有7個(gè)物品，它們的重量和價(jià)值如下表所示。若

3、這些物品均不能被分割，且背包容量M=150，使用回溯方法求解此背包問(wèn)題。請(qǐng)寫出狀態(tài)空間搜索樹(20分)。物品ABCDEFG重量35306050401025價(jià)值10403050354030答：按照單位效益從大到小依次排列這7個(gè)物品為：FBGDECA。將它們的序號(hào)分別記為17。則可生產(chǎn)如下的狀態(tài)空間搜索樹。其中各個(gè)節(jié)點(diǎn)處的限界函數(shù)值通過(guò)如下方式求得：【排序1分】每個(gè)節(jié)點(diǎn)1分】狀態(tài)空間搜索樹及其計(jì)算過(guò)程17分，a4040305035.15115190.625(1111700)b.4084040305030口0旦15177.5(111100)6012c4040305010170(1,1,1,10,0,

4、1)d.1501054040303530167.560I101;,0)e.1501304040503530175601(1,10,1,1,0)3f.1501304040503510170.71354(1,10,1,1,0,)7g.40405030160(1,10,1,0,1,0)h.1501404040353010146.85352(1,10,0,1,1,)71403005060H67.5j.4030503530十0145157.5tttJ60(01111120)在Q1處獲得該問(wèn)題的最優(yōu)解為(1,1,1,1,0,0,1),背包效益為170。即在背包中裝入物品F、B、G、D、A時(shí)達(dá)到最大效益，為

5、170,重量為150。【結(jié)論2分】一、已知A(a(k)，k=1，2，3，4，5，6，r=5，r=10，r=3，r=12，r=5，r=50，r=6，kijr*r1234567TOC o 1-5 h z丿ii求矩陣鏈積A1XA2XA3XA4XA5XA6的最佳求積順序。(要求：給出計(jì)算步驟)(20分)123456答：使用動(dòng)態(tài)規(guī)劃算法進(jìn)行求解。求解矩陣為：【每個(gè)矩陣18分】12345610150330405165520102036033024301950301809301770403000186050150060123456101224220222230344404450560TOC o 1-5 h

6、z因此，最佳乘積序列為(4A2)(A3A4)(A5A6),共執(zhí)行乘法2010次。【結(jié)論2分】123456二、假設(shè)有7個(gè)物品，它們的重量和價(jià)值如下表所示。若這些物品均可以被分割，且背包容量M=150,如果使用貪心方法求解此背包問(wèn)題，請(qǐng)回答：(20分)。對(duì)各個(gè)物品進(jìn)行排序時(shí)，依據(jù)的標(biāo)準(zhǔn)都有哪些？使用上述標(biāo)準(zhǔn)分別對(duì)7個(gè)物品進(jìn)行排序，并給出利用各個(gè)順序進(jìn)行貪心求解時(shí)獲得解。上述解中哪個(gè)是最優(yōu)的？物品ABCDEFG重量35306050401025價(jià)值10403050354030(1)標(biāo)準(zhǔn)：重量、價(jià)值和單位價(jià)值?！?分，每個(gè)1分】使用重量從小到大：FGBAEDC。得到貪心解為：FGBAE全部放入，而D放入

7、20%，得到價(jià)值為165?！?分】使用價(jià)值從大到?。篋FBEGCA，得到貪心解為：DFBE全部放入，而G放入80%，得到價(jià)值為：189。【5分】使用單位價(jià)值從大到小：FBGDECA,得到貪心解為：FBGD全部放入，而E放入87.5%，得到價(jià)值為190.625。【5分】顯然使用單位價(jià)值作為標(biāo)準(zhǔn)得到的是最優(yōu)解?！?分】三、對(duì)于下圖使用Dijkstra算法求由頂點(diǎn)a到其他各個(gè)頂點(diǎn)的最短路徑。并給出求各個(gè)頂點(diǎn)對(duì)之間的最短路徑的算法思想。(20分)。答：三、用V表示已經(jīng)找到最短路徑的頂點(diǎn)，V2表示與V中某個(gè)頂點(diǎn)相鄰接且不在V中的頂點(diǎn);Et表示加入到最短路徑中的邊,e2為與V,中的頂點(diǎn)相鄰接且距離最短的路徑?！?分】步驟VV2EE2.abab2.a,bdabbd3.a,b,dc,fab,bddc,df4.a,b,d,cfab,bddf5.a,b,c,d,feab,bd,dc,dffe6.a,b,c,d,e,fgab,bd,dc,df,feeg7.a,b,c,d,e,f,ghab,bd,dc,df,fe,eggh8.a,b,c,d,e,f,g,hab,bd,de,df,fe,eg,g