PB19030888 Zhang Shuheng
Experimental equipment and environment
One PC, Win11 enterprise operating system, gcc 9.1.0 compiler, Clion 2021.2.2 code editor, Excel drawing tool
Experimental content
1. Optimal scheme of matrix chain multiplication
2. All longest common subsequences
Experimental requirements
The code is limited to C/C + +. The root folder 80 Zhang Shuheng pb19030888 project1 is established. The experimental report, ex1 and ex2 experimental folders are established under the root folder. Three subfolders are established in each experimental folder: input folder: storing input data, src folder: source program, and output folder: output data.
Experimental steps and methods
Matrix chain multiplication
1. File input and output
Input / output stream with absolute path
string from = "C:\\Users\\ASUS\\Desktop\\AL\\ex1\\input\\1_1_input.txt"; string dest = "C:\\Users\\ASUS\\Desktop\\AL\\ex1\\output\\result.txt"; string time = "C:\\Users\\ASUS\\Desktop\\AL\\ex1\\output\\time.txt"; ifstream file_in; file_in.open(from); file_out.open(dest); time_out.open(time);
2. Matrix chain multiplication algorithm
The timer starts, the dynamic programming method solves the optimal solution of matrix chain multiplication, and the timer closes
chrono::steady_clock::time_point t1 = chrono::steady_clock::now();
for(int i = 1; i<= N; i++)
dp[i][i] = 0;
for (int len = 2; len <= N; len++) {
for (int i = 1; i <= N - len + 1; i++) {
int j = i + len - 1;
dp[i][j] = 9223372036854775807;
for (int k = i; k < j; k++) {
long long tmp = dp[i][k] + dp[k + 1][j] + nums[i-1] * nums[k] * nums[j];
if(tmp < dp[i][j]){
dp[i][j] = tmp;
s[i][j] = k;
}
}
}
}
chrono::steady_clock::time_point t2 = chrono::steady_clock::now();
3. Print the optimal solution of matrix chain multiplication
Print recursively
void print(int s[][150], int i, int j){
if(i == j)
file_out << "A" << i;
else{
file_out << "(";
print(s, i, s[i][j]);
print(s, s[i][j] + 1, j);
file_out << ")";
}
}
4. Print the running time and dynamic planning table when N=5, draw the time curve and analyze it
Longest common subsequence
1. File input and output
Input / output stream with absolute path
string from = "C:\\Users\\ASUS\\Desktop\\AL\\ex2\\input\\1_2_input.txt"; string time = "C:\\Users\\ASUS\\Desktop\\AL\\ex2\\output\\time.txt"; ifstream file_in; file_in.open(from); ofstream time_out; time_out.open(time);
2. Longest common subsequence algorithm
The timer starts, the dynamic programming method solves the longest common subsequence, and the timer closes
chrono::steady_clock::time_point t1 = chrono::steady_clock::now(); int length = lcs_length(m, n); chrono::steady_clock::time_point t2 = chrono::steady_clock::now();
int lcs_length(int m, int n){
c = vector<vector<int> >(m+1,vector<int>(n+1));
for(int i=0; i<m+1; ++i){
for(int j=0; j<n+1; ++j){
if (i == 0 || j == 0)
c[i][j] = 0;
else if(X[i-1] == Y[j-1])
c[i][j] = c[i-1][j-1] + 1;
else
c[i][j] = max(c[i-1][j], c[i][j-1]);
}
}
return c[m][n];
}
4. Print all longest common subsequences and their number (no repetition is allowed)
Use set < string > LCS; Save all the longest common subsequences, which are counted in a way that does not allow repetition
string str;
lcs_print(m, n, str);
ofstream file_out;
file_out.open("C:\\Users\\ASUS\\Desktop\\AL\\ex2\\output\\result_" + to_string(N) + ".txt");
file_out << "The number of LCSs is " << lcs.size() << endl;
set<string>::iterator it = lcs.begin();
for( ; it!=lcs.end(); it++)
file_out << *it << endl;
lcs.clear();
void lcs_print(int i, int j, string lcs_str){
while (i>0 && j>0){
if (X[i-1] == Y[j-1]){
lcs_str.push_back(X[i-1]);
--i;
--j;
}
else{
if (c[i-1][j] > c[i][j-1])
--i;
else if (c[i-1][j] < c[i][j-1])
--j;
else{
lcs_print(i-1, j, lcs_str);
lcs_print(i, j-1, lcs_str);
return;
}
}
}
reverse(lcs_str.begin(),lcs_str.end());
lcs.insert(lcs_str);
}
5. Print the running time, draw the time curve and analyze it
Analysis of experimental results
Matrix chain multiplication
Draw the time curve and fit it with the cubic function. The result basically conforms to the cubic function growth model, so the actual time complexity is approximately the same as the theoretical time complexity, which is $O(n^3)$
Longest common subsequence
Draw the time curve and fit it with the quadratic function. The result basically conforms to the quadratic function growth model. There is a slight deviation when N=25. It may be that this example is slightly simpler in judgment and calculation than other examples, but the error is within the acceptable range. Therefore, the actual time complexity is approximately the same as the theoretical time complexity, which is $O(n^2)$
Experimental summary
Through this experiment, I basically mastered the general idea of dynamic programming algorithm to solve practical problems