【正文】 =0。 ? int *p=new int[n+1]。 ? for(int i=0。i=n。i++) ? p[i]=0。 ? =p。 ? (1)。 ? delete[] p。 ? return 108 3. 算法效率 ? 圖 m可著色問題的解空間樹中內(nèi)結(jié)點(diǎn)個(gè)數(shù)是 。 ? 對于每一個(gè)內(nèi)結(jié)點(diǎn)，在最壞情況下，用 ok檢查當(dāng)前擴(kuò)展結(jié)點(diǎn)的每一個(gè)兒子所相應(yīng)的顏色可用性需耗時(shí) O(mn)。因此，回溯法總的時(shí)間耗費(fèi)是 ???10niim)()1/()1()(10nnnii nmOmmnmmnm ???????109 旅行售貨員問題 1. 算法描述 ? 解空間：排列樹 ? 開始時(shí) x=[1,2,...,n]，則相應(yīng)的排列樹由x[1:n]的所有排列構(gòu)成。 ABDH IN OGMFLJ KP QC E1324344 3244 2233 25 96 613243 062 01 045110 遞歸算法 ? 當(dāng) i=n時(shí)，當(dāng)前擴(kuò)展結(jié)點(diǎn)是排列樹的葉結(jié)點(diǎn)的父結(jié)點(diǎn)，此時(shí)檢查圖 G是否存在 一條從頂點(diǎn) x[n1]到頂點(diǎn) x[n]的邊 和一條從頂點(diǎn) x[n]到頂點(diǎn) 1的邊 ，如果兩條邊都存在，則找到一條回路。再判斷此回路的費(fèi)用是否優(yōu)于當(dāng)前最優(yōu)回路的費(fèi)用，是則更新當(dāng)前最優(yōu)值和最優(yōu)解。 ABDH IN OGMFLJ KP QC E1324344 3244 2233 25 96 6111 ? 當(dāng) in時(shí)，當(dāng)前擴(kuò)展結(jié)點(diǎn)位于排列樹的第 i1層。圖 G中存在從頂點(diǎn) x[i1]到 x[i]的邊時(shí)，檢查 x[1:i]的費(fèi)用是否小于當(dāng)前最優(yōu)值，是則進(jìn)入排列樹的第 i層，否則剪去相應(yīng)子樹。 ABDH IN OGMFLJ KP QC E1324344 3244 2233 25 96 6? templatetypename Type ? class Traveling ? { ? friend Type TSP(int **,int [],int,Type)。 ? private: ? void Backtrack(int i)。 ? int n。 //圖 G的頂點(diǎn)數(shù) ? int *x。 //當(dāng)前解 ? int *bestx。 //當(dāng)前最優(yōu)解 ? Type **a。 //圖 G的鄰接矩陣 ? Type cc。 //當(dāng)前費(fèi)用 ? Type bestc。 //當(dāng)前最優(yōu)值（費(fèi)用） ? Type NoEdge。 //無邊標(biāo)記，可用 INT_MAX ? }。 ? templatetypename Type ? void TravelingType::Backtrack(int i) ? { ? if(i==n) ? { ? if(a[x[n1]][x[n]]!=NoEdgeamp。amp。 a[x[n]][1]!=NoEdgeamp。amp。 ? (cc+a[x[n1]][x[n]]+a[x[n]][1]bestc ||bestc==NoEdge)) ? { ? for(int j=1。 j=n。 j++) ? bestx[j]=x[j]。 ? bestc=cc+a[x[n1]][x[n]]+a[x[n]][1]。 ? } ? } ? else ? { ? for(int j=i。 j=n。 j++) ? if(a[x[i1]][x[j]]!=NoEdgeamp。amp。(cc+a[x[i1]][x[j]]bestc||bestc==NoEdge)) ? { ? Swap(x[i],x[j])。 ? cc+=a[x[i1]][x[i]]。 ? Backtrack(i+1)。 ? cc=a[x[i1]][x[i]]。 ? Swap(x[i],x[j])。 ? } ? } ? } ? templatetypename Type ? Type TSP(Type **a,int v[],int n,Type NoEdge) ? { ? TravelingType Y。 ? //初始化 Y ? =new int[n+1]。 ? for(int i=1。 i=n。 i++) ? [i]=i。 ? =a。 ? =n。 ? =NoEdge。 ? =v。 ? =0。 ? =NoEdge。 ? //搜索 x[2:n]的全排列 ? (2)。 ? delete[] 。 ? return 。 ? } 116 2. 算法效率 ? 算法 backtrack在最壞情況下可能需要更新當(dāng)前最優(yōu)解 O((n1)!)次，每次更新 bestx需計(jì)算時(shí)間 O(n)，從而整個(gè)算法的計(jì)算時(shí)間復(fù)雜性為 O(n!)。 117 圓排列問題 1. 問題描述 ? 給定 n個(gè)大小不等的圓 c1,c2,…,c n，現(xiàn)要將這 n個(gè)圓排進(jìn)一個(gè)矩形框中，且要求各圓與矩形框的底邊相切。圓排列問題要求從 n個(gè)圓的所有排列中找出有最小長度的圓排列。 118 例： ? 當(dāng) n=3，且所給的 3個(gè)圓的半徑分別為 1,1,2時(shí)，這 3個(gè)圓的最小長度的圓排列如圖所示。其最小長度為 。 242 ?31 22242 ?119 2. 算法設(shè)計(jì) ? 解空間：排列樹 ? 本問題的難點(diǎn)： – 計(jì)算當(dāng)前所選擇的圓在當(dāng)前圓排列中圓心的橫坐標(biāo)（ Center）。 – 計(jì)算當(dāng)前圓排列的長度（ Compute）。 ? 數(shù)組 r表示當(dāng)前圓排列， r[i]為第 i個(gè)圓的半徑。 ? 數(shù)組 x記錄當(dāng)前圓排列中各圓的圓心橫坐標(biāo)。 ? 約定：在當(dāng)前圓排列中排在第一個(gè)圓的圓心的橫坐標(biāo)為 0. 120 ? class Circle ? { ? friend float CirclePerm(int,float*)。 ? private: ? float Center(int t)。 ? void Compute()。 ? void Backtrack(int t)。 ? float min。 //當(dāng)前最優(yōu)值 ? float *x。 //當(dāng)前圓排列圓心橫坐標(biāo) ? float *r。 //當(dāng)前圓排列 ? int n。 //待排列圓的個(gè)數(shù) ? }。 121 Center r [ t ] + r [ j ]][*][2 jrtrr [ t ] r [ j ]x [ j ]? ? ? ? ? ?jrtrjx *2?x [ 1 ]0122 float Circle::Center(int t) //計(jì)算當(dāng)前所選圓的圓心橫坐標(biāo) { float temp=0。 for(int j=1。jt。j++) { float valuex=x[j]+*sqrt(r[t]*r[j])。 //t與 j相切 if(valuextemp) temp=valuex。 } return temp。 } 123 Compute 123x [ 2 ] r [ 2 ] x [ 3 ] + r [ 3 ]void Circle::Compute() //計(jì)算當(dāng)前圓排列的長度 { float low=0。 float high=0。 for(int i=1。i=n。i++) { if(x[i]r[i]low) low=x[i]r[i]。 //最左端坐標(biāo) (0或負(fù)數(shù) ) if(x[i]+r[i]high) high=x[i]+r[i]。 //最右端坐標(biāo) } if(highlowmin) min=highlow。 } ? void Circle::Backtrack(int t) ? { ? if(tn) ? Compute()。 ? else ? for(int j=t。j=n。j++) ? { ? Swap(r[t],r[j])。 ? float centerx=Center(t)。 ? if(centerx+r[t]+r[1]min) //下界約束 ? { ? x[t]=centerx。 ? Backtrack(t+1)。 ? } ? Swap(r[t],r[j])。 ? } ? } 126 ? float CirclePerm(int n,float *a) ? { ? Circle X。 ? =n。 ? =a。 ? =FLT_MAX。 //cfloat中定義了 FLT_MAX（最大 float值） ? float *x=new float[n+1]。 ? =x。 ? (1)。 ? delete[] x。 ? return 。 ? } 127 3. 算法效率 ? 在最壞情況下可能需要計(jì)算 O(n!)次當(dāng)前圓排列長度，每次計(jì)算需 O(n)時(shí)間，從而整個(gè)算法的時(shí)間復(fù)雜度為 O((n+1)!)。 128 電路板排列問題 1. 問題描述 ? 將 n塊電路板以最佳排列方式插入帶有 n個(gè)插槽的機(jī)箱中， n塊電路板的不同排列方式對應(yīng)于不同的電路板插入方案。 ? 設(shè) B={1,2,...,n}是 n塊電路板，L={N1,N2,...,Nm}是 n塊電路板的 m個(gè)連接塊，其中每個(gè)連接塊 Ni是 B的一個(gè)子集，且 Ni中的電路板用同一根導(dǎo)線連接在一起。 129 例： ? 設(shè) n=8， m=5，給定的 n塊電路板及 m個(gè)連接塊如下： ? B={1,2,...,8}； L={N1,N2,...N5}； ? N1={4,5,6}。 N2={2,3}。 N3={1,3}。 N4={3,6}。 N5={7,8}。 2 1 3 4 5 6 7 81 2 3 4 5 6 7 8N2N3N4N1N5130 ? 設(shè) x表示 n塊電路板的排列，即在第 i個(gè)插槽中插入電路板。 ? x所確定的 電路板排列密度 density(x)定義為跨越相鄰電路板插槽的最大連線數(shù)。 2 1 3 4 5 6 7 81 2 3 4 5 6 7 8N2N3N4N1N5x 2 1 3 4 5 6 7 8 density(x)=2 131 問題： ? 在設(shè)計(jì)機(jī)箱時(shí)，插槽一側(cè)的布線間隙由電路板排列的密度所確定。因此電路板排列問題要求對于給定的電路板連接條件，確定電路板的最佳排列，使其具有最小密度。 132 2. 算法設(shè)計(jì) ? 用整型二維數(shù)組 B表示輸入。 B[i][j]的值為 1表示電路板 i在連接塊 Nj中。 ? total[j]是連接塊 Nj中的電路板數(shù)。 ? now[j]是電路板的部分排列 x[1:i]中所含 Nj中的電路板數(shù)。 0 0 1 0 0 0 1 0 0 0 0 1