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

算法設(shè)計(jì)與分析試題對(duì)于下圖使用Dijkstra算法求由頂點(diǎn)a到頂點(diǎn)h的最短路徑。解：用V1表示已經(jīng)找到最短路徑的頂點(diǎn)，V2表示與V1中某個(gè)頂點(diǎn)相鄰接且不在V1中的頂點(diǎn)；E1表示加入到最短路徑中的邊，E2為與V1中的頂點(diǎn)相鄰接且距離最短的路徑?！?分】步驟V1V2E1 E2{a} {} {ab}{a,b} vxoa841{ab} {bd}{a,b,d} {c,f} {ab,bd} {dc,df}{a,b,d,c} {f}{ab,bd} {df}{a,b,c,d,f}{e} {ab,bd,dc,df} {fe}{a,b,c,d,e,f} {g} {ab,bd,dc,df,fe} {eg}{a,b,c,d,e,f,g} {h} {ab,bd,dc,df,fe,eg} {gh}{a,b,c,d,e,f,g,h} {} {ab,bd,de,df,fe,eg,gh} {}【以上每步2分】結(jié)果：從a到h的最短路徑為，權(quán)值為18?！?分】求所有頂點(diǎn)對(duì)之間的最短路徑可以使用Dijkstra算法，使其起始節(jié)點(diǎn)從a循環(huán)到h，每次求起始節(jié)點(diǎn)到其他節(jié)點(diǎn)的最短路徑，最終可以求得所有頂點(diǎn)對(duì)之間的最短路徑?！?分】假設(shè)有7個(gè)物品，它們的重量和價(jià)值如下表所示。若這些物品均不能被分割，且背包容量M＝150，使用回溯方法求解此背包問題。請(qǐng)寫出狀態(tài)空間搜索樹。物品ABCDEFG重量35306050401025價(jià)值10403050354030解：按照單位效益從大到小依次排列這7個(gè)物品為：FBGDECA。將它們的序號(hào)分別記為1～7。則可生產(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.j.在Q1處獲得該問題的最優(yōu)解為，背包效益為170。即在背包中裝入物品F、B、G、D、A時(shí)達(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的最佳求積順序。（要求：給出計(jì)算步驟）解：使用動(dòng)態(tài)規(guī)劃算法進(jìn)行求解。求解矩陣為：【每個(gè)矩陣18分】12345610150330405165520102036033024301950301809301770403000186050150060123456101224220222230344404450560因此，最佳乘積序列為（A1A2）（（A3A4）（A5A6）），共執(zhí)行乘法2010次。【結(jié)論2分】四、回答如下問題：什么是算法？算法的特征有哪些？什么是P類問題？什么是NP類問題？請(qǐng)描述集合覆蓋問題的近似算法的基本思想。解：（1）算法是解決某類問題的一系列運(yùn)算的集合【2分】。具有有窮行、可行性、確定性、0個(gè)或者多個(gè)輸入、1個(gè)或者多個(gè)輸出【8分】。（2）用確定的圖靈機(jī)可以在多項(xiàng)式實(shí)踐內(nèi)可解的判定問題稱為P類問題【2分】。用不確定的圖靈機(jī)在多項(xiàng)式實(shí)踐內(nèi)可解的判定問題稱為P類問題?！?分】集合覆蓋問題的近似算法采用貪心思想：對(duì)于問題<X,F>，每次選擇F中覆蓋了盡可能多的未被覆蓋元素的子集S，然后將U中被S覆蓋的元素刪除，并將S加入C中，最后得到的C就是近似最優(yōu)解?！?分】五、排序和查找是常用的計(jì)算機(jī)算法。按照要求完成以下各題：對(duì)數(shù)組A={15，9，115，118，3，90，27，25，5}，使用合并排序方法將其排成遞減序。若改變二分搜索法為三分搜索法，即從一個(gè)遞減序列A中尋找元素Z，先與元素比較，若，則在前面?zhèn)€元素中尋找Z；否則與比較，總之使余下的序列為個(gè)元素。給出該方法的偽代碼描述。使用上述算法對(duì)（1）所得到的結(jié)果搜索如下元素，并給出搜索過程：118，31，25。解：（1）第一步：15911511839027255 第二步：15911811590327255 第三步：11811515990272535 第四步：11811590272515935 第五步：11811590272515953【5分，每步1分】（2）輸入：遞減數(shù)組A[left:right]，待搜索元素v?！?分】輸出：v在A中的位置pos，或者不在A中的消息（-1）?！?分】步驟：【8分】intBinarySearch(intA[],intleft,intright,intv){ intmid; while(left<=right) { first=left+(right-left+1)/3; second=left+(right-left+1)/3*2; if(v==A[first])returnfirst; elseif(v>A[first])right=first-1; elseif(v==A[second])returnsecond; elseif(v>A[second]){left=first+1;right=second-1;} elseleft=second+1; } return-1; }（3）搜索118：118>27，所以right＝3；118>115，所以right＝1；118＝118，找到?！?分】搜索31：31>27，所以right＝3；31<90，所以left=4，結(jié)束，未找到。【2分】搜索25：9<25<27，所以left=5，right=6；25＝25，找到?！?分】六、假設(shè)有7個(gè)物品，它們的重量和價(jià)值如下表所示。若這些物品均可以被分割，且背包容量M＝150，如果使用貪心方法求解此背包問題，請(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分】（2）使用重量從小到大：FGBAEDC。得到貪心解為：FGBAE全部放入，而D放入20%，得到價(jià)值為165。【5分】使用價(jià)值從大到?。篋FBEGCA，得到貪心解為：DFBE全部放入，而G放入80%，得到價(jià)值為：189?！?分】使用單位價(jià)值從大到?。篎BGDECA，得到貪心解為：FBGD全部放入，而E放入87.5%，得到價(jià)值為190.625?！?分】（3）顯然使用單位價(jià)值作為標(biāo)準(zhǔn)得到的是最優(yōu)解?！?分】七、多段圖問題：設(shè)G＝(V，E)是一個(gè)賦權(quán)有向圖，其頂點(diǎn)集V被劃分成k>2個(gè)不相交的子集Vi：，其中，V1和Vk分別只有一個(gè)頂點(diǎn)s（稱為源）和一個(gè)頂點(diǎn)t（稱為匯），圖中所有的邊（u,v），，。求由s到t的最小成本路徑。（25分）給出使用動(dòng)態(tài)規(guī)劃算法求解多段圖問題的基本思想。使用上述方法求解如下多段圖問題。解：（1）基本思想：設(shè)P(i,j)是從Vi中的節(jié)點(diǎn)j到匯點(diǎn)t的最小成本路徑，Cost(i,j)是其成本。則。邊界條件是（1）若h=t，則Cost(h,t)＝0；（2）Cost(k-1,j)＝c(j,t)。【10分】（2）求解過程可以表示為：【6分，每個(gè)節(jié)點(diǎn)0.5分】其中每個(gè)節(jié)點(diǎn)標(biāo)示的序偶(p,q)中，p表示節(jié)點(diǎn)到t的成本，q表示后繼節(jié)點(diǎn)的編號(hào)。從而，最優(yōu)路徑為：1271012和1361012，成本為16。【4分】八、設(shè)x1、x2、x3是一個(gè)三角形的三條邊，而且x1+x2+x3=14。請(qǐng)問有多少種不同的三角形？給出解答過程。解：由于x1、x2、x3是三角形的三條邊，從而xi+xj>xk，|xi-xj|<xk，（i,j,k=1,2,3），【4分】根據(jù)x1+x2+x3=14可知1<xi<7（i=1,2,3）【4分】。利用回溯法求解得到：【7分，每個(gè)節(jié)點(diǎn)0.5分】即有4個(gè)可行解：（6，6，2），（6，5，3），（6，4，4，）（5，5，4）?！?分】九、15謎問題：在一個(gè)4×4的方格的棋盤上，將數(shù)字1到15代表的15個(gè)棋子以任意的順序置入各方格中，空出一格。要求通過有限次的移動(dòng)，把一個(gè)給定的初始狀態(tài)變成目標(biāo)狀態(tài)。移動(dòng)的規(guī)則是：每次只能把空格周圍的四格數(shù)字（棋子）中的任意一個(gè)移入空格，從而形成一個(gè)新的狀態(tài)。為了有效的移動(dòng)，設(shè)計(jì)了估值函數(shù)C1(x)，表示在結(jié)點(diǎn)x的狀態(tài)下，沒有到達(dá)目標(biāo)狀態(tài)下的正確位置的棋子的個(gè)數(shù)。解：【每個(gè)節(jié)點(diǎn)1分，注意限界值。總共20分】十、設(shè)數(shù)組A有n個(gè)元素，需要找出其中的最大最小值。（20分）請(qǐng)給出一個(gè)解決方法，并分析其復(fù)雜性。把n個(gè)元素等分為兩組A1和A2，分別求這兩組的最大值和最小值，然后分別將這兩組的最大值和最小值相比較，求出全部元素的最大值和最小值。如果A1和A2中的元素多于兩個(gè)，則再用上述方法各分為兩個(gè)子集。直至子集中元素至多兩個(gè)元素為止。這是什么方法的思想？請(qǐng)給出該方法的算法描述，并分析其復(fù)雜性。解：（1）基本思想：從頭到尾逐個(gè)掃描，紀(jì)錄最大和最小元素。【2分】輸入：具有n個(gè)元素的數(shù)組【1分】輸出：最大值和最小值【1分】步驟：【4分】voidFindMaxMin(intA[],intn,intmax,intmin){ max=min=A[0]; for(i=1;i<n;i++) { if(A[i]>max)max=A[i]; if(A[i]<min)min=A[i]; }}復(fù)雜性分析：由于是從頭到尾掃描各個(gè)元素，而每個(gè)元素都要與max和min比較一遍，從而時(shí)間復(fù)雜性為：O(n)?！?分】（2）【10分】voidFindMaxMin(intleft,intright,intmax,intmin) { if(left==right)max=min=A[left]; elseif(left=right-1) { max=(A[left]<A[right]?A[right]:A[left]); min=(A[left]<A[right]?A[left]:A[right]); } else{ mid=(left+right)/2; FindMaxMin(left,mid,gmax,gmin); FindMaxMin(mid+1,right,hmax,hmin); max=(gmax<hmax?hmax:gmax); min=(gmin<hmin?gmin:hmin]); }}十一、用分支限界法解裝載問題時(shí)，對(duì)算法進(jìn)行了一些改進(jìn)，下面的程序段給出了改進(jìn)部分；試說明斜線部分完成什么功能，以及這樣做的原因，即采用這樣的方式，算法在執(zhí)行上有什么不同。////檢查左兒子結(jié)點(diǎn)Typewt=Ew+w[i];//左兒子結(jié)點(diǎn)的重量if(wt<=c){//可行結(jié)點(diǎn)if(wt>bestw)bestw=wt;//加入活結(jié)點(diǎn)隊(duì)列if(i<n)Q.Add(wt);}//檢查右兒子結(jié)點(diǎn)if(Ew+r>bestw&&i<n)Q.Add(Ew);//可能含最優(yōu)解Q.Delete(Ew);//取下一擴(kuò)展結(jié)點(diǎn)解：斜線標(biāo)識(shí)的部分完成的功能為：提前更新bestw值；這樣做可以盡早的進(jìn)行對(duì)右子樹的剪枝。具體為：算法Maxloading初始時(shí)將bestw設(shè)置為0，直到搜索到第一個(gè)葉結(jié)點(diǎn)時(shí)才更新bestw。因此在算法搜索到第一個(gè)葉子結(jié)點(diǎn)之前，總有bestw=0，r>0故Ew+r>bestw總是成立。也就是說，此時(shí)右子樹測(cè)試不起作用。為了使上述右子樹測(cè)試盡早生效，應(yīng)提早更新bestw。又知算法最終找到的最優(yōu)值是所求問題的子集樹中所有可行結(jié)點(diǎn)相應(yīng)重量的最大值。而結(jié)點(diǎn)所相應(yīng)得重量僅在搜索進(jìn)入左子樹是增加，因此，可以在算法每一次進(jìn)入左子樹時(shí)更新bestw的值。十二、簡(jiǎn)要回答下列問題：1.算法重要特性是什么？算法分析的目的是什么？算法的時(shí)間復(fù)雜性與問題的什么因素相關(guān)？2.什么是哈密頓環(huán)問題？用回溯法求解哈密頓環(huán)，如何定義判定函數(shù)？答：1.（1）確定性、可實(shí)現(xiàn)性、輸入、輸出、有窮性，（2）分析算法占用計(jì)算機(jī)資源的情況，對(duì)算法做出比較和評(píng)價(jià)，設(shè)計(jì)出額更好的算法，（3）算法的時(shí)間復(fù)雜性與問題的規(guī)模相關(guān)，是問題大小n的函數(shù)；2.（1）哈密頓環(huán)是指一條沿著圖G的N條邊環(huán)行的路徑，它的訪問每個(gè)節(jié)點(diǎn)一次并且返回它的開始位置，（2）當(dāng)前選擇的節(jié)點(diǎn)X[k]是從未到過的節(jié)點(diǎn),即X[k]≠X[i](i=1,2,…,k-1)，且C(X[k-1],X[k])≠∞，如果k=-1，則C(X[k],X[1])≠∞。十三、簡(jiǎn)要回答下列問題：快速排序的基本思想是什么。什么是直接遞歸和間接遞歸？消除遞歸一般要用到什么數(shù)據(jù)結(jié)構(gòu)？答：1.快速排序的基本思想是在待排序的N個(gè)記錄中任意取一個(gè)記錄，把該記錄放在最終位置后，數(shù)據(jù)序列被此記錄分成兩部分。所有關(guān)鍵字比該記錄關(guān)鍵字小的放在前一部分，所有比它大的放置在后一部分，并把該記錄排在這兩部分的中間，這個(gè)過程稱作一次快速排序。之后重復(fù)上述過程，直到每一部分內(nèi)只有一個(gè)記錄為止。2..在定義一個(gè)過程或者函數(shù)的時(shí)候又出現(xiàn)了調(diào)用本過程或者函數(shù)的成分，既調(diào)用它自己本身，這稱為直接遞歸。如果過程或者函數(shù)P調(diào)用過程或者函數(shù)Q，Q又調(diào)用P，這個(gè)稱為間接遞歸。消除遞歸一般要用到棧這種數(shù)據(jù)結(jié)構(gòu)。十四、寫出多段圖最短路經(jīng)動(dòng)態(tài)規(guī)劃算法求解下列實(shí)例的過程，并求出最優(yōu)值。5252863186317474各邊的代價(jià)如下：C(1,2)=3，C(1,3)=5，C(1,4)=2C(2,6)=8，C(2,7)=4，C(3,5)=5，C(3,6)=4，C(4,5)=2，C(4,6)=1C(5,8)=4，C(6,8)=5，C(7,8)=6解：Cost(4,8)=0Cost(3,7)=C(7,8)+0=6，D[5]=8Cost(3,6)=C(6，8)+0=5,D[6]=8Cost(3,5)=C(5，8)+0=4D[7]=8Cost(2,4)=min{C(4，6)+Cost(3,6),C(4，5)+Cost(3,5)}=min{1+5,2+4}=6D[4]=6Cost(2,3)=min{C(3，6)+Cost(3,6)}=min{4+5}=9D[3]=5Cost(2,2)=min{C(2，6)+Cost(3,6),C(2，7)+Cost(3,7)}=min{8+5,4+6}=10D[2]=7Cost(1,1)=min{C(1,2)+Cost(2,2),C(1,3)+Cost(2,3),C(1,4)+Cost(2,4)}=min{3+10,5+9,2+6}=8D[1]=41→4→6→8十五、寫出maxmin算法對(duì)下列實(shí)例中找最大數(shù)和最小數(shù)的過程。數(shù)組A=(48,12,61,3,5,19,32,7)解：寫出maxmin算法對(duì)下列實(shí)例中找最大數(shù)和最小數(shù)的過程。數(shù)組A=()1、48,12,61,3,5,19,32,72、48,1261,35,1932,73、48～61,12～319～32，5～74、61～323～55、613十六、快速排序算法對(duì)下列實(shí)例排序，算法執(zhí)行過程中，寫出數(shù)組A第一次被分割的過程。A=(65,70,75,80,85,55,50,2)解：第一個(gè)分割元素為65(1)(2)(3)(4)(5)(6)(7)(8)ip(1)(2)(3)(4)(5)(6)(7)(8)ip65707580855550228652758085555070376525080855575704665250558580757046557075808565502十七、一個(gè)旅行者要駕車從A地