演算法作業4

tags: 演算法

1. Show, by means of a counterexample, that the following “greedy” strategy does not always determine an optimal way to cut rods. Define the density of a rod of length i to be pi / i, that is, its value per inch. The greedy strategy for a rod of length n cuts off a first piece of length i, where 1 ≤ i ≤ n, having maximum density. It then continues by applying the greedy strategy to the remaining piece of length n-i.

   Answer:
   給定一個n=3且p[3]={2,0,3}的價目表，分別代表n=1~3的時候的售價。依照greedy strategy來解決此題的話，n=1的時候

   $p_i/i$有最大值2/1=2，因此依照此方法會將n=3的rod切成長度1與長度2的組合，這樣的收益會是2+0=2，但如果完全不切，長度n=3的rod收益是3，大於依照greedy strategy所得到的結果，因此greedy strategy在這裡不適用。

2. Consider a modification of the rod-cutting problem in which, in addition to a price pi for each rod, each cut incurs a fixed cost of c. The revenue associated with a solution is now the sum of the prices of the pieces minus the costs of making the cuts. Give a dynamic-programming algorithm to solve this modified problem.

   Answer:
   以下為改動過後的rod-cutting problem的程式碼
   初始值:

   $R_i=p_i$
   遞回式:
   $R_n=\underset{1\le i\le n}{\underbrace{max}}(p_i+R_{n-i}+c)$ (
   $R_i$在程式碼當中以Revenue[i]表示)
   解:
   $R_n$
   ​​​​input: n , p[]//p為價目表
   ​​​​global variable: c
   ​​​​
   ​​​​Rod-Cutting(p[],n){
   ​​​​    Revenue[n+1]={0};//建立一個長度n+1的陣列，0~n
   ​​​​    Revenue[0]=0;//長度0沒有收益
   ​​​​    
   ​​​​    for i = 1:n
   ​​​​        Revenue[i]=p[i];
   ​​​​        for j = 1:i-1 //原本跑到i，但j=i相當於沒砍，所以不用收錢
   ​​​​            q=p[j]+Revenue[i-j]+c;//每砍一刀都要收c塊錢
   ​​​​            if q>Revenue[i]
   ​​​​                Revenue[i]=q;
   ​​​​    return Revenue[n]
   ​​​​}
   

3. Modify MEMORIZED-CUT-ROD to return not only the value but the actual solution, too.

   Answer:
   多開一個陣列s[]來記錄切rod的位置，s[i]代表長度i的rod切在s[i]的位置的時候會有最佳解，s[i]=i代表不用切
   以下是程式碼

   ​​​​input: n, p[]
   ​​​​global variable: s[n] //長度n的陣列
   ​​​​
   ​​​​Rod-Cutting(p[],n){
   ​​​​    Revenue[n+1]={0};//建立一個長度n+1的陣列
   ​​​​    Revenue[0]=0;
   ​​​​    
   ​​​​    for i = 1:n
   ​​​​        Revenue[i]=p[i];
   ​​​​        s[i]=i;
   ​​​​        for j = 1:i
   ​​​​            q=p[j]+Revenue[i-j];
   ​​​​            if q>Revenue[i]
   ​​​​                Revenue[i]=q;
   ​​​​                s[i]=j;
   ​​​​    //做完這些回圈後，s[]裡就包含了所有長度需要切的地方
   ​​​​    return Revenue[n];
   ​​​​}
   

