中國(guó)科學(xué)院大學(xué)計(jì)算機(jī)學(xué)院計(jì)算機(jī)算法劉玉貴期末題庫(kù)習(xí)題答案-第九十十一章練習(xí)參考答案

第九十十一章練習(xí)參考答案第9章1.答：Intselection(int*s,double*P,intn){//賭輪法選擇,設(shè)s[i]整數(shù)doublewheel_pos;partsum=0;inti=0wheel_pos=frandom();//賭輪位置[0-1]partsum=0;do{ partsum=partsum+p[i]i++}while(partsum<wheel_pos&&i<n);returns[i-1];}（這可看做是一個(gè)舍伍得算法。舍伍得算法其它練習(xí)如：給定問(wèn)題的編碼策略，求一個(gè)隨機(jī)初值。如0/1背包遺傳算法，解=(x1,x2,..xn)，xi∈{0,1},請(qǐng)隨機(jī)生成一個(gè)初始解。）2.解：從1-365個(gè)整數(shù)中依次隨機(jī)抓取25個(gè)，其可能的排列數(shù)為365.364…341=365!/340!；如果允許重復(fù)，即一個(gè)數(shù)抓出來(lái)后，再放回去繼續(xù)用，則有36525種排列，二者之比為R=365!/(340!.36525)。可用隨機(jī)選取25個(gè)1-365間的數(shù)，求其中沒(méi)有重復(fù)數(shù)字排列所占比例R來(lái)近似計(jì)算。doubleR(){doubler;intp[25],i,j,L,tintm,n//總抓取次數(shù)、有重復(fù)數(shù)字次數(shù)L=1000000;t=0//控制提前跳出for循環(huán)dowhilem<L{for(i=1to25){P[i]=random(365)+1//隨機(jī)產(chǎn)生1-365之間的整數(shù)for(j=1toi-1){ifp[j]=p[i]{n=n+1；//本組出現(xiàn)重復(fù)數(shù)字t=1break;}if(t=1)break;}m=m+1;t=0;}Return(double)(m-n)/m；}3.解：修改第7章分枝限界算法，四個(gè)方向隨機(jī)選擇一個(gè)未被標(biāo)記的方向擴(kuò)展：以下是LasVegas算法：(需重復(fù)調(diào)用本程序或成功，或達(dá)到一定次數(shù)返回不可達(dá)結(jié)果。第二問(wèn)，修改while循環(huán)條件，可控制僅隨機(jī)完成若干段布線，后邊接隊(duì)列式分枝限界算法完成后面的布線，參考第九章n皇后問(wèn)題，及第七章電路板布線問(wèn)題算法。（略）)boolFindPath(Positionstart,Positionfinish,int&PathLen,Position*&path){//計(jì)算從起點(diǎn)位置start到目標(biāo)位置//finish的最短布線路徑.找到最短布//線路徑則返回true,否則返回falseif((start.row==finish.row)&&(start.col==finish.col){PathLen=0;returntrue;}//start=finish//設(shè)置方格陣列“圍墻”for(inti=0;i<=m+1;i++)grid[0][i]=grid[n+1][i]=1;//頂部和底部for(inti=0;i<=n+1;i++)grid[i][0]=grid[i][m+1]=1;//左翼和右翼Positionoffset[4];//初始化相對(duì)位移offset[0].row=0;offset[0].col=1;//右offset[1].row=1;offset[1].col=0;//下offset[2].row=0;offset[2].col=-1;//左offset[3].row=-1;offset[3].col=0;//上intNumOfNbrs=4;//相鄰方格數(shù)Positionhere,nbr;here.row=start.row;here.col=start.col;grid[start.row][start.col]=2;//標(biāo)記可達(dá)方格位置do{//標(biāo)記相鄰可達(dá)方格count=0；for(inti=0;i<NumOfNbrs;i++){nbr.row=here.row+offset[i].row;nbr.col=here.col+offset[i].col;if(grid[nbr.row][nbr.col]==0)y[count++]=i;//該方格未被標(biāo)記，記錄該方向。不再用隊(duì)列。}if(count>0){//有布線位置

i=y[rnd.Random(count)];//隨機(jī)選一個(gè)方向nbr.row=here.row+offset[i].row;nbr.col=here.col+offset[i].col;grid[nbr.row][nbr.col]=grid[here.row][here.col]+1;}elsereturn//無(wú)進(jìn)一步擴(kuò)展位置，隨機(jī)布線失敗if((nbr.row==finish.row)&&(nbr.col==finish.col))break;//若到達(dá)目標(biāo)位置跳出do//從本節(jié)點(diǎn)再擴(kuò)展here.row=nbr.rowhere.col=nbr.col}while(true);//構(gòu)造最短布線路徑PathLen=grid[finish.row][finish.col]-2;path=newPosition[PathLen];//從目標(biāo)位置finish開(kāi)始向起始位置回溯here=finish;for(intj=PathLen-1;j>=0;j--){path[j]=here;//找前驅(qū)位置for(inti=0;i<NumOfNbrs;i++){nbr.row=here.row+offset[i].row;nbr.col=here.col+offset[i].col;if(grid[nbr.row][nbr.col]==j+2)break;}here=nbr;//向前移動(dòng)}returntrue;}4.答：(1)LasVegas算法不會(huì)得到不正確的解。(√)(2)MonteCarlo算法不會(huì)得到不正確的解。(×)(3)LasVegas算法總能求得一個(gè)解。(×)(4)MonteCarlo算法總能求得一個(gè)解。(√)5.答：1-(1-)k6.答:(2)。（反之，偏真的,答案(1)）7.答：（1）一般情況下，無(wú)法有效判定LasVegas算法所得解是否肯定正確。（×）（2）一般情況下，無(wú)法有效判定MonteCarlo算法所得解是否肯定正確。（√）（3）雖然在某些步驟引入隨機(jī)選擇，但Sherwood算法總能求得問(wèn)題的一個(gè)解，且所求得的解總是正確的。(√)（4）雖然在某些步驟引入隨機(jī)選擇，但Sherwood算法總能求得問(wèn)題的一個(gè)解，但一般情況下，無(wú)法有效判定所求得的解是否正確。(×)第10章證明：當(dāng)FF(I)=1時(shí)，顯然FF(I)=OPT(I)。下面設(shè)FF(I)>1，記w=。因?yàn)槿魏蝺芍幌渥拥闹亓恐痛笥贐（否則不會(huì)開(kāi)新箱子，可裝到一個(gè)箱子里），因此，當(dāng)FF(I)為偶數(shù)時(shí)，W>B×FF(I)/2；當(dāng)FF(I)為奇數(shù)時(shí)，設(shè)最重的箱子重量為B1，則有W>B×(FF(I)-1)/2+B1>B×FF(I)/2。故總有FF(I)<2W/B。又顯然OPT(I)≥W/B，得FF(I)<2OPT(I)。證明：根據(jù)算法，每一個(gè)頂點(diǎn)關(guān)聯(lián)的割邊數(shù)大于等于關(guān)聯(lián)的非割邊數(shù)，對(duì)所有的頂點(diǎn)求和，每條邊出現(xiàn)2次，故所有的割邊數(shù)大于等于所有非割邊數(shù)。從而MCUT(I)≥|E|/2。又顯然OPT(I)≤|E|，得證OPT(I)≤2MCUT(I)。解：遞推公式：B(0)=0,B(i)=B(i-1)∪{t|t-ti∈B(i-1),ti≤D},i=1,2,…n。顯然，OPT(I)=。算法DP輸入：n個(gè)作業(yè)的處理時(shí)間t[1..n]DP(t[]){D=;B(0)=0;fori=1ton{B(i):=B(i-1);fort=t[i]toDif(t-t[i]∈B(i-1))B(i)=B(i)∪{t}；}t:=maxB(n);J=;}輸出-t；//最優(yōu)解for(i=nto1step-1){ift-t[i]∈B(i-1){J=J∪{i};t=t-t[i]if(t<=0)break;}}輸出J,{1,2,…n}\J；//解集合I1、I2}DP的時(shí)間復(fù)雜度為T(mén)(n)=O(nD)=O(n2tmax)，這是偽多項(xiàng)式時(shí)間算法。以此為基礎(chǔ)，設(shè)計(jì)近似算法：FPTAS(t[],){tmax=max{t[i]|i=1,2,…n};b=max{tmax/(1+1/)n,1};for(i=1ton)t/[i]=t[i]/b;DP(t/[])//以t/[1..n]調(diào)用算法DP}FPTAS的時(shí)間復(fù)雜度T(n)=O(n2t/max)=O(n2tmax/b)=O(n3(1+1/))。下面分析其近似性能。當(dāng)b=1時(shí)，F(xiàn)PTAS得到最優(yōu)解。不妨設(shè)b>1，b(t/[i]-1)<t[i]≤bt/[i]。對(duì)任意S{1,2,…,n}，，則（*）記最優(yōu)解J*，F(xiàn)PTAS的近似解J,j/={1,2…,n}-J，OPT(I)=，F(xiàn)PTAS(I)=，于是FPTAS(I)-OPT(I)=-=(-)+(-)+(-)由(*)式，第一項(xiàng)小于等于0，J/是關(guān)于t/[1..n]的最優(yōu)解，第二項(xiàng)也小于等于0，又顯然FPTAS(I)≥tmax,于是FPTAS(I)-OPT(I)≤-≤bn≤tmax/(1+1/)≤FPTAS(I)/(1+1/)化簡(jiǎn)即得FPTAS(I)≤(1+)OPT(I)，得證FPTAS是完全多項(xiàng)式時(shí)間近似方案。（類(lèi)似0/1背包問(wèn)題，但本例求最小。另外，第5章中所謂優(yōu)化動(dòng)態(tài)規(guī)劃算法，可仿本例定義V[i]={v|v=,含義為前i項(xiàng)物品任意裝法所得收益值的集合，按其遞推公式設(shè)計(jì)的動(dòng)態(tài)規(guī)劃算法就是那個(gè)算法，可能更容易按動(dòng)態(tài)規(guī)劃思想理解。）看ppt答：(1)旅行商問(wèn)題存在多項(xiàng)式時(shí)間近似方案。(×)(2)0/1背包問(wèn)題存在多項(xiàng)式時(shí)間近似方案。(√)(3)0/1背包問(wèn)題的貪心算法(單位價(jià)值高優(yōu)先裝入)是絕對(duì)近似算法。(×)(4)多機(jī)調(diào)度問(wèn)題的貪心近似算法(按輸入順序?qū)⒆鳂I(yè)分配給當(dāng)前最小負(fù)載機(jī)器)是-近似算法。(√)第11章解：N(s)={(1324),(2134),(4123),(3214),(3421),(3142)}解：N(x)={01001,10001,11101,11011,11000}?？磒pt解：影響力大的對(duì)象是指改變它，可以導(dǎo)致目標(biāo)值發(fā)生較大幅度的變化(可能變壞也可能變好)。如0/1背包問(wèn)題，物品重量大的對(duì)象影響力大，特赦后可以騰出較大背包容量。解：(1)禁忌搜索中，禁忌某些對(duì)象是為了避免鄰域中的不可行解。(×)(2)禁忌長(zhǎng)度越大越好。(×)(3)禁忌長(zhǎng)度越小越好。(×)6.看ppt7.答：tk越高接受的概率越大，fij越小接受退步解的概率越大。8.答：(1)(2)(3)9.答：排序適應(yīng)函數(shù)：線性加速適應(yīng)函數(shù)：fitness(x)=af(x)+bf(x)等。10．簡(jiǎn)單交配可能產(chǎn)生非解編碼(染色體)。解決辦法:改變交配規(guī)則，如交配位后基因按異方基因順序選取不重復(fù)基因、不變位法等。11.下面屬于遺傳算法實(shí)現(xiàn)的關(guān)鍵技術(shù)問(wèn)題的有___________。(1)解的編碼(2)初始種群的選擇(3)鄰域定義(4)適應(yīng)函數(shù)答：（1）（4）第8章補(bǔ)充練習(xí)1.下面說(shuō)法，正確的是：______1、3、______.(1)P類(lèi)問(wèn)題是存在多項(xiàng)式時(shí)間算法的問(wèn)題。(2)