矩阵链最小乘法次数的上机报告
学号：913106840530 姓名：郑铜亚
一、 二、 三、
实验名称：
矩阵链相乘问题； 实验内容与要求：
用动态规划策略求矩阵链相乘的最小乘法次数及乘法方式； 代码浅析：
①定义矩阵链大小SIZE为6，以r[SIZE+1]存储各行大小及末尾矩阵列大小、c[SIZE][SIZE]作矩阵存储上三角求解的最小乘法次数结果，point[SIZE][SIZE]存储对应C(i,j)=min{C(I,k-1)+C(k,j)+ri*rk*rj}最小时的k值；//当然可以用一维数组存储上三角矩阵，此处为容易编程先不考虑空间优化；
②主体函数照搬书上，为适配C++语言将数组下标及循环上界分别修改为0/SIZE-d，另外用选择的思想设置临时变量temp与最小的C(i,j)进行交换，并同时设置point[i][j]=k，此时最后修改的k即是最小乘法的分割点；
③用递归调用的方法进行加括号打印，递归终点是对角线上的元素，此时为Mi；而任意上三角的c[i][j]=c[i][k-1]*c[k]c[j]，此时k即为point[i][j]；
附：为打印漂亮，附加添加’\\t’的函数，不过实际效果并不漂亮：
四、
测试用例：
①上机PPT上例子测试：
②分别调整M1-6的行大小来比较最终最小乘法次数的变化：
M1:?*500 M2:500*10 M3:10*300 M4:300*1000 M5:1000*100 M6:100*500
M1 最小乘法次数 乘法方式 1 10 100 1000 10000 458000 4560000 5500000 14500000 -1787967296(溢出) 最小乘法次数 603000 6010000 6300000 9000000 36000000? 最小乘法次数 570000 5700000 31500000 程序崩溃 程序崩溃 (((((M1M2)M3)M4)M5)M6) (((M1M2)((M3M4)M5))M6) ((M1M2)(((M3M4)M5)M6)) ((M1M2)(((M3M4)M5)M6)) ((M1M2)(((M3M4)M5)M6)) 乘法方式 (M1(((M2M3)M4)M5)M6)) (M1((M2((M3M4))M5))M6)) ((M1M2)(((M3M4)M5)M6)) ((M1M2)(((M3M4)M5)M6)) ((M1M2)(((M3M4)M5)M6)) 乘法方式 ((M1M2)(((M3M4)M5)M6)) ((M1M2)(((M3M4)M5)M6)) (M1(M2(M3(M4(M5M6))))) M1:300*? M2:?*10 M3:10*300 M4:300*1000 M5:1000*100 M6:100*500 M2 1 10 100 1000 10000 M3 1 10 100 1000 10000 M1:300*500 M2:500*? M3:?*300 M4:300*1000 M5:1000*100 M6:100*500 总结：由动态规划递推式可知，该算法为O(n^3)时间和O(n^2)空间的复杂度； 观察程序求取结果，可知在矩阵过大时乘法次数超过int所表示的2^31-1的上界而溢出，因此也无法给出正确的乘法方式；而在远超过其他矩阵数量级并不引起程序崩溃时，最小乘法次数有比较良好的线性性质，并且乘法方式不会改变；当n极小时有”洼地效应“，即乘法方式向最小维的矩阵倾斜，通常在多重括号的里面； ③对比自然矩阵链相乘与最小乘法次数的运行时间差异： //为防止溢出，采用[-5,+5]区间生成的随机数进行实验
M1:?*500 M2:500*10 M3:10*300 M4:300*1000 M5:1000*100 M6:100*500 M1 1 10 100 1000 M2 1 10 100 1000 M3 1 10 自然链乘/ms 0 1.5 15.6 自然链乘/ms 0 46.2 47.3 自然链乘/ms 46.0 46.8 最小乘法/ms 0 1.5 1.9 4.9 最小乘法/ms 0.2 2.0 2.1 3.1 最小乘法/ms 0.2 1.9 M1:300*? M2:?*10 M3:10*300 M4:300*1000 M5:1000*100 M6:100*500 M1:300*500 M2:500*? M3:?*300 M4:300*1000 M5:1000*100 M6:100*500 100 1000 54.1 10.7 由上述表格可以看出，自然链乘时，除非首部行数呈线性增长，运行时间呈线性增长，否则都以极小的常数进行增长；而按最小乘法次数提供的乘法方式运行时，通常可以相比自然链乘具有极大的时间优势，而且通常以低于线性增长的趋势增长。
关于矩阵链相乘最小乘法次数的上机报告
