算法設(shè)計(jì)與分析第08章(編輯修改稿)
2025-07-13 12:32 本頁面
【文章內(nèi)容簡介】 { for(i=0。in。i++)coutx[i] 。//輸出一個(gè)可行解 coutendl。 } else NQueens(k+1,n,x)。//深度優(yōu)先進(jìn)入下一層 } } } void NQueens(int n,int *x) { NQueens(0,n,x)。 } 時(shí)間分析 可通過計(jì)算得到這 5次試驗(yàn)中實(shí)際需要生成的結(jié)點(diǎn)數(shù)的平均值為 1625。 8皇后問題狀態(tài)空間樹的結(jié)點(diǎn)總數(shù)是： 因此 ， 需要實(shí)際生成的結(jié)點(diǎn)數(shù)目大約占總結(jié)點(diǎn)數(shù)的 %。 ? ?? ????70jj0i109601)i8(1 子集和數(shù) 問題描述 已知 n個(gè)不同正數(shù) wi， 0?i?n1， 的集合 ， 求該集合的所有滿足條件的子集 ， 使得每個(gè)子集中的正數(shù)之和等于另一個(gè)給定的正數(shù) M。 例 8－ 2 設(shè)有 n=4個(gè)正數(shù)的集合 W={w0,w1,w2,w3}=(11,13,24,7)和整數(shù) M=31， 求 W的所有滿足條件的子集 ， 使得子集中的正數(shù)之和等于 M。 回溯法求解 解結(jié)構(gòu)形式 ：可變長度元組和固定長度元組 。 可變長度元組 （ x0,? ,xk?1,xk） ， 0?kn。 元組的每個(gè)分量的取值可以是元素值 ， 也可以是選入子集的正數(shù)的下標(biāo) 。 例如： （ 11， 13， 7） 或者 （ 0， 1， 2） 固定長度 n元組 （ x0,x1,? ,xn?1） ， xi?{0,1}, 0?in。xi=0， 表示 wi未選入子集 ， xi=1， 表示 wi入選子集 。 例如 ： （ x0,x1,x2,x3） =（ 1,1,0,1) W={w0,w1,w2,w3}=(11,13,24,7)， M=31 W={w0,w1,w2,w3}=(11,13,24,7)， M=31 可變長度元組的解空間樹 W={w0,w1,w2,w3}=(11,13,24,7)， M=31 固定長度 n元組 （ x0,x1,? ,xn?1） ， xi?{0,1}, 0?in。xi=0， 表示 wi未選入子集 ， xi=1， 表示 wi入選子集 。 例如 ： （ x0,x1,x2,x3） =（ 1,1,0,1) 稱這種從 n個(gè)元素的集合中找出滿足某些性質(zhì)的子集的狀態(tài)空間樹為 子集樹 。 子集樹有 2n個(gè)解狀態(tài) ， 遍歷子集樹的時(shí)間為 Ω(2n)。 固定長度 n元組 （ x0,x1,? ,xn?1） ， 表示的子集和數(shù)問題 的 約束函數(shù)： Bk(x0,x1,? ,xk) 為 true， 當(dāng)且僅當(dāng) ? ????????????1k0i1k0ikii1nkiiii Mwxw Mwxw 且 子集和數(shù)算法 【 程序 8－ 5】 子集和數(shù)的回溯算法 void SumOfSub (float s,int k,float r,int* x,float m,float* w) { x[k]=1。 if (s+w[k]==m) { //得到一個(gè)可行解 for (int j=0。j=k。j++) coutx[j] 39。 39。 //輸出一個(gè)解 coutendl。 } elseif (s+w[k]+w[k+1]=m) SumOfSub(s+w[k],k+1,rw[k],x,m,w)。 //搜索左子樹 if ((s+rw[k]=m)amp。amp。(s+w[k+1]=m)) //∑wi*xi+ 剩余部分?jǐn)?shù)值之和（ wk=0除外） { x[k]=0。 SumOfSub(s,k+1,rw[k],x,m,w)。 //搜索右子樹 } } void SumOfSub (int* x,int n,float m,float* w) { float r=0。//沒處理元素的數(shù)值之和 for(int i=0。in。i++) r=r+w[i]。//計(jì)算 if(r=m amp。amp。 w[0]=m) SumOfSub(0,0,r,x,m,w)。 } 1w[]nikri????1w[]nikri????1 w [ ]nikri??? ?W={w0,w1,w2,w3}=(11,13,24,7)， M=31 例 8－ 3 設(shè)有 n=6個(gè)正數(shù)的集合 W=(5,10,12,13,15,18)和整數(shù)M=30， 求 W的所有元素之和為 M的子集 。 圖的著色 問題描述 已知無向圖 G=(V,E)和 m種不同的顏色 ， 如果只允許使用這 m種顏色對圖 G的結(jié)點(diǎn)著色 ， 每個(gè)結(jié)點(diǎn)著一種顏色 。 問是否存在一種著色方案 ， 使得圖中任意相鄰的兩個(gè)結(jié)點(diǎn)都有不同的顏色 。 這就是 m著色判定問題 （ mcolorability decision problem） 回溯法求解 設(shè)無向圖 G=(V,E)采用如下定義的鄰接矩陣 a表示： 解
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1