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