ম্যাট্রিক্স চেইন মালটিপ্লিকেশন (Matrix Chain Multiplication)

আমাদের কিছু ম্যাট্রিক্স দেয়া থাকবে।আমাদেরকে বের করতে হবে, এমন কোন অর্ডার এ ম্যাট্রিক্সগুলিকে গুন করলে তাদের cost মিনিমাম হবে।
ধরি আমাদের ২ টি ম্যাট্রিক্স দেয়া আছে A এবং B.
এখন A = [ P x Q ] ; এখানে P হল সারি (row), Q হল কলাম (column)
B = [ Q x R ]
এখন A*B করার পরে আমরা যে নতুন ম্যাট্রিক্স পাবো, তার ডাইমেনশন হবে = P x R
এখন আমাদের সবসময় লক্ষ্য রাখতে হবে যে ২ টি ম্যাট্রিক্স এর গুনের জন্য অবশ্যই প্রথম ম্যাট্রিক্স এর কলাম এবং দ্বিতীয় ম্যাট্রিক্স এর সারি সমান হতে হবে। এবং এক্ষেত্রে তাদের মাঝে গুনের জন্য টোটাল মালটিপ্লিকেশন লাগবে ঃ P*Q*R; [ ১ম ম্যাট্রিক্স এর সারি * ১ম ম্যাট্রিক্স এর কলাম * ২য় ম্যাট্রিক্স এর কলাম ]।
অর্থাৎ, cost = P*Q*R.

এবং আমাদের কাজ হচ্ছে একাধিক ম্যাট্রিক্স এভাবে লিনিয়ারলি গুন করা যাতে তাদের cost মিনিমাম হয়।
এখানে মূল ব্যাপার হল, আমরা যেভাবেই মালটিপ্লাই করিনা কেন, ফাইনাল রেজাল্ট সবসময় একই আসবে। অর্থাৎ গুন করার ক্ষেত্রে অর্ডার কোন প্রভাব ফেলেনা। তবে একেক অর্ডার এর জন্য একেকরকম cost আসবে। আমাদের কাজ হবে এমন অর্ডার বের করা যাতে cost মিনিমাম হয়।

ধরি, A [10 x 100 ] , B [ 100 x 5 ] , C [ 5 x 50 ], এই তিনটি ম্যাট্রিক্স। এখন আমরা ২ ভাবে এদের গুন করতে পারি।

• ( A * B ) * C
• A * ( B * C )

