矩阵链乘法算法矩阵链乘法算法|算法设计与分

MATRIX-CHAIN-ORDER (p) 1. nlength[p]-1 2. for i ← 1 to n 3. do m [i, i] ← 0 4. for l ← 2 to n// l is the chain length 5. do for i ← 1 to n-l + 1 6. do j ← i+ l -1 7. m[i, j] ←∞ 8. for k← i to j-1 9. do q← m [i, k] + m [k + 1, j] + pi-1 pk pj 10. If q < m [i, j] 11. then m [i, j] ← q 12. s [i, j] ← k 13. return m and s.

我们将使用table来构建最佳解决方案。
步骤1：构建最佳解决方案：

PRINT-OPTIMAL-PARENS (s, i, j) 1. if i=j 2. then print "A" 3. else print "(" 4. PRINT-OPTIMAL-PARENS (s, i, s [i, j]) 5. PRINT-OPTIMAL-PARENS (s, s [i, j] + 1, j) 6. print ")"

分析：有三个嵌套循环。每个循环最多执行n次。

l, 长度, O（n）次迭代。
i, 开始, O（n）次迭代。
k, 分割点, O（n）次迭代

主体循环常数复杂度
总复杂度为：O（n3）
带有示例的算法问题：P [7、1、5、4、2}
解决方案：在这里, P是矩阵维的数组。
因此, 这里将有4个矩阵：

A17x1A21x5A35x4A44x2i.e.First Matrix A1 have dimension 7 x 1Second Matrix A2 have dimension 1 x 5Third Matrix A3 have dimension 5 x 4Fourth Matrix A4 have dimension 4 x 2Let say, From P = {7, 1, 5, 4, 2} - (Given)And P is the Positionp0 = 7, p1 =1, p2 = 5, p3 = 4, p4=2.Length of array P = number of elements in P∴length (p)= 5From step 3Follow the steps in Algorithm in SequenceAccording to Step 1 of Algorithm Matrix-Chain-Order

步骤1：

n ← length [p]-1Where n is the total number of elementsAnd length [p] = 5∴ n = 5 - 1 = 4n = 4 Now we construct two tables m and s.Table m has dimension [1.....n, 1.......n]Table s has dimension [1.....n-1, 2.......n]

文章图片

文章图片
现在, 根据算法的步骤2

for i ← 1 to nthis means: for i ← 1 to 4 (because n =4)fori=1m [i, i]=0m [1, 1]=0Similarly for i = 2, 3, 4m [2, 2] = m [3, 3] = m [4, 4] = 0i.e. fill all the diagonal entries "0" in the table mNow, l ← 2 to nl ← 2 to 4(because n =4 )

情况1：
1.当l-2

for (i ← 1 to n - l + 1)i ← 1 to 4 - 2 + 1i ← 1 to 3When i = 1doj ← i + l - 1j ← 1 + 2 - 1j ← 2i.e. j = 2Now, m [i, j] ← ∞ i.e. m [1, 2] ← ∞ Put ∞ in m [1, 2] tablefor k ← i to j-1k ← 1 to 2 - 1k ← 1 to 1k = 1Now q ← m [i, k] + m [k + 1, j] + pi-1 pk pjfor l = 2i = 1j =2k = 1q ← m [1, 1] + m [2, 2] + p0x p1x p2and m [1, 1] = 0for i ← 1 to 4∴ q ← 0 + 0 + 7 x 1 x 5q ← 35We have m [i, j] = m [1, 2] = ∞ Comparing q with m [1, 2]q < m [i, j]i.e. 35 < m [1, 2]35 < ∞True then, m [1, 2 ] ← 35(∴ m [i, j] ← q)s [1, 2] ← k and the value of k = 1s [1, 2 ] ← 1Insert "1" at dimension s [1, 2] in table s. And 35 at m [1, 2]

2.我仍然是2

L = 2i ← 1 to n - l + 1i ← 1 to 4 - 2 + 1i ← 1 to 3for i = 1 done beforeNow value of i becomes 2i = 2j ←i + l - 1j ←2 + 2 - 1j ←3j = 3m [i , j]← ∞i.e. m [2, 3] ← ∞ Initially insert ∞ at m [2, 3]Now, for k ← i to j - 1k ← 2 to 3 - 1k ← 2 to 2i.e. k =2Now, q ← m [i, k] + m [k + 1, j] + pi-1 pk pjFor l =2i = 2j = 3k = 2q ← m [2, 2] + m [3, 3] + p1x p2 x p3q ← 0 + 0 + 1 x 5 x 4q ← 20Compare q with m [i , j ]If q < m [i, j] i.e. 20 < m [2, 3]20 < ∞TrueThen m [i, j ] ← qm [2, 3 ] ← 20and s [2, 3] ← k and k = 2s [2, 3] ← 2

3.现在我变成了3

i = 3l = 2j ← i + l - 1j ← 3 + 2 - 1j ← 4j = 4Now, m [i, j ] ← ∞m [3, 4 ] ← ∞Insert ∞ at m [3, 4] for k ← i to j - 1k ← 3 to 4 - 1k ← 3 to 3 i.e. k = 3Now, q ← m [i, k] + m [k + 1, j] + pi-1 pk pji = 3l = 2j = 4k = 3q ← m [3, 3] + m [4, 4] + p2x p3 x p4q ← 0 + 0 + 5 x 2 x 4q40Compare q with m [i, j]If q < m [i, j]40 < m [3, 4]40 < ∞ TrueThen, m [i, j] ← qm [3, 4] ← 40and s [3, 4] ← ks [3, 4] ← 3

情况2：l变成3

L = 3for i = 1 to n - l + 1i = 1 to 4 - 3 + 1i = 1 to 2When i = 1 j ← i + l - 1 j ← 1 + 3 - 1j ← 3 j = 3Now, m [i, j]← ∞m [1, 3]←∞for k ← i to j - 1k ← 1 to 3 - 1k ← 1 to 2

现在, 我们比较k = 1和k = 2的值。两个中的最小值将分别放在m [i, j]或s [i, j]中。

文章图片
现在从上面

Value of q become minimum for k=1∴ m [i, j] ← qm [1, 3] ← 48Also m [i, j] > qi.e. 48 < ∞∴ m [i , j] ← qm [i, j] ← 48and s [i, j] ← ki.e. m [1, 3] ← 48s [1, 3] ←1Now i become 2 i = 2l = 3then j ← i + l -1j ←2 + 3 - 1j ← 4j = 4 so m [i, j] ← ∞m [2, 4] ← ∞Insert initially ∞ at m [2, 4]for k← i to j-1k← 2 to 4 - 1k← 2 to 3

在这里, 还要找到两个值k = 2和k = 3的最小值m [i, j]

文章图片

But 28 < ∞So m [i, j] ← qAnd q← 28m [2, 4]← 28ands [2, 4]← 3i.e. It means in s table at s [2, 4] insert 3 and at m [2, 4] insert 28.

情况3：l变为4

L = 4For i ← 1 to n-l + 1i ← 1 to 4 - 4 + 1i ← 1i = 1 do j← i + l - 1j ← 1 + 4 - 1j ← 4j = 4Now m [i, j]←∞m [1, 4] ←∞for k← i to j -1k ← 1 to 4 - 1k← 1 to 3When k = 1q←m [i, k] + m [k + 1, j] + pi-1 pk pjq← m [1, 1] + m [2, 4] + p0xp4x p1q ← 0 + 28 + 7 x 2 x 1q← 42Compare q and m [i, j]m [i, j] was ∞i.e. m [1, 4] if q < m [1, 4]42< ∞True Then m [i, j] ← q m [1, 4] ← 42and s [1, 4]1 ? k =1When k = 2 L = 4, i=1, j = 4q ← m [i, k] + m [k + 1, j] + pi-1 pk pjq ← m [1, 2] + m [3, 4] + p0 xp2 xp4q ← 35 + 40 + 7 x 5 x 2q← 145Compare q and m [i, j]Now m [i, j]i.e. m [1, 4] contains 42.So if q < m [1, 4]But 145 less than or not equal to m [1, 4]So 145 less than or not equal to 42.So no change occurs.When k = 3 l = 4 i = 1 j = 4q←m [i, k] + m [k + 1, j] + pi-1 pk pjq ← m [1, 3] + m [4, 4] + p0 xp3 x p4q ← 48 + 0 + 7 x 4 x 2q← 114Again q less than or not equal to m [i, j] i.e. 114 less than or not equal to m [1, 4]114 less than or not equal to 42

因此不会发生任何变化。因此m [1, 4]的值保持为42。s [1, 4]的值= 1
【矩阵链乘法算法】现在, 我们将仅使用s表来获得最佳解决方案。