4. Find an optimal parenthesization of a matrix-chain product whose sequence of dimensions is《5, 10, 3, 12, 5, 50, 6》.

   Answer:
   題目給了7個dimensions，也就是說有6個矩陣，假設這些矩陣叫做

   $A_0{A}_1{A}_2{A}_3{A}_4{A}_5$
   依據下面程式碼可以求得這六個矩陣相乘cost最少的方式
   最少的cost為2010
   相乘的方式為
   $((A_0{A}_1)((A_2{A}_3)(A_4{A}_5)))$
   ​​​​#include <iostream>
   
   ​​​​using namespace std;
   
   ​​​​const int Size=7;
   ​​​​int s[Size-2][Size-1];
   
   ​​​​inline int Matrix_Chain(int* a) {
   ​    int m[Size][Size] = { 0 };
   ​    for (int i = 0; i < Size; i++)
   ​	    m[i][i] = 0;
   ​    
   ​​​​    int q;
   ​    for (int len = 2; len < Size; len++) {
   ​	for (int i = 0; i < Size - len; i++) {
   ​		int j = i + len - 1;
   ​		m[i][j] = 100000000;
   ​		for (int k = i; k <= j; k++) {
   ​			q = m[i][k] + m[k + 1][j] + a[i] * a[k + 1] * a[j + 1];
   ​			if (q < m[i][j]) {
   ​				m[i][j] = q;
   ​				s[i][j] = k;
   ​			}
   ​		}
   ​	    }
   ​    }
   ​    return m[0][Size - 2];
   ​​​​}
   
   ​​​​inline void Print_Answer(int i,int j) {
   ​    if (i == j)
   ​    {
   ​	    cout << "A" << i;
   ​    }
   ​    else
   ​    {
   ​	    cout << "(";
   ​	    Print_Answer(i, s[i][j]);
   ​	    Print_Answer(s[i][j] + 1, j);
   ​	    cout << ")";
   ​    }
   ​​​​}
   
   ​​​​int main(void) {
   ​
   ​    int a[Size] = { 5, 10, 3, 12, 5, 50 ,6 };
   
   ​    cout << Matrix_Chain(a) << endl;
   ​    Print_Answer(0, Size - 2); cout << endl;
   
   ​    return 0;
   ​​​​}
   ​​​​
   

