最新算法設(shè)計(jì)與分析c語言描述陳慧南版課后答案-資料下載頁
2025-06-25 15:16本頁面
【正文】 int LCS::LCSLength() {for ( int i =1。 i=m。 i++) c[i][0]=0。for (i =1。 i=n。 i++) c[0][i]=0。for (i =1。 i=m。 i++) for (int j =1。 j=n。 j++) if (x[i]= =y[j]) c[i][j]=c[i1][j1]+1。 else if (c[i1][j]=c[i][j1]) c[i][j]=c[i1][j]。 else c[i][j]=c[i][j1]。return c[m][n]。 }15. , , , , , , ,81．狀態(tài)空間：描述問題的各種可能的情況，一種情況對呀狀態(tài)空間的一個(gè)狀態(tài)。顯示約束：用于規(guī)定每個(gè)xi取值的約束條件稱為顯示約束隱式約束：用于判定一個(gè)候選解是否為可行解的條件問題狀態(tài)：在狀態(tài)空間樹中的每個(gè)節(jié)點(diǎn)稱為一個(gè)問題狀態(tài)解狀態(tài)：如果從根到樹中某個(gè)狀態(tài)的路徑代表一個(gè)作為候選解的元組，則該狀態(tài)為解狀態(tài)答案狀態(tài)：如果從根到樹中某個(gè)狀態(tài)的路徑代表一個(gè)作為可行解的元組，則該狀態(tài)為解狀態(tài)?；罱Y(jié)點(diǎn)：回溯法從開始結(jié)點(diǎn)出發(fā)，以深度優(yōu)先的方式搜索整個(gè)解空間，這個(gè)開始結(jié)點(diǎn)就成為一個(gè)活結(jié)點(diǎn)。未檢測的結(jié)點(diǎn)稱為活結(jié)點(diǎn)擴(kuò)展結(jié)點(diǎn)：算法從x出發(fā)，訪問x的摸個(gè)后繼結(jié)點(diǎn)y，則x被稱為擴(kuò)展結(jié)點(diǎn)約束函數(shù)：一個(gè)約束函數(shù)是關(guān)于部分向量的函數(shù)Bk(x0,x1.....xk),它被定義為：如果可以判定Y的子樹上不含任何答案狀態(tài)，則Bk(x0,x1.....xk)為false,否則為true.剪枝函數(shù)：約束函數(shù)和限界函數(shù)的目的相同，都是為了剪去不必要搜索的子樹，減少問題求解所需實(shí)際生成的狀態(tài)節(jié)點(diǎn)數(shù)，他們統(tǒng)稱為剪枝函數(shù)82bool place(int k,int ,I,int*x){For(int j=0,jk,j++) If((x[j]==i)||(abs(x[j]j)==abs(jk)))Return false。 Return true。}Void nqueens(int k,int n,int *x){For(int i=0。in。i++) If(place(k,I,x)){ X[k]=I。 If(k= =n1{ For(i=0。in。i++)coutx[i]endl。 Return。}Else nqueens(k+1,n,x)} }Void nqueens(int n,int *x){ Nqueens(0,n,x)。}
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1