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

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