算法設(shè)計與分析-課后習(xí)題集答案-資料下載頁
2025-01-09 09:30本頁面
【正文】 元組，則該狀態(tài)為解狀態(tài)。 活結(jié)點(diǎn)：回溯法從開始結(jié)點(diǎn)出發(fā)，以深度優(yōu)先的方式搜索整個解空間，這個開始結(jié)點(diǎn)就成為一個活結(jié)點(diǎn)。未檢測的結(jié)點(diǎn)稱為活結(jié)點(diǎn) 擴(kuò)展結(jié)點(diǎn)：算法從 x出發(fā)，訪問 x的摸個后繼結(jié)點(diǎn) y，則 x被稱為擴(kuò)展結(jié)點(diǎn) 約束函數(shù)：一個約束函數(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ù) 2 int count=0。 int N=1。 bool 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]。 coutendl。 count++。 } Else if(countN) nqueens(k+1,n,x) } } Void nqueens(int n,int *x) { Nqueens(0,n,x)。 } ： 0 , 0 , 8 75 , 1 , 8 25 , 2 , 7 51 5 , 3 , 6 55 , 3 , 6 51 5 , 4 , 5 3 1 7 , 4 , 5 31 5 , 5 , 3 8 1 7 , 5 , 3 81 5 , 6 , 2 00 , 1 , 8 27 , 2 , 7 5 0 , 2 , 7 51 7 , 3 , 6 50 , 3 , 6 51 7 , 4 , 5 30 , 4 , 5 31 7 , 5 , 3 8 1 5 , 5 , 3 81 5 , 6 , 2 0AB CDx [ 0 ] = 1x [ 0 ] = 0x [ 1 ] = 0x [ 1 ] = 1x [ 1 ] = 0x [ 2 ] = 0 x [ 2 ] = 0x [ 2 ] = 1 x [ 2 ] = 1x [ 3 ] = 0 x [ 3 ] = 0 x [ 3 ] = 0x [ 3 ] = 1x [ 4 ] = 0 x [ 4 ] = 0 x [ 4 ] = 0 x [ 4 ] = 1x [ 5 ] = 0 x [ 5 ] = 0x [ 5 ] = 1x [ 5 ] = 1x [ 6 ] = 1 x [ 6 ] = 1 可行解：（ 1， 0， 0， 1， 0， 1）， （ 0， 1， 1， 0， 0， 1）， （ 1， 0， 1， 0， 0， 0， 1）， （ 0， 0， 0， 0， 1， 0， 1） 7. 可行解為： （ 1）（ 1， 0， 0， 1， 0， 1）， （ 0， 1， 1， 0， 0， 1）， （ 1， 0， 1， 0， 0， 0， 1）， （ 0， 0， 0， 0， 1， 0， 1） （ 2）（ 1， 0， 1）， （ 0， 1， 0， 0， 1， 1）， （ 1， 0， 0， 0， 1， 0， 1）， （ 0， 1， 0， 1， 0， 0， 1） （ 3）（ 1， 0， 1）， （ 0， 1， 0， 0， 1， 1）， （ 0， 0， 1， 1， 0， 1）， （ 0， 0， 1， 1， 0， 1） 第三組的計算時間最少，其次是第二組，最慢的是第一組。 第 九 章 templateclass T void JST::GenerateAns(int *x, int amp。k) { Node *ans1=ans。 k=0。 while(ans1j0) { k++。 ans1=ans1parent。 } ans1=ans。 for(int i=k1。 i=0。 i) { x[i]=ans1j。 ans1=ans1parent。 } } 0 1 2 3 4 p={3,8,6,4,5} total=26 U=7 d={1,2,3,4,4} 最優(yōu)解值 =19 t={1,1,2,2,1} 最 優(yōu)解 X={1,2,4} (p,d,t)= (8,2,1) , (6,3,2) , (5,4,1) 1 2 3 4 5 7 8 9 11 12 17 18 22 14
試題試卷相關(guān)推薦
鄂ICP備17016276號-1