5. A mathematical expression is given without parentheses. Design an algorithm to parenthesize the expression such that the value of the expression is maximized. For example, consider the expression: 2+7⋅5. There are two ways to parenthesize the expression 2+(7⋅5) = 37 and (2+7)⋅5 = 45, so in this case, your algorithm should output the second expression. Here, you may assume the given expressions contain only 3 kinds of binary operators ‘+’, ‘−’, and ‘⋅’.

   Answer:
   以下使用DP的方式解決此題，此題的optimal structure比較不同，因為一個算式的最大值不一定是由它最大的兩個子算式組合而成，其它也有可能，例如兩個很小的負數相乘可能會比兩個很大的正整數相乘更大。使用到的表格都有以註解方式寫在以下pseudo code當中。

   輸入:E[n]，長度為n的算式，E[i]可能為一個整數或者一個算符，長度都是1，例如E[i]=100，E[i]的長度也是1。
   初始值:max[i][i]=E[i],min[i][i]=E[i]，表示算式當中第i個數字到第i個數字的最大值跟最小值即為該數字。
   遞迴式:

   $ma{x}_{ij}=\underset{i\le k\le j}{\underbrace{max}}(ma{x}_{i(k-1)}(op)ma{x}_{(k+1)j},ma{x}_{i(k-1)}(op)mi{n}_{(k+1)j},mi{n}_{i(k-1)}(op)ma{x}_{(k+1)j},mi{n}_{i(k-1)}(op)mi{n}_{(k+1)j})$
   
   $mi{n}_{ij}=\underset{i\le k\le j}{\underbrace{min}}(ma{x}_{i(k-1)}(op)ma{x}_{(k+1)j},ma{x}_{i(k-1)}(op)mi{n}_{(k+1)j},mi{n}_{i(k-1)}(op)ma{x}_{(k+1)j},mi{n}_{i(k-1)}(op)mi{n}_{(k+1)j})$
   
   $op$代表算符，可能為
   $+、-、\ast$
   解答:解答以recursive function的方式呼叫並列印。
   ​​​​input: E[n]//長度為n的算式，假設所有輸入的數字都大於等於0
   ​​​​
   ​​​​global variable:
   ​​​​    max[n][n]//max[i][j]代表E[i]到E[j]的最大值
   ​​​​    min[n][n]//min[i][j]代表E[i]到E[j]的最小值
   ​​​​    Max_p[n][n]//Max_p[i][j]代表E[i]到E[j]最大值的割點
   ​​​​    Min_p[n][n]//Min_p[i][j]代表E[i]到E[j]最小值的割點
   ​​​​    max_c[n][n]
   ​​​​    min_c[n][n]
   ​​​​    //max_c[i][j]=00代表max[i][j]是由max[i][Max_p[i][j]-1]+max[Max_p[i][j]+1][j]組成
   ​​​​    //max_c[i][j]=01代表max[i][j]是由max[i][Max_p[i][j]-1]+min[Max_p[i][j]+1][j]組成
   ​​​​    //max_c[i][j]=10代表max[i][j]是由min[i][Max_p[i][j]-1]+max[Max_p[i][j]+1][j]組成
   ​​​​    //max_c[i][j]=11代表max[i][j]是由min[i][Max_p[i][j]-1]+min[Max_p[i][j]+1][j]組成
   ​​​​
   ​​​​Biggest_E(E[],n){
   ​​​​    //initialize
   ​​​​    for i = 1:n
   ​​​​        if E[i]!='*' && E[i]!='+' && E[i]!='-'
   ​​​​            max[i][i]=E[i];
   ​​​​            min[i][i]=E[i];
   ​​​​        
   ​​​​    for Len = 1:n
   ​​​​        for i = 1:n-len
   ​​​​            j=i+len;
   ​​​​            Max=-INF;//負無窮大
   ​​​​            Min=INF;
   ​​​​            if j>n
   ​​​​                break;
   ​​​​            max[i][j]=Max;
   ​​​​            min[i][j]=Min;
   ​​​​            for k = i:j
   ​​​​                n1=0,n2=0,n3=0,n4=0;
   ​​​​                if E[k]=='*'
   ​​​​                    n1=max[i][k-1]*max[k+1][j];
   ​​​​                    n2=max[i][k-1]*min[k+1][j];
   ​​​​                    n3=min[i][k-1]*max[k+1][j];
   ​​​​                    n4=min[i][k-1]*min[k+1][j];
   ​​​​                else if E[k]=='+'
   ​​​​                    n1=max[i][k-1]+max[k+1][j];
   ​​​​                    n2=max[i][k-1]+min[k+1][j];
   ​​​​                    n3=min[i][k-1]+max[k+1][j];
   ​​​​                    n4=min[i][k-1]+min[k+1][j];
   ​​​​                else if E[k]=='-'
   ​​​​                    n1=max[i][k-1]-max[k+1][j];
   ​​​​                    n2=max[i][k-1]-min[k+1][j];
   ​​​​                    n3=min[i][k-1]-max[k+1][j];
   ​​​​                    n4=min[i][k-1]-min[k+1][j];
   ​​​​                Max,codeMax=max(n1,n2,n3,n4);//codeMax is 00 if Max==n1依此類推
   ​​​​                Min,codeMin=max(n1,n2,n3,n4);
   ​​​​                if Max>max[i][j]
   ​​​​                    max[i][j]=Max;
   ​​​​                    Max_p[i][j]=k;
   ​​​​                    max_c[i][j]=codeMax;
   ​​​​                if Min<min[i][j]
   ​​​​                    min[i][j]=Min;
   ​​​​                    Min_p[i][j]=k;
   ​​​​                    min_c[i][j]=codeMax;
   ​​​​                
   ​​​​}
   ​​​​
   ​​​​Print_parenthesis(E[],head,tail,type){
   ​​​​    if head==tail
   ​​​​        print E[head];
   ​​​​        
   ​​​​    print "(";
   ​​​​    if type == "max"
   ​​​​        if max_c[head][tail]==00
   ​​​​            Print_parenthesis(E[],head,Max_p[head][tail]-1,"max");
   ​​​​            print E[Max_p[head][tail]];//把切割點的算符印出來
   ​​​​            Print_parenthesis(E[],Max_p[head][tail]+1,"max");
   ​​​​        else if max_c[head][tail]==01
   ​​​​            Print_parenthesis(E[],head,Max_p[head][tail]-1,"max");
   ​​​​            print E[Max_p[head][tail]];
   ​​​​            Print_parenthesis(E[],Max_p[head][tail]+1,"min");
   ​​​​        else if max_c[head][tail]==10
   ​​​​            Print_parenthesis(E[],head,Max_p[head][tail]-1,"min");
   ​​​​            print E[Max_p[head][tail]];
   ​​​​            Print_parenthesis(E[],Max_p[head][tail]+1,"max");
   ​​​​        else if max_c[head][tail]==11
   ​​​​            Print_parenthesis(E[],head,Max_p[head][tail]-1,"min");
   ​​​​            print E[Max_p[head][tail]];
   ​​​​            Print_parenthesis(E[],Max_p[head][tail]+1,"min");
   ​​​​    if type == "min"
   ​​​​        if min_c[head][tail]==00
   ​​​​            Print_parenthesis(E[],head,Min_p[head][tail]-1,"max");
   ​​​​            print E[Min_p[head][tail]];
   ​​​​            Print_parenthesis(E[],Min_p[head][tail]+1,"max");
   ​​​​        else if min_c[head][tail]==01
   ​​​​            Print_parenthesis(E[],head,Min_p[head][tail]-1,"max");
   ​​​​            print E[Min_p[head][tail]];
   ​​​​            Print_parenthesis(E[],Min_p[head][tail]+1,"min");
   ​​​​        else if min_c[head][tail]==10
   ​​​​            Print_parenthesis(E[],head,Min_p[head][tail]-1,"min");
   ​​​​            print E[Min_p[head][tail]];
   ​​​​            Print_parenthesis(E[],Min_p[head][tail]+1,"max");
   ​​​​        else if min_c[head][tail]==11
   ​​​​            Print_parenthesis(E[],head,Min_p[head][tail]-1,"min");
   ​​​​            print E[Min_p[head][tail]];
   ​​​​            Print_parenthesis(E[],Min_p[head][tail]+1,"min");
   ​​​​    print ")";
   ​​​​}
   ​​​​
   ​​​​//main function
   ​​​​main(){
   ​​​​    Biggest_E(E[],n);
   ​​​​    Print_parenthesis(E[],1,n,"max");
   ​​​​}
   ​​​​
   

