ضرب ماتریس‌ها

ماتریس‌ها به طور ساده، همانند آرایه‌های دوبعدی اند. یک ماتریس $n \times m$ یعنی ماتریسی که $n$ سطر و $m$ ستون دارد (تعداد سطر‌ها و ستون‌ها می‌تواند برابر باشد). برای ضرب کردن دو ماتریس، باید تعداد ستون‌های اولی با تعداد سطر‌های دومی برابر باشد. ضرب‌کردن یک ماتریس $n \times m$ در یک ماتریس $m \times p$ به اندازه‌ی $n \times m \times p$ هزینه (زمان) می‌برد و خروجی‌اش یک ماتریس $n \times p$ است.
اما اگر بیش از دو ماتریس داشته باشیم، این که به چه ترتیبی این ضرب‌ها را انجام بدهیم (یا چگونه بین ماتریس‌ها پرانتزگذاری کنیم) در هزینه‌ی نهایی تاثیر دارد (دقت کنید که جواب یکسان است، فقط هزینه‌ای که ما صرف می‌کنیم فرق می‌کند.)
برای مثال، فرض کنید، سه ماتریس به ابعاد (۲،۳) و (۳،۴) و (۴،۵) داشته باشیم. اگر ابتدا اولی و دومی و سپس نتیجه را با سومی ضرب کنیم، هزینه‌ی ما ۶۴ واحد می‌شود. اما اگر ابتدا دومی و سومی را ضرب کرده و سپس اولی را با نتیجه ضرب کنید، ۹۰ واحد باید هزینه کنید. $$ 2 \times 3 \times 4 + 2 \times 4 \times 5 = 64 $$ $$ 3 \times 4 \times 5 + 2 \times 3 \times 5 = 90 $$

فرض کنید ابعاد $k$ ماتریس به شما داده شده است. کمترین هزینه‌ی ضرب کردن این ماتریس‌ها در هم چقدر می‌شود؟ (دقت کنید که شما نمی‌توانید جای ماتریس‌ها را با هم عوض کنید، بلکه فقط می‌توانید ترتیب انجام شدن ضرب‌ها را انتخاب کنید.)

اگر کمی سوال را بررسی کنید، می‌توانید ببینید که تعداد حالت‌های مختلف انجام این پرانتز‌گذاری بسیار زیاد است. در واقع این مقدار برابر $(k-1)!$ است. اما در مجموع، برای حل بسیاری از این حالت‌های مختلف، باید مقادیر تکراری زیادی حساب کنیم.
همانطور که در ابتدا گفته شد، در این مسئله فقط باید مشخص کنیم که پرانتزگذاری بین ماتریس‌ها باید چگونه باشد. و اگر دقت کنید، در صورتی که تمام ماتریس‌های $i$ ام تا $j$ ام در یک پرانتز کلی قرار داشته باشند، فرقی نمی‌کند که چگونه عملیات ضرب را در این تکه انجام دهید، چون در هر صورت، ماتریس پایانی این مجموعه یکسان است (درنتیجه ابعاد آن نیز یکسان است). پس بهتر است این تکه را هم به بهترین روش (با کمترین هزینه) حل کنیم. این مسئله خود شبیه مسئله‌ی اصلی است با این تفاوت که دنباله‌ی ماتریس‌هایمان فقط ماتریس‌های $i$ ام تا $j$ ام اند.
با داشتن این ایده در ذهن بیایید به سراغ سوال اصلی برویم. می‌خواهیم سوال اصلی را به یک سری از زیر‌سوال‌هایی که در بالا تعریف کردیم، تبدیل کنیم. با کمی بررسی بیشتر، متوجه می‌شویم که اگر آخرین ضربی که باید انجام شود را تعیین کنیم، باید چیزی به این شکل باشد: $$ ( A_1, A_2, \dots , A_i ) \times ( A_{i+1}, A_{i+2} , \dots , A_k ) $$ که تکه‌ی اول و دوم آن را می‌توان با زیرمسئله‌هایی که در بالا تعریف کردیم حل کنیم. پس راه حل به دست آمده را می‌توان به زبان ریاضی به شکل زیر تعریف کرد: (فرض کنید اندازه‌ی بعد اول یا همان سطر‌های ماتریس اول تا $k$ ام را $a_1$ تا $a_k$ و بعد دوم یا ستون‌های ماتریس آخر را $a_{k+1}$ بنامیم. می‌دانیم که باید برای مثال اندازه‌ی بعد دوم ماتریس $i$ ام، برابر بعد اول ماتریس $i+1$ باشد، وگرنه ضرب ممکن نیست)
مقدار $d_{i,j}$ را برابر کمترین هزینه‌ی ضرب کردن ماتریس $i$ ام تا $j$ ام در نظر بگیرید. پس جواب مسأله برابر مقدار $d_{۱,k}$ است.
مقدار اولیه: $d_{i,i}$ برابر صفر است، چون هیچ نیاز به انجام هیچ ضربی نیست.
به روز رسانی: مقدار $d_{i,j}$ با شرط $j>i$ بسته به اینکه کدام ضرب در انتها انجام شود، به صورت روبرو تعریف می‌شود: $$ d_{i,j} = \min_{i \leq m < j}{\big( d_{i,m} + d_{m+1,j} + a_i \times a_{m+1} \times a_{j+1} )} $$ شبه کد (باید دقت کنید که ابتدا دسته‌های به طول ۱ را پر کنید، سپس طول ۲ و …) :

for i from 1 to k 
	d[i][i] = 0 


for len from 1 to k
	for i from 1 to k

		if i+len > k
			break
		j = i+len

		d[i][j] = inf 
		for m from i to j-1
			value = d[i][m] + d[m+1][j] + a[i] * a[m+1] * a[j+1] 
			d[i][j] = min( d[i][j] , value )

حافظه مورد نیاز از $O(n^2)$ است. و هر به روز رسانی نیز از $O(n)$ است. پس پیچیدگی زمانی از $O(n^3)$ است.

matrix_multiplication.cpp

#include <iostream>
using namespace std;
typedef pair<int, int> pii;
 
const int MAXK = 1000;
const int INF = 1<<30; // 2 ^ 30
 
pii inp[MAXK+10];
int a[MAXK+10];
int d[MAXK+10][MAXK+10];
 
int main() {
	ios::sync_with_stdio(false);
	int k;
	cin >> k;
	for(int i=0; i<k; i++)
		cin >> inp[i].first >> inp[i].second;
 
	for(int i=1; i<k; i++){
		if( inp[i].first != inp[i-1].second ){
			cout << "matrix sizes are not valid" << endl;
			return 0;
		}
		a[i] = inp[i].first;
	}
	a[0] = inp[0].first;
	a[k] = inp[k-1].second;
 
	for(int i=0; i<k; i++)
		d[i][i] = 0;
 
	for(int len=1; len<=k; len++)
		for(int i=0; i<k; i++){
			if( i+len >= k )
				break;
			int j = i+len;
 
			d[i][j] = INF;
			for(int m=i; m<j; m++)
				d[i][j] = min( d[i][j] , d[i][m] + d[m+1][j] + a[i] * a[m+1] * a[j+1] );
		}
 
	cout << d[0][k-1] << endl;
 
	return 0;
}

• MIXTURES