এখন ( A * B ) * C এর ক্ষেত্রে, প্রথমে,
( A * B ) এর জন্য cost, c1 = 10 * 100 * 5 = 5000; [ cost = P*Q*R ]
এখন ( A * B ) করার পরে আমরা যে নতুন ম্যাট্রিক্স পাবো, ধরি নতুন ম্যাট্রিক্সটি A' .
তাহলে A' এর ডাইমেনশন হবেঃ A' [ 10 x 5 ]; [ P x R ]
এখন, ( A' * C ) এর জন্য cost, c2 = 10 * 5 * 50 = 2500
সুতরাং, টোটাল cost, c = 5000 + 2500 = 7500

একইভাবে A * ( B * C ) এর জন্য টোটাল cost হবে 75000
কাজেই আমাদের জন্য প্রথম অর্ডার এ মালটিপ্লাই করলে cost মিনিমাম হবে।

অ্যালগরিদম (Algorithm)

আমরা আমাদের MCM (Matrix Chain Multiplication) বের করার জন্য যে ম্যাট্রিক্সগুলি দেয়া থাকবে, সেগুলি থেকে আমরা তাদের ডাইমেনশনকে একটু মডিফাই করে একটি অ্যারেতে সেভ রাখবো এমন ভাবে যাতে, প্রতিটির ইনডেক্স এ তাদের সারির (row) মানগুলি থাকবে। উদাহরন দিলে ব্যাপারটি পরিষ্কার হবে।
ধরি, আমাদের ৬ টি ম্যাট্রিক্স দেয়া আছে এভাবেঃ

A1 [ 30 x 35 ]

A2 [ 35 x 15 ]

A3 [ 15 x 5 ]

A4 [ 5 x 10 ]

A5 [ 10 x 20 ]

A6 [ 20 x 25 ]

এখন আমরা এদের সারি-কলামের মানগুলোকে একটি অ্যারে p তে এভাবে সাজায়ে রাখবোঃ

কাজেই আমরা যদি, A1 * A2 করতে চাই, তাহলে p অ্যারে থেকে আমরা p[0]*p[1]*p[2] করলেই মান পেয়ে যাবো।
তাহলে আমরা এখন একটি ফর্মুলা দাঁড়া করাতে পারি এভাবেঃ

m[i,j] = i হতে j পর্যন্ত ম্যাট্রিক্স গুন করতে মিনিমাম মালটিপ্লিকেশন।
তাহলে আমরা লিখতে পারিঃ

m[ i,j ] = { 0 if , i == j, else
                min { m[ i,k ] + m[ k+1,j ] + p[ k-1 ] * p[ k ] * p[ j ]  }; [k = 1 to j-1]

আমরা এই ফর্মুলা অনুযায়ী আমাদের MCM table জেনারেট করবো।

টেবিল জেনারেট (MCM table generate)

যেহেতু আমাদের ৬ টি ম্যাট্রিক্স, তাই আমরা 6 x 6 সাইজ এর একটি ২-ডি অ্যারে নিবো। এখন আমরা প্রতিবার, length 1 to 6 পর্যন্ত ম্যাট্রিক্স মালটিপ্লিকেশন এর অর্ডার বের করবো।
length = 1 হলে, m[i,j] = m[i,i] = m[j,j] = 0; m[i,j] হল, m ২-ডি অ্যারের i,j ইনডেক্স।

তাহলে, আমাদের টেবিল দেখতে এরকম হবে। এখানে আমরা cost গুলিকে হিসাব করবো।

length = 2 হলে,
m[1,2] = m[1,1] + m[2,2] + p[0]*p[1]*p[2] = 0+0+30*35*15 = 15750
m[2,3] = m[2,2] + m[3,3] + p[1]*p[2]*p[3] = 0+0+35*15*5 = 2625
m[3,4] = m[3,3] + m[4,4] + p[2]*p[3]*p[4] = 0+0+15*5*10 = 750

m[4.5] = m[4,4] + m[5,5] + p[3]*p[4]*p[5] = 0+0+5*10*20 = 1000

m[5,6] = m[5,5] + m[6,6] + p[4]*p[5]*p[6] = 0+0+10*20*25 = 5000

length = 3;
m[1,3] = m[1,1] + m[2,3] + p[0]*p[1]*p[3] = 0+2625+30*35*5 = 7875; k = 1
               m[1,2] + m[3,3] + p[0]*p[2]*p[3] = 15750+0+30*15*5 = 18000; k = 2
এখানে, ৩ দৈর্ঘ্যের জন্য, একবার (A1*A2)*A3, আরেকবার A1*(A2*A3) হিসাবে করে এদের মাঝে মিনিমামটি নিতে হবে। কাজেই m[1,3] = min (7875,18000) = 7875.
lenght = 3 এর জন্য আমরা k এর মান 1,2 ধরবো। এখন এভাবে length = 3 এর জন্য সকল ভ্যালু বসালে আমরা পাবোঃ

এখন length = 4 এর জন্য, k = 1,2,3 ধরে হবেঃ
m[1,4] = m[1,1] + m[2,4] + p[0]*p[1]*p[4] = 14875; k = 1
               m[1,2] + m[3,4] + p[0]*p[2]*p[4] = 21000; k = 2
               m[1,3] + m[4,4] + p[0]*p[3]*p[4] = 9375; k = 3
m[1,4] = min (14875,21000,9375) = 9375

এভাবে বাকি মান বসালে আমরা পাইঃ

length = 5;
m[1,5] = m[1,1] + m[2,5] + p[0]*p[1]*p[5] = 28125

               m[1,2] + m[3,5] + p[0]*p[2]*p[5] = 27250 

               m[1,3] + m[4,5] + p[0]*p[3]*p[5] = 11875; k = 3

               m[1,4] + m[5,5] + p[0]*p[4]*p[5] = 15375
m[1,5] = 11875, so-->

lenght = 6 -->

অর্থাৎ আমাদের ম্যাট্রিক্স মালটিপ্লিকেশন এর জন্য মিনিমাম cost = 15125. এখন আমরা যদি অর্ডার বের করতে চাই, যে কিভাবে আসলে আমরা মাল্টিপ্লিকেশনটি করলাম, এজন্য আমাদের আরো একটি 6x6 সাইজ এর অ্যারে লাগবে। এখানে আমরা প্রতিবার k এর কোন মানের জন্য মিনিমাম ভ্যালুটি নিচ্ছি, সেই k এর মান সেভ করে রাখবো।
যেমন আমরা length = 2 এর সময়, k = 1,2,3,4,5 পর্যন্ত নিয়েছিলাম। সেই অনুযায়ী মিনিমাম সাজালেঃ

আমরা এই অ্যারের নাম দিলাম s, এখানে আমরা k - partition এর নাম্বারগুলি সেভ রাখবো।
length = 3 এর জন্য, আমরা m[1,3] তে যেই মিনিমাম ভ্যালু রেখেছিলাম, সেটি ছিল k = 1 এর ভ্যালু। আমরা এরকম কিছু একটি পেয়েছিলাম-->

m[1,3] = m[1,1] + m[2,3] + p[0]*p[1]*p[3] = 0+2625+30*35*5 = 7875; k = 1
               m[1,2] + m[3,3] + p[0]*p[2]*p[3] = 15750+0+30*15*5 = 18000; k = 2

এখানে মিনিমাম ভ্যালু এর জন্য k = 1, কাজেই আমরা s[1,3] = 1 রাখবো। এভাবে length = 3,4,5,6 এর জন্য সাজালে আমাদের বাকি ঘরগুলি সাজায়ে আমরা ফাইনালি এরকম একটি ম্যাট্রিক্স পাবোঃ

অর্ডার প্রিন্ট (Order print)

আমরা এখন আমাদের ম্যাট্রিক্স এর মাল্টিপ্লিকেশন এর অর্ডারটি প্রিন্ট করবো। আমাদের অর্ডার ফাইন্ডিং এর অ্যালগরিদম ঃ

	void Print_Optimal_Parens( int i, int j )
	{
	if( i == j )
	{
	cout << " A" << i ;
	return ;
	}
	else
	{
	cout << " ( ";
	Print_Optimal_Parens( i, path[ i ][ j ] );
	Print_Optimal_Parens( path[ i ][ j ] + 1, j );
	cout << " ) ";
	}
	}

view raw mcm_order.cpp hosted with ❤ by GitHub

এভাবে আমরা পাবোঃ ( (A1) (A2 A3) ) ( (A4 A5) (A6) )
অর্থাৎ, এই অর্ডারে মাল্টিপ্লিকেশন চালালে আমরা মিনিমাম cost, এক্ষেত্রে 15215 পাবো।
MCM code:

	//Sifat Siddiqi Shishir
	#include<bits/stdc++.h>
	using namespace std;
	#define MAX 9999
	#define INF 1e9
	int cost [ MAX ][ MAX ], path[ MAX ][ MAX ], mat[ MAX ], n ;
	void Matrix_Chain_Order( )
	{
	for( int l = 2; l <= n; l++ )
	{
	for( int i = 1; i <= n-l+1; i++ )
	{
	int j = i+l-1;
	cost[ i ][ j ] = INF;
	for( int k = i; k <= j-1; k++ )
	{
	int q = cost[ i ][ k ] + cost[ k+1 ][ j ] + mat[ i-1 ] * mat[ k ] * mat[ j ];
	if( q < cost[ i ][ j ] )
	{
	cost[ i ][ j ] = q;
	path[ i ][ j ] = k;
	}
	}
	}
	}
	}
	void Print_Optimal_Parens( int i, int j )
	{
	if( i == j )
	{
	cout << " M" << i ;
	return ;
	}
	else
	{
	cout << " ( ";
	Print_Optimal_Parens( i, path[ i ][ j ] );
	Print_Optimal_Parens( path[ i ][ j ] + 1, j );
	cout << " ) ";
	}
	}
	int main()
	{
	cin >> n;
	for( int i = 1; i <= n; i++ )
	{
	cout << "Dimension for matrix no " << i << ": ?? X ?? " << endl ;
	cin >> mat [ i-1 ] >> mat [ i ] ;
	}
	Matrix_Chain_Order( );
	cout << "Minimum number of multiplication : " << cost[ 1 ][ n ] << endl ;
	Print_Optimal_Parens( 1, n );
	return 0;
	}

view raw mcm_full.cpp hosted with ❤ by GitHub

প্র্যাকটিস প্রব্লেম (Practice Problems)

• Uva 348: Optimal Array Multiplication Sequence
• Poj 2246: Matrix Chain Multiplication