6. Which is a more efficient way to determine the optimal number of multiplications in a matrix-chain multiplication problem: enumerating all the ways of parenthesizing the product and computing the number of multiplications for each, or running RECURSIVE-MATRIX-CHAIN? Justify your answer.

   ​​​​RECURSIVE-MATRIX-CHAIN(p, i, j)
   ​​​​    return 0 if i == j
   ​​​​    m[i][j] = ∞
   ​​​​    for k in i...j
   ​​​​        q = RECURSIVE-MATRIX-CHAIN(p, i, k) + RECURSIVE-MATRIX-CHAIN(p, k + 1, j) + p[i - 1] * p[k] * p[j]
   ​​​​        m[i][j] = q if q < m[i][j]
   ​​​​    return m[i][j]
   
   

   Answer:
   我認為兩種方式一樣沒有效率，第一種是將所有可能的運算順序都做一遍然後比較，時間複雜度會和catalan number一樣。第二種方式是使用上述的Recursive-Martrix-Chain，看起來雖然有用一個表格紀錄運算結果，類似DP的方式，但每次進行一個新的function call的時候，m[i][j]都需要被重新計算一次，而找m[i][j]的方式也是將所有能切割的可能都試過一次，這樣跟第一種方式沒有不同，也是每一次計算一種括號的方式就將它以下的所有子問題都重新解一遍，時間複雜度同樣也會和catalan number一樣。

   更新:Recurive method比較有效率

7. As stated, in dynamic programming we first solve the sub-problems and then choose which of them to use in an optimal solution to the problem. Professor Capulet claims that it is not always necessary to solve all the sub-problems in order to find an optimal solution. She suggests that an optimal solution to the matrix-chain multiplication problem can be found by always choosing the matrix Ak at which to split the sub-product

   $A_i{A}_{i+1}...A_j$ (by selecting k to minimize the quantity
   $p_{i-1}{p}_k{p}_j$) before solving the sub-problems. Find an instance of the matrix-chain multiplication problem for which this greedy approach yields a sub-optimal solution.

   Answer:
   假設有三個矩陣

   $A_0{A}_1{A}_2$，他們組成的dimensions是{5,10,3,4}，依照DP的解法，運算順序應該是
   $(A_0\ast A_1)\ast A_2$，但依照這個greedy approach的方法結果會是
   $A_0\ast (A_1\ast A_2)$。