第15章動態規劃 · 《算法導論》答案

# 一、綜述動態規劃是通過組合子問題的解而解決整個問題的。動態規劃適用于子問題不是獨立的情況，也就是各子問題的包含公共的子子問題。動態規劃對每個子問題只求解一次，將其結果保存在一張表中。動態規劃通常用于最優化問題。動態規劃的設計步驟：a.描述最優解的結構b.遞歸定義最優解的值c.按自底向上的方式計算最優觖的值d.由計算出的結構構造一個最優解 # 二、代碼 ### 15.1裝配線調度 ~~~ #include <iostream> using namespace std; #define I 2 #define J 6 int a[I+1][J+1], t[I+1][J+1], e[I+1], x[I+1], n = J;//輸入 int f[I+1][J+1], l[I+1][J+1],rf,rl; //輸出 //書上的偽代碼 void Fastest_Way() { //初始化 f[1][1] = e[1] + a[1][1]; f[2][1] = e[2] + a[2][1]; int j; for(j = 2; j <= n; j++) { //根據公式15.6計算 if(f[1][j-1] + a[1][j] <= f[2][j-1] + t[2][j-1] + a[1][j]) { //記錄計算結果 f[1][j] = f[1][j-1] + a[1][j]; l[1][j] = 1; } else { //記錄計算結果 f[1][j] = f[2][j-1] + t[2][j-1] + a[1][j]; l[1][j] = 2; } //根據公式15.7計算 if(f[2][j-1] + a[2][j] <= f[1][j-1] + t[1][j-1] + a[2][j]) { //記錄計算結果 f[2][j] = f[2][j-1] + a[2][j]; l[2][j] = 2; } else { //記錄計算結果 f[2][j] = f[1][j-1] + t[1][j-1] + a[2][j]; l[2][j] = 1; } } //最后一個結果另外記錄 if(f[1][n] + x[1] <= f[2][n] + x[2]) { rf = f[1][n] + x[1]; rl = 1; } else { rf = f[2][n] + x[2]; rl = 2; } } //輸出 void Print_Stations() { cout<<"輸出裝配路線"<<endl; int i = rl, j; //從后向前輸出 cout<<"line "<<i<<" station "<<n<<endl; for(j = n; j > 1; j--) { //獲取記錄的結果 i = l[i][j]; cout<<"line "<<i<<" station "<<j-1<<endl; } } //練習 //15.1-1 void Print_Stations2(int i, int j) { cout<<"順序輸出裝配路線"<<endl; if(j != n) i = l[i][j+1]; //先輸出前面的 if(j > 1) Print_Stations2(i, j-1); //再輸出當前的 cout<<"line "<<i<<" station "<<j<<endl; } //輸入數據 void Input() { int i, j; cout<<"輸入在裝配站S(i,j)的裝配時間a(i,j)："<<endl; //7 9 3 4 8 4 8 5 6 4 5 7 for(i = 1; i <= I; i++) { for(j = 1; j <= J; j++) cin>>a[i][j]; } cout<<"輸入進入裝配線i的花費時間e(i)："<<endl; //2 4 for(i = 1; i <= I; i++) cin>>e[i]; cout<<"輸入從S(i,j)站移動S(i2,j+1)的花費時間t(i,j)："<<endl; //2 3 1 3 4 2 1 2 2 1 for(i = 1; i <= I; i++) { for(j = 1; j < J; j++) cin>>t[i][j]; } cout<<"輸入從裝配線i離開的花費時間x(i)："<<endl; //3 2 for(i = 1; i <= I; i++) cin>>x[i]; } void Output() { int i, j; cout<<"輸出f[i][j]"<<endl; //f[i][j]表示第j個站是在裝配線i上完成的，完成1到j的裝配最少需要的時間 for(i = 1; i <= I; i++) { for(j = 1; j <= J; j++) cout<<f[i][j]<<' '; cout<<endl; } cout<<"輸出l[i][j]"<<endl; //l[i][j]表示使得f[i][j]最小時在哪個裝配線上裝配j-1 for(i = 2; i <= I; i++) { for(j = 1; j <= J; j++) cout<<l[i][j]<<' '; cout<<endl; } } int main() { Input(); Output(); Fastest_Way(); Print_Stations(); Print_Stations2(rl, J); return 0; } ~~~ ### 15.2矩陣鏈乘法 ~~~ #include <iostream> using namespace std; #define N 6 int m[N+1][N+1] = {0}, s[N+1][N+1] = {0}; void Matrix_Chain_Order(int *p) { int i, l, j, k, q; for(i = 1; i <= N; i++) m[i][i] = 0; for(l = 2; l <= N; l++) { for(i = 1; i <= N - l + 1; i++) { j = i + l - 1; m[i][j] = 0x7fffffff; for(k = i; k <= j - 1; k++) { q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]; if(q < m[i][j]) { m[i][j] = q; s[i][j] = k; } } } } } //15.2-2遞歸算法 int Matrix_Chain_Order(int *A, int start, int end) { //只有一個矩陣時，不需要括號 if(start == end) return 0; //如果已經有結果，直接使用結果 if(m[start][end]) return m[start][end]; int i, q; m[start][end] = 0x7fffffff; //P199，公式15.15 for(i = start; i < end; i++) { q = Matrix_Chain_Order(A, start, i) + Matrix_Chain_Order(A, i+1, end) + A[start-1] * A[i] * A[end]; //選最小值 if(q < m[start][end]) { m[start][end] = q; s[start][end] = i; } } return m[start][end]; } //輸出結果 void Print_Optimal_Parens(int *A, int i, int j) { if(i == j) cout<<'A'<<i; else { cout<<'('; Print_Optimal_Parens(A, i, s[i][j]); Print_Optimal_Parens(A, s[i][j]+1, j); cout<<")"; } } int main() { int A[N+1] = {5, 10, 3, 12, 5, 50, 6}; int A2[N+1] = {30, 35, 15, 5, 10, 20, 25}; Matrix_Chain_Order(A, 1, N); Print_Optimal_Parens(A, 1, N); return 0; } ~~~ ### 15.3動態規劃基礎 ~~~ #include <iostream> using namespace std; #define N 6 int m[N+1][N+1] = {0}, s[N+1][N+1] = {0}; //重疊子問題 int Recursive_Matrix_Chain(int *p, int i, int j) { //只有一個矩陣時，不需要括號 if(i == j) return 0; //如果已經有結果，直接使用結果 if(m[i][j]) return m[i][j]; int k, q; m[i][j] = 0x7fffffff; //P199，公式15.15 for(k = i; k < j; k++) { q = Recursive_Matrix_Chain(p, i, k) + Recursive_Matrix_Chain(p, k+1, j) + p[i-1] * p[k] * p[j]; //選最小值 if(q < m[i][j]) { m[i][j] = q; s[i][j] = k; } } return m[i][j]; } //做備忘錄 int Lookup_Chain(int *p, int i, int j) { int k, q; if(m[i][j] < 0x7fffffff) return m[i][j]; if(i == j) m[i][j] = 0; else { for(k = i; k < j; k++) { q = Lookup_Chain(p, i, k) + Lookup_Chain(p, k+1, j) + p[i-1]*p[k]*p[j]; if(q < m[i][j]) { m[i][j] = q; s[i][j] = k; } } } return m[i][j]; } int Medorized_Matrix_Chain(int *p) { int n = N, i, j; for(i = 1; i <= n; i++) { for(j = i; j <= n; j++) m[i][j] = 0x7fffffff; } return Lookup_Chain(p, 1, n); } //輸出結果 void Print_Optimal_Parens(int *p, int i, int j) { if(i == j) cout<<'A'<<i; else { cout<<'('; Print_Optimal_Parens(p, i, s[i][j]); Print_Optimal_Parens(p, s[i][j]+1, j); cout<<")"; } } int main() { int A[N+1] = {5, 10, 3, 12, 5, 50, 6}; int A2[N+1] = {30, 35, 15, 5, 10, 20, 25}; //重疊子問題 memset(s, 0, sizeof(s)); cout<<Recursive_Matrix_Chain(A, 1, N)<<endl; Print_Optimal_Parens(A, 1, N); cout<<endl; //做備忘錄 memset(s, 0, sizeof(s)); cout<<Medorized_Matrix_Chain(A)<<endl; Print_Optimal_Parens(A, 1, N); cout<<endl; return 0; } ~~~ ### 15.4最長公共子序列 ~~~ #include <iostream> using namespace std; #define M 8 #define N 9 int b[M+1][N+1] = {0}, c[M+1][N+1] = {0}; int c2[2][M+1] = {0}; /****書上的偽代碼***********************/ void Lcs_Length(int *x, int *y) { int i, j; //初始化 for(i = 1; i <= M; i++) c[i][0] = 0; for(j = 1; j <= N; j++) c[0][j] = 0; //根據公式15.14計算 for(i = 1; i <= M; i++) { for(j = 1; j <= N; j++) { //記錄計算結果 if(x[i] == y[j]) { c[i][j] = c[i-1][j-1] + 1; b[i][j] = 2; } else { if(c[i-1][j] >= c[i][j-1]) { c[i][j] = c[i-1][j]; b[i][j] = 1; } else { c[i][j] = c[i][j-1]; b[i][j] = 3; } } } } } //輸出 void Print_Lcs(int *x, int i, int j) { if(i == 0 || j == 0) return; if(b[i][j] == 2) { Print_Lcs(x, i-1, j-1); cout<<x[i]<<' '; } else if(b[i][j] == 1) Print_Lcs(x, i-1, j); else Print_Lcs(x, i, j-1); } //15.4-2 不使用表b的情況下計算最LCS并輸出 void Lcs_Length2(int *x, int *y) { int i, j; //初始化 for(i = 1; i <= M; i++) c[i][0] = 0; for(j = 1; j <= N; j++) c[0][j] = 0; //求LCS的時間沒有什么區別，只要把與b有關的去掉就可以了 for(i = 1; i <= M; i++) { for(j = 1; j <= N; j++) { //第一種情況 if(x[i] == y[j]) c[i][j] = c[i-1][j-1] + 1; else { //第二種情況 if(c[i-1][j] >= c[i][j-1]) c[i][j] = c[i-1][j]; //第三種情況 else c[i][j] = c[i][j-1]; } } } } //區別在于輸出，根據計算反推出前一個數據，而不是通過查找獲得 void Print_Lcs2(int *x, int i, int j) { //遞歸到初始位置了 if(i == 0 || j == 0) return; //三種情況，剛好與Lcs_Length2中的三種情況相對應（不是按順序對應） //第二種情況 if(c[i][j] == c[i-1][j]) Print_Lcs2(x, i-1, j); //第三種情況 else if(c[i][j] == c[i][j-1]) Print_Lcs2(x, i, j-1); //第一種情況 else { //匹配位置 Print_Lcs2(x, i-1, j-1); cout<<x[i]<<' '; } } //15.4-3備忘錄版本，類似于遞歸，只是對做過的計算記錄下來，不重復計算 //每一次迭代是x[1..m]和y[1..n]的匹配 int Lcs_Length3(int *x, int *y, int m, int n) { //長度為0，肯定匹配為0 if(m == 0|| n == 0) return 0; //若已經計算，直接返回結果 if(c[m][n] != 0) return c[m][n]; //公式15.14的對應 if(x[m] == y[n]) c[m][n] = Lcs_Length3(x, y, m-1, n-1) + 1; else { int a = Lcs_Length3(x, y, m-1, n); int b = Lcs_Length3(x, y, m, n-1); c[m][n] = a > b ? a : b; } return c[m][n]; } //15.4-4(1)使用2*min(m,n)及O(1)的額外空間來計算LCS的長度 void Lcs_Length4(int *x, int *y) { int i, j; //c2是2*min(M,N)的矩陣，初始化 memset(c2, 0 ,sizeof(c2)); //類似于上文的循環，只是i%2代表當前行，(i-1)%2代表上一行，其余內容相似 for(i = 1; i <= N; i++) { for(j = 1; j <= M; j++) { if(y[i] == x[j]) c2[i%2][j] = c2[(i-1)%2][j-1] + 1; else { if(c2[(i-1)%2][j] >= c2[i%2][j-1]) c2[i%2][j] = c2[(i-1)%2][j]; else c2[i%2][j] = c2[i%2][j-1]; } } } //輸出結果 cout<<c2[N%2][M]<<endl; } void Lcs_Length5(int *x, int *y) { int i, j, temp = 0; memset(c2, 0 ,sizeof(c2)); for(i = 1; i <= N; i++) { for(j = 1; j <= M; j++) { if(y[i] == x[j]) c2[i%2][j] = c2[(i-1)%2][j-1] + 1; else { if(c2[(i-1)%2][j] >= c2[i%2][j-1]) c2[i%2][j] = c2[(i-1)%2][j]; else c2[i%2][j] = c2[i%2][j-1]; } } } cout<<c2[N%2][M]<<endl; } void Print() { int i, j; for(i = 1; i <= M; i++) { for(j = 1; j <= N; j++) cout<<c[i][j]<<' '; cout<<endl; } } int main() { int x[M+1] = {0,1,0,0,1,0,1,0,1}; int y[N+1] = {0,0,1,0,1,1,0,1,1,0}; Lcs_Length(x, y); // Print(); Print_Lcs(x, M, N); // Lcs_Length2(x, y); // Lcs_Length3(x, y, M, N); // Print(); // Print_Lcs2(x, M, N); // Lcs_Length4(x, y); return 0; } ~~~ ### 15.5最優二叉查找樹 ~~~ #include <iostream> using namespace std; #define N 7 double e[N+2][N+2] = {0};//期望 double w[N+2][N+2] = {0};//概率 int root[N+2][N+2] = {0};//記錄樹的根結點的位置 /*****調試過程中用于輸出中間信息***************************/ void PrintE() { int i, j; for(i = 1; i <= N+1; i++) { for(j = 1; j <= N+1; j++) cout<<e[i][j]<<' '; cout<<endl; } cout<<endl; } void PrintW() { int i, j; for(i = 1; i <= N+1; i++) { for(j = 1; j <= N+1; j++) cout<<w[i][j]<<' '; cout<<endl; } cout<<endl; } void PrintRoot() { int i, j; for(i = 1; i <= N+1; i++) { for(j = 1; j <= N+1; j++) cout<<root[i][j]<<' '; cout<<endl; } cout<<endl; } /****書上的偽代碼對應的程序****************************/ //構造最做樹 void Optimal_Bst(double * p, double *q, int n) { int i, j, r ,l; double t; //初始化。當j=i-1時，只有一個虛擬鍵d|i-1 for(i = 1; i <= n+1; i++) { e[i][i-1] = q[i-1]; w[i][i-1] = q[i-1]; } //公式15.19 for(l = 1; l <= n; l++) { for(i = 1; i <= n-l+1; i++) { j = i+l-1; e[i][j] = 0x7fffffff; //公式15.20 w[i][j] = w[i][j-1] + p[j] + q[j]; for(r = i; r <= j; r++) { //公式15.19 t = e[i][r-1] + e[r+1][j] + w[i][j]; //取最小值 if(t < e[i][j]) { e[i][j] = t; //記錄根結點 root[i][j] = r; } } } } } /****練習**********************/ //15.5-1輸出最優二叉查找樹 void Construct_Optimal_Best(int start, int end) { //找到根結點 int r = root[start][end]; //如果左子樹是葉子 if(r-1 < start) cout<<'d'<<r-1<<" is k"<<r<<"'s left child"<<endl; //如果左子樹不是葉子 else { cout<<'k'<<root[start][r-1]<<" is k"<<r<<"'s left child"<<endl; //對左子樹遞歸使用Construct_Optimal_Best Construct_Optimal_Best(start, r-1); } //如果右子樹是葉子 if(end < r+1) cout<<'d'<<end<<" is k"<<r<<"'s right child"<<endl; //如果右子樹不是葉子 else { cout<<'k'<<root[r+1][end]<<" is k"<<r<<"'s right child"<<endl; //對右子樹遞歸使用Construct_Optimal_Best Construct_Optimal_Best(r+1, end); } } int main() { int n = N; // double p[N+1] = {0, 0.15, 0.10, 0.05, 0.10, 0.20}; // double q[N+1] = {0.05, 0.10, 0.05, 0.05, 0.05, 0.10}; double p[N+1] = {0, 0.04, 0.06, 0.08, 0.02, 0.10, 0.12, 0.14}; double q[N+1] = {0.06, 0.06, 0.06, 0.06, 0.05, 0.05, 0.05}; Optimal_Bst(p, q, n); // PrintE(); // PrintW(); // PrintRoot(); cout<<'k'<<root[1][N]<<" is root"<<endl; Construct_Optimal_Best(1, N); return 0; } ~~~ # 三、練習 ### 15.1裝配線調度 ### 15.1-1 ~~~ //15.1-1 void Print_Stations2(int i, int j) { cout<<"順序輸出裝配路線"<<endl; if(j != n) i = l[i][j+1]; //先輸出前面的 if(j > 1) Print_Stations2(i, j-1); //再輸出當前的 cout<<"line "<<i<<" station "<<j<<endl; } ~~~ ### 15.1-4 不使用l數組來記錄，輸出時根據類似L4-L13的比較來計算出前一個station的數據 ### 15.2矩陣鏈乘法 ### 15.2-1 算法：類似于15.3的做備忘錄運行結果：((A1A2)((A3A4)(A5A6))) ### 15.2-2 ~~~ //15.2-2遞歸算法 int Matrix_Chain_Order(int *A, int start, int end) { //只有一個矩陣時，不需要括號 if(start == end) return 0; //如果已經有結果，直接使用結果 if(m[start][end]) return m[start][end]; int i, q; m[start][end] = 0x7fffffff; //P199，公式15.15 for(i = start; i < end; i++) { q = Matrix_Chain_Order(A, start, i) + Matrix_Chain_Order(A, i+1, end) + A[start-1] * A[i] * A[end]; //選最小值 if(q < m[start][end]) { m[start][end] = q; s[start][end] = i; } } return m[start][end]; } ~~~ ### 15.3動態規劃基礎 ### 15.3-1 枚舉的時間的復雜度是O(4^n)/(n^(3/2)) RECURSIVE-MATRIX-CHAIN的時間復雜度是O(n*3^(n-1)) 顯然后者更有效 ### 15.3-3 解釋見1樓 ~~~ #include <iostream> using namespace std; #define N 6 int m[N+1][N+1] = {0}, s[N+1][N+1] = {0}; //15.2-2遞歸算法 int Matrix_Chain_Order(int *A, int start, int end) { //只有一個矩陣時，不需要括號 if(start == end) return 0; //如果已經有結果，直接使用結果 if(m[start][end]) return m[start][end]; int i, q; m[start][end] = -1; //P199，公式15.15 for(i = start; i < end; i++) { q = Matrix_Chain_Order(A, start, i) + Matrix_Chain_Order(A, i+1, end) + A[start-1] * A[i] * A[end]; //選最小值 if(q > m[start][end]) { m[start][end] = q; s[start][end] = i; } } return m[start][end]; } //輸出結果 void Print_Optimal_Parens(int *A, int i, int j) { if(i == j) cout<<'A'<<i; else { cout<<'('; Print_Optimal_Parens(A, i, s[i][j]); Print_Optimal_Parens(A, s[i][j]+1, j); cout<<")"; } } int main() { int A[N+1] = {5, 10, 3, 12, 5, 50, 6}; int A2[N+1] = {30, 35, 15, 5, 10, 20, 25}; Matrix_Chain_Order(A, 1, N); Print_Optimal_Parens(A, 1, N); return 0; } ~~~ ### ?15.4最長公共子序列 ### 15.4-1 1 0 0 1 1 0 ### 15.4-2 ~~~ //15.4-2 不使用表b的情況下計算最LCS并輸出 void Lcs_Length2(int *x, int *y) { int i, j; //初始化 for(i = 1; i <= M; i++) c[i][0] = 0; for(j = 1; j <= N; j++) c[0][j] = 0; //求LCS的時間沒有什么區別，只要把與b有關的去掉就可以了 for(i = 1; i <= M; i++) { for(j = 1; j <= N; j++) { //第一種情況 if(x[i] == y[j]) c[i][j] = c[i-1][j-1] + 1; else { //第二種情況 if(c[i-1][j] >= c[i][j-1]) c[i][j] = c[i-1][j]; //第三種情況 else c[i][j] = c[i][j-1]; } } } } //區別在于輸出，根據計算反推出前一個數據，而不是通過查找獲得 void Print_Lcs2(int *x, int i, int j) { //遞歸到初始位置了 if(i == 0 || j == 0) return; //三種情況，剛好與Lcs_Length2中的三種情況相對應（不是按順序對應） //第二種情況 if(c[i][j] == c[i-1][j]) Print_Lcs2(x, i-1, j); //第三種情況 else if(c[i][j] == c[i][j-1]) Print_Lcs2(x, i, j-1); //第一種情況 else { //匹配位置 Print_Lcs2(x, i-1, j-1); cout<<x[i]<<' '; } } ~~~ ### 15.4-3 ~~~ //15.4-3備忘錄版本，類似于遞歸，只是對做過的計算記錄下來，不重復計算 //每一次迭代是x[1..m]和y[1..n]的匹配 int Lcs_Length3(int *x, int *y, int m, int n) { //長度為0，肯定匹配為0 if(m == 0|| n == 0) return 0; //若已經計算，直接返回結果 if(c[m][n] != 0) return c[m][n]; //公式15.14的對應 if(x[m] == y[n]) c[m][n] = Lcs_Length3(x, y, m-1, n-1) + 1; else { int a = Lcs_Length3(x, y, m-1, n); int b = Lcs_Length3(x, y, m, n-1); c[m][n] = a > b ? a : b; } return c[m][n]; } ~~~ ### 15.4-4 （1）使用2*min(m,n)及O(1)的額外空間來計算LCS的長度因為這里只需要求長度，而不需要求序列，可以只存儲需要的內容。每一次的計算c[i][j]只與c[i-1][j]、c[i][j-1]、c[i-1][j-1]有關，所以只保留第i行和第i-1行 ~~~ //15.4-4(1)使用2*min(m,n)及O(1)的額外空間來計算LCS的長度 void Lcs_Length4(int *x, int *y) { int i, j; //c2是2*min(M,N)的矩陣，初始化 memset(c2, 0 ,sizeof(c2)); //類似于上文的循環，只是i%2代表當前行，(i-1)%2代表上一行，其余內容相似 for(i = 1; i <= N; i++) { for(j = 1; j <= M; j++) { if(y[i] == x[j]) c2[i%2][j] = c2[(i-1)%2][j-1] + 1; else { if(c2[(i-1)%2][j] >= c2[i%2][j-1]) c2[i%2][j] = c2[(i-1)%2][j]; else c2[i%2][j] = c2[i%2][j-1]; } } } //輸出結果 cout<<c2[N%2][M]<<endl; } ~~~ （2）使用min(m,n)項以及O(1)空間 ~~~ //15.4-4(2)使用min(m,n)及O(1)的額外空間來計算LCS的長度 void Lcs_Length4(int *x, int *y) { int i, j; //c2是min(M,N)的矩陣，初始化 memset(c2, 0 ,sizeof(c2)); //類似于上文的循環，只是i%2代表當前行，(i-1)%2代表上一行，其余內容相似 int t1 = 0, t2; for(i = 1; i <= N; i++) { t2 = c[j]; for(j = 1; j <= M; j++) { if(y[i] == x[j]) c2[j] = t1 + 1; else c2[j] = max(c2[j], c2[j-1]); t1 = t2; } } //輸出結果 cout<<c2[M]<<endl; } ~~~ ### 15.4-5 ~~~ #include <iostream> #include <string> using namespace std; #define N 10 int c[N+1] = {0};//c[i]表示A[1..i]的最長遞增子序列 int pre[N+1];//pre[i]表示若要得到A[1..i]的最長遞增子序列，i的前一個是哪個 //求最長遞增子序列 void Length(int *A) { int i, j; //A[i] = max{A[j]+1} if A[j]>A[i] and j<i for(i = 1; i <= N; i++) { //初始化 c[i] = 0; pre[i] = 0; for(j = 0; j < i; j++) { if(A[i] > A[j]) { if(c[j] + 1 > c[i]) { c[i] = c[j]+1; pre[i] = j; } } } } cout<<c[N]<<endl; } //若要輸出A[1..n]中的最長單調子序列，先輸出A[1..pre[n]]中的最長單調子序列 void Print(int *A, int n) { if(pre[n]) Print(A, pre[n]); cout<<A[n]<<' '; } int main() { //因為從第開始記數，所以數組中的第一個數不算，只是占一個位置 // int A[N+1] = {0,1,2,3,4,5,6,7,8,9,10}; int A[N+1] = {0,11,2,13,4,15,6,17,8,19,10}; Length(A); Print(A, N); return 0; } ~~~ ### 15.1最優二叉查找樹 ### 15.5-1 ~~~ //15.5-1輸出最優二叉查找樹 void Construct_Optimal_Best(int start, int end) { //找到根結點 int r = root[start][end]; //如果左子樹是葉子 if(r-1 < start) cout<<'d'<<r-1<<" is k"<<r<<"'s left child"<<endl; //如果左子樹不是葉子 else { cout<<'k'<<root[start][r-1]<<" is k"<<r<<"'s left child"<<endl; //對左子樹遞歸使用Construct_Optimal_Best Construct_Optimal_Best(start, r-1); } //如果右子樹是葉子 if(end < r+1) cout<<'d'<<end<<" is k"<<r<<"'s right child"<<endl; //如果右子樹不是葉子 else { cout<<'k'<<root[r+1][end]<<" is k"<<r<<"'s right child"<<endl; //對右子樹遞歸使用Construct_Optimal_Best Construct_Optimal_Best(r+1, end); } } ~~~ ### 15.5-2 k5 is root k2 is k5's left child k1 is k2's left child d0 is k1's left child d1 is k1's right child k3 is k2's right child d2 is k3's left child k4 is k3's right child d3 is k4's left child d4 is k4's right child k6 is k5's right child d5 is k6's left child k7 is k6's right child d6 is k7's left child d7 is k7's right child ### 15.5-4 ~~~ //15.5-4 void Optimal_Bst(double * p, double *q, int n) { int i, j, r ,l; double t; //初始化。當j=i-1時，只有一個虛擬鍵d|i-1 for(i = 1; i <= n+1; i++) { e[i][i-1] = q[i-1]; w[i][i-1] = q[i-1]; } //公式15.19 for(l = 1; l <= n; l++) { for(i = 1; i <= n-l+1; i++) { j = i+l-1; e[i][j] = 0x7fffffff; //公式15.20 w[i][j] = w[i][j-1] + p[j] + q[j]; //root[i,j-1] <= root[i,j] <= root[i+1,j] for(r = root[i][j-1]; r <= root[i+1][j]; r++) { //公式15.19 t = e[i][r-1] + e[r+1][j] + w[i][j]; //取最小值 if(t < e[i][j]) { e[i][j] = t; //記錄根結點 root[i][j] = r; } } } } } ~~~ # 四、思考題 ### 15-1 雙調歐幾里德旅行商問題見[算法導論-15-1-雙調歐幾里得旅行商問題](http://blog.csdn.net/mishifangxiangdefeng/article/details/7918983) ### 15-2 整齊打印見[算法導論-15-2-整齊打印](http://blog.csdn.net/mishifangxiangdefeng/article/details/7921947) ### 15-3 編輯距離見[算法導論-15-3-編輯距離](http://blog.csdn.net/mishifangxiangdefeng/article/details/7925025) ### 15-4 計劃一個公司聚會見[算法導論-15-4-計劃一個公司聚會](http://blog.csdn.net/mishifangxiangdefeng/article/details/7930830) ### 15-6 在棋盤上的移動見[算法導論-15-6-在棋盤上移動](http://blog.csdn.net/mishifangxiangdefeng/article/details/7931438) ### 15-7 達到最高效益的調度見[算法導論-15-7-達到最高效益的調度](http://blog.csdn.net/mishifangxiangdefeng/article/details/7932349)