矩阵链乘法算法

MATRIX-CHAIN-ORDER (p) 
 1. n   length[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次。

  1. l, 长度, O(n)次迭代。
  2. i, 开始, O(n)次迭代。
  3. k, 分割点, O(n)次迭代

主体循环常数复杂度

总复杂度为:O(n3)

带有示例的算法

问题:P [7、1、5、4、2}

解决方案:在这里, P是矩阵维的数组。

因此, 这里将有4个矩阵:

A17x1  A21x5  A35x4  A44x2
i.e.
First Matrix A1 have dimension 7 x 1
Second Matrix A2 have dimension 1 x 5
Third Matrix A3 have dimension 5 x 4
Fourth Matrix A4 have dimension 4 x 2

Let say, From P = {7, 1, 5, 4, 2} - (Given)
And P is the Position
p0 = 7, p1 =1, p2 = 5, p3 = 4, p4=2.
Length of array P = number of elements in P
∴length (p)= 5
From step 3
Follow the steps in Algorithm in Sequence
According to Step 1 of Algorithm Matrix-Chain-Order

步骤1:

n ← length [p]-1
	   Where n is the total number of elements
     And length [p] = 5
∴ n = 5 - 1 = 4
n = 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 n
this means: for i ← 1 to 4 (because n =4)
for  i=1
m [i, i]=0
m [1, 1]=0
Similarly for i = 2, 3, 4
m [2, 2] = m [3, 3] = m [4, 4] = 0
i.e. fill all the diagonal entries "0" in the table m
Now, l ← 2 to n
l ← 2 to 4    (because n =4 )

情况1:

1.当l-2

for (i ← 1 to n - l + 1)
	    i ← 1 to 4 - 2 + 1
	    i ← 1 to 3

When i = 1
  do   j ← i + l - 1
	         j ← 1 + 2 - 1
	         j ← 2
     i.e. j = 2
Now, m [i, j] ← ∞	 
	i.e. m [1, 2] ← ∞ 
Put ∞ in m [1, 2] table
	  for k ← i to j-1
	       k ← 1 to 2 - 1
	       k ← 1 to 1
            k = 1
Now q ← m [i, k] + m [k + 1, j] + pi-1 pk pj
			for l = 2
			     i = 1
			     j =2
			    k = 1
	    q ← m [1, 1] + m [2, 2] + p0x p1x p2
             and m [1, 1] = 0
		  for i ← 1 to 4
     ∴ q ← 0 + 0 + 7 x 1 x 5
	    q ← 35
We 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 = 1
		s [1, 2 ] ← 1
Insert "1" at dimension s [1, 2] in table s. And 35 at m [1, 2]

2.我仍然是2

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

3.现在我变成了3

i = 3
  l = 2
j ← i + l - 1
j ← 3 + 2 - 1
j ← 4
j = 4
Now, m [i, j ] ← ∞
          m [3, 4 ] ← ∞
Insert ∞ at m [3, 4] 
  for k ← i to j - 1
	       k ← 3 to 4 - 1
	       k ← 3 to 3
	i.e. k = 3
Now, q ← m [i, k] + m [k + 1, j] + pi-1 pk pj
i = 3
				l = 2
				j = 4
				k = 3
q ← m [3, 3] + m [4, 4] + p2  x p3 x p4
q ← 0 + 0 + 5 x 2 x 4
q   40
Compare q with m [i, j]
		If q < m [i, j]
		   40 < m [3, 4]
		   40 < ∞ 
		True
Then, m [i, j] ← q
	      m [3, 4] ← 40
and s [3, 4] ← k
	  s [3, 4] ← 3

情况2:l变成3

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

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

矩阵链乘法算法示例

现在从上面

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

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

矩阵链乘法算法示例
But 28 < 	∞
   So m [i, j] ← q
      And q  ← 28
  m [2, 4]  ← 28
  and   s [2, 4]  ← 3
i.e. It means in s table at s [2, 4] insert 3 and at m [2, 4] insert 28.

情况3:l变为4

L = 4
	   For i ← 1 to n-l + 1
		i ← 1 to 4 - 4 + 1
		i ← 1
		i = 1
	do j  ← i + l - 1
	     j ← 1 + 4 - 1
	     j ← 4
	    j = 4
Now m [i, j]  ←  ∞
        m [1, 4] ←  ∞
for k  ← i to j -1
     k ← 1 to 4 - 1
     k  ← 1 to 3
When k = 1
q  ←  m [i, k] + m [k + 1, j] + pi-1 pk pj                
q  ← m [1, 1] + m [2, 4] + p0xp4x p1
q ← 0 + 28 + 7 x 2 x 1
q  ← 42
Compare 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] ← 42
and s [1, 4]  1	? k =1
When k = 2
	L = 4, i=1, j = 4
q ← m [i, k] + m [k + 1, j] + pi-1 pk pj                
q ← m [1, 2] + m [3, 4] + p0 xp2 xp4
q ← 35 + 40 + 7 x 5 x 2
q  ← 145
Compare 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 = 4
q  ←  m [i, k] + m [k + 1, j] + pi-1 pk pj                
q ← m [1, 3] + m [4, 4] + p0 xp3 x p4
q ← 48 + 0 + 7 x 4 x 2
q  ← 114
Again 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表来获得最佳解决方案。

DAA算法的解释示例
微信公众号
手机浏览(小程序)
0
分享到:
没有账号? 忘记密码?