矩阵链最小乘法次数的上机报告
矩阵链最小乘法次数的上机报告一、 实验名称：矩阵链相乘问题；二、 实验内容与要求：用动态规划策略求矩阵链相乘的最小乘法次数及乘法方式；三、 代码浅析：定义矩阵链大小SIZE为6，以rSIZE+1存储各行大小及末尾矩阵列大小、cSIZESIZE作矩阵存储上三角求解的最小乘法次数结果，pointSIZESIZE存储对应C(i,j)=minC(I,k-1)+C(k,j)+ri*rk*rj最小时的k值；/当然可以用一维数组存储上三角矩阵，此处为容易编程先不考虑空间优化；主体函数照搬书上，为适配C+语言将数组下标及循环上界分别修改为0/SIZE-d，另外用选择的思想设置临时变量temp与最小的C(i,j)进行交换，并同时设置pointij=k，此时最后修改的k即是最小乘法的分割点；用递归调用的方法进行加括号打印，递归终点是对角线上的元素，此时为Mi；而任意上三角的cij=cik-1*ckcj，此时k即为pointij；附：为打印漂亮，附加添加t的函数，不过实际效果并不漂亮：四、 测试用例：上机PPT上例子测试：分别调整M1-6的行大小来比较最终最小乘法次数的变化：M1:?*500 M2:500*10 M3:10*300 M4:300*1000 M5:1000*100 M6:100*500M1最小乘法次数乘法方式1458000(M1M2)M3)M4)M5)M6)104560000(M1M2)(M3M4)M5)M6)1005500000(M1M2)(M3M4)M5)M6)100014500000(M1M2)(M3M4)M5)M6)10000-1787967296(溢出)(M1M2)(M3M4)M5)M6)M1:300*? M2:?*10 M3:10*300 M4:300*1000 M5:1000*100 M6:100*500M2最小乘法次数乘法方式1603000(M1(M2M3)M4)M5)M6)106010000(M1(M2(M3M4)M5)M6)1006300000(M1M2)(M3M4)M5)M6)10009000000(M1M2)(M3M4)M5)M6)1000036000000?(M1M2)(M3M4)M5)M6)M1:300*500 M2:500*? M3:?*300 M4:300*1000 M5:1000*100 M6:100*500M3最小乘法次数乘法方式1570000(M1M2)(M3M4)M5)M6)105700000(M1M2)(M3M4)M5)M6)10031500000(M1(M2(M3(M4(M5M6)1000程序崩溃10000程序崩溃总结：由动态规划递推式可知，该算法为O(n3)时间和O(n2)空间的复杂度；观察程序求取结果，可知在矩阵过大时乘法次数超过int所表示的231-1的上界而溢出，因此也无法给出正确的乘法方式；而在远超过其他矩阵数量级并不引起程序崩溃时，最小乘法次数有比较良好的线性性质，并且乘法方式不会改变；当n极小时有”洼地效应“，即乘法方式向最小维的矩阵倾斜，通常在多重括号的里面；对比自然矩阵链相乘与最小乘法次数的运行时间差异：/为防止溢出，采用-5,+5区间生成的随机数进行实验M1:?*500 M2:500*10 M3:10*300 M4:300*1000 M5:1000*100 M6:100*500M1自然链乘/ms最小乘法/ms100101.51.510015.61.910004.9M1:300*? M2:?*10 M3:10*300 M4:300*1000 M5:1000*100 M6:100*500M2自然链乘/ms最小乘法/ms100.21046.22.010047.32.110003.1M1:300*500 M2:500*? M3:?*300 M4:300*1000 M5:1000*100 M6:100*500M3自然链乘/ms最小乘法/ms146.00.21046.81.910054.110.71000由上述表格可以看出，自然链乘时，除非首部行数呈线性增长，运行时间呈线性增长，否则都以极小的常数进行增长；而按最小乘法次数提供的乘法方式运行时，通常可以相比自然链乘具有极大的时间优势，而且通常以低于线性增长的趋势增长。
