最新算法設(shè)計與分析作業(yè)三-展示頁
2025-07-04 03:13本頁面
【正文】 }連乘的情況。每一種完全加括號的方式對應(yīng)于一個矩陣連乘積的計算次序，這決定著作乘積所需要的計算量。完全加括號的矩陣連乘積可遞歸地定義為： （1） 單個矩陣是完全加括號的； （2） 矩陣連乘積A是完全加括號的，則A可表示為2個完全加括號的矩陣連乘積B和C的乘積并加括號，即A=(BC)。這種計算次序可以用加括號的方式來確定。要算出這n個矩陣的連乘積A1A2…An。算法設(shè)計與分析實驗報告學(xué) 院 信息科學(xué)與技術(shù)學(xué)院 專業(yè)班級 軟件工程3班 學(xué) 號 20122668 姓 名 王建君 指導(dǎo)教師 尹治本 2014年10月 實驗四 矩陣相乘次序 問題提出用動態(tài)規(guī)劃算法解矩陣連乘問題。給定n個矩陣{A1,A2,…,An}，其中Ai與Ai+1是可乘的，i=1,2,…,n1。由于矩陣乘法滿足結(jié)合律，故計算矩陣的連乘積可以有許多不同的計算次序。若一個矩陣連乘積的計算次序完全確定，也就是說該連乘積已完全加括號，則可以依此次序反復(fù)調(diào)用2個矩陣相乘的標(biāo)準(zhǔn)算法計算出矩陣連乘積。 例如，矩陣連乘積A1A2A3A4有5種不同的完全加括號的方式：（A1（A2（A3A4））），（A1（（A2A3）A4）），（（A1A2）（A3A4）），（（A1（A2A3））A4），（（（A1A2）A3）A4）。若A是一個pq矩陣，B是一個qr矩陣，則計算其乘積C=AB的標(biāo)準(zhǔn)算法中，需要進(jìn)行pqr次數(shù)乘。設(shè)這三個矩陣的維數(shù)分別為10100，1005，550。第二種加括號方式的計算量時第一種方式計算量的10倍。于是，自然提出矩陣連乘積的最優(yōu)計算次序問題，即對于給定的相繼n個矩陣{A1,A2,…,An}（其中矩陣Ai的維數(shù)為pi1pi，i＝1,2,…,n），如何確定計算矩陣連乘積A1A2…An的計算次序（完全加括號方式），使得依此次序計算矩陣連乘積需要的數(shù)乘次數(shù)最少。本實驗的算法思路是： 1)計算最優(yōu)值算法MatrixChain()：建立兩張表（即程序中的**m和**s，利用二維指針存放），一張表存儲矩陣相乘的最小運算量，主對角線上的值為0，依次求2個矩陣、3個矩陣…、直到n個矩陣相乘的最小運算量，其中每次矩陣相乘的最小運算量都在上一次矩陣相乘的最小運算量的基礎(chǔ)上求得，最后一次求得的值即為n個矩陣相乘的最小運算量；另一張表存儲最優(yōu)斷開位置。分三種情況： （1）只有一個矩陣，則只需打印出A1； （2）有兩個矩陣，
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1