الگوریتم ضرب زنجیری ماتریس ها

مساله ضرب زنجیری ماتریسها و پرانتزبندی بهینه آن یکی از مثالهای مشهور کاربرد برنامه نویسی پویا در حل مسائل بهینه سازی است.

فرض کنید قصد داریم حاصلضرب عبارت ماتریسی A3 x 7 x B7 x 8 x C8 x 4 را محاسبه کنیم. می دانیم که ضرب ماتریسها خاصیت شرکت پذیری دارند و ترتیب ضرب آنها مهم نیست. پرانتزبندی های مختلف ضرب ماتریس ها حالتهای مختلف محاسبه آن را به ما می دهند:

1: A x ( B x C )

2: ( A x B ) x C

در حالت اول ابتدا B در C ضرب شده و سپس حاصل آنها در A ضرب می شود، و در حالت دوم ابتدا A و B در هم ضرب شده و سپس نتیجه در C ضرب می شود. حال سوال این است که آیا این پرانتزبندی ها تفاوتی با هم دارند؟

ضرب ماتریس دلخواه MR x L در ماتریس دلخواه دیگری مانند NL x C به R x L x C عمل ضرب عددی نیاز دارد (چرا؟). با توجه به این موضوع، تعداد کل عملهای ضرب برای محاسبه حاصلضرب سه ماتریس فوق را در هر دو پرانتزبندی محاسبه می کنیم:

1: A x ( B x C ) : 7 x 8 x 4 + 3 x 7 x 4 = 308

در حالت اول ابتدا ماتریس B در C ضرب می شود. سپس ماتریس A و ماتریس حاصل از ضرب اول، با ابعاد ( ۴ , ۷ )، در هم ضرب می شوند. به همین ترتیب در مورد حالت دوم داریم:

2: ( A x B ) x C : 3 x 7 x 8 + 3 x 8 x 3 = 240

پس در پرانتزبندی به فرم دوم تعداد ضرب کمتری نیاز است.

ثابت شده است که تعداد کل حالتهای پرانتزبندی ضرب زنجیری n ماتریس، مطابق با جملات دنباله اعداد کاتالان هستند:

هدف ما این است که در بین تمامی این حالت ها، حالتی را بیابیم که حاصل ضرب ماتریسها با حداقل ضرب عددی محاسبه شود.

روش تقسیم و حل (Divide and Conquer):

ابتدا سعی می کنیم با استفاده از روش تقسیم و حل الگوریتمی برای پاسخ مساله پیدا کنیم. برای اینکار عبارت مورد نظر را به دو قسمت تقسیم می کنیم. به عنوان مثال فرض کنید n = 7 باشد. در این صورت به شش طریق می توان عبارت را به دو دسته تقسیم کرد:

1: ( M1 ) x ( M2 x M3 x M4 x M5 x M6 x M7 )

2: ( M1 x M2 ) x ( M3 x M4 x M5 x M6 x M7 )

3: ( M1 x M2 x M3 ) x ( M4 x M5 x M6 x M7 )

4: ( M1 x M2 x M3 x M4 ) x ( M5 x M6 x M7 )

5: ( M1 x M2 x M3 x M4 x M5 ) x ( M6 x M7 )

6: ( M1 x M2 x M3 x M4 x M5 x M6 ) x ( M7 )

هر کدام از حاصلضربهای داخل پرانتزها، زیر مساله ای با n < 7 هستند. همانطور که می دانید در ضرب دو ماتریس، تعداد ستونهای ماتریس اول با تعداد سطرهای ماتریس دوم برابر است. در نتیجه ابعاد هفت ماتریس فوق را به صورت زیر می توان خلاصه کرد:

d0 , d1 , d2 , d3 , d4 , d5 , d6 , d7

که ماتریس اول d0 سطر و d1 ستون، ماتریس دوم d1 سطر و d2 ستون، . . . و ماتریس هفتم d6 سطر و d7 ستون دارد. حال تابع Mult را به گونه ای تعریف می کنیم که حداقل ضربهای مورد نیاز برای ضرب ماتریسهای iام تا jام را محاسبه کند. در این صورت برای شش حالت فوق داریم:

1: ( M1 ) x ( M2 x M3 x M4 x M5 x M6 x M7 ) : min1 = Mult( 1, 1 ) + Mult( 2, 7 ) + d0 d1 d7

2: ( M1 x M2 ) x ( M3 x M4 x M5 x M6 x M7 ) : min2 = Mult( 1, 2 ) + Mult( 3, 7 ) + d0 d2 d7

3: ( M1 x M2 x M3 ) x ( M4 x M5 x M6 x M7 ) : min3 = Mult( 1, 3 ) + Mult( 4, 7 ) + d0 d3 d7

4: ( M1 x M2 x M3 x M4 ) x ( M5 x M6 x M7 ) : min4 = Mult( 1, 4 ) + Mult( 5, 7 ) + d0 d4 d7

5: ( M1 x M2 x M3 x M4 x M5 ) x ( M6 x M7 ) : min5 = Mult( 1, 5 ) + Mult( 6, 7 ) + d0 d5 d7

6: ( M1 x M2 x M3 x M4 x M5 x M6 ) x ( M7 ) : min6 = Mult( 1, 6 ) + Mult( 7, 7 ) + d0 d6 d7

قسمت اول عبارتهای فوق مربوط به محاسبه زیرمساله سمت چپ، قسمت دوم برای محاسبه زیرمساله سمت راست، و قسمت سوم ضرب دو ماتریس حاصل از زیر مساله ها در یکدیگر است. به عنوان نمونه در سطر سوم پس از تفکیک مساله به دو زیر مساله، دو ماتریس با ابعاد ( d0, d3 ) و ( d3, d7 ) به دست می آیند، که باید در پایان کار به هم ضرب شوند. حال با مینیمم گرفتن از minkها مساله اصلی حل می شود:

Mult( 1, 7 ) = Min { mink } = Min { Mult( 1, k ) + Mult( k + 1, 7 ) + d0 dk d7 } , k = 1, 2 , 3 , ... , 6

این رابطه را می توان به صورت کلی برای هر شروع و انتهایی نوشت:

Mult( i, j ) = Min { mink } = Mult( i, k ) + Mult( k + 1, j ) + di - 1 dk dj } , k = i, i + 1, i + 2, ... , j - 1

توجه داشته باشید که اگر i < j نباشد منطق حکم می کند که ( Mult( i, j صفر شود. با توجه به توصیحات فوق، بدنه تابع Mult در حالت کلی به این صورت خواهد بود:

int Mult( int i, int j )

{

int min;

min = minimum of { Mult( i, k ) + Mult( k + 1, j ) + d[ i - 1 ] * d[ k ] * d[ j ] } for k = i, i + 1, i + 2, . . . , j - 1;

return min;

}

در این تابع ابعاد ماتریسها در فرم آرایه d به صورت عمومی تعریف شده اند. ثابت شده است مرتبه چنین تابعی برای پرانتزبندی بهینه ضرب زنجیری n ماتریس ( O( 3n است. به نظر می رسد که این روش کارا نیست. علت آن هم وجود همپوشانی است که در ادامه به آن می پردازیم.

روش برنامه نویسی پویا (DynamicProgramming):

حال به سراغ برنامه نویسی پویا رفته و دو شرط لازم این روش برای حل مسائل بهینه سازی را بررسی می کنیم:

1- همپوشانی: برای بررسی وجود همپوشانی در تابع فوق دو روش وجود دارد. اول اینکه درخت فراخوانی های بازگشتی تابع را به ازای یک n کوچک رسم کرده و فراخوانی ها تکراری را مشاهده کنید. دومین روش این است که به مرتبه تعداد فراخوانی ها توجه کنید. با توجه به اینکه مقادیر i و j اعداد طبیعی کوچکتر از n هستند، تعداد کل حالتهای فراخوانی تابع Mult با پارامترهای مختلف از مرتبه ( O( n2 خواهد بود. در حالی که ثابت شده است تعداد کل فراخوانی های تابع از مرتبه ( O( 3n است. این اختلاف تنها می تواند ناشی از فراخوانیهای تکراری باشد.

2- اصل بهینگی: اگر بنا باشد پرانتزبندی کل عبارت بهینه شود، پرانتزبندی زیرمساله ها هم باید بهینه باشند. یعنی بهینه بودن مساله، بهینه بودن زیر مساله ها را ایجاب می کند و اصل بهینگی در اینجا صادق است.

پس با توجه به توضیحات فوق می توان از روش برنامه نویسی پویا استفاده کرد.

در روش برنامه نویسی پویا اغلب از یک آرایه برای ذخیره نتایج جهت استفاده مجدد استفاده شده، و زیر مسائل به صورت جزء به کل حل می شوند. در مورد این مساله، ابتدا زیر مسائلی که تنها از دو ماتریس تشکیل شده اند محاسبه می شوند. سپس زیر مسائلی که از سه ماتریس تشکیل شده اند محاسبه می شوند. این دسته از زیر مسائل به زیر مسائلی متشکل از دو ماتریس تجزیه می شوند که قبلا محاسبات آنها صورت گرفته، و نتایج آنها در آرایه ذخیره شده اند. در نتیجه نیاز به محاسبه مجدد آنها نیست. به همین ترتیب در مرحله بعد زیر مسائل با چهار ماتریس محاسبه می شوند، و الی آخر.

برای پیاده سازی این روش آرایه دوبعدی M را منطبق با عملکرد تابع Mult تعریف می کنیم. این آرایه دوبعدی به صورت زیر تعریف می شود:

M[ i ][ j ] = Min { M[ i ][ k ] + M[ k + 1 ][ j ] + d[ i ] * d[ k + 1 ] * d [ j ] } , k = i, i + 1, i + 2, . . . , j - 1 ; 0 < i < j < n + 1

M[ i ][ j ] = 0 ; 0 < i = j < n + 1

توجه داشته باشید که اندیس شروع آرایه ها را یک در نظر گرفته ایم و تنها از قسمت بالای قطر اصلی ماتریس استفاده می کنیم. تابع زیر محاسبات لازم را جهت ساخت این ماتریس انجام می دهد:

int Mult( int n )

{

int i, j;

for( i = 1 ; i <= n ; i++ )

{

M[ i ][ i ] = 0;

}

for( i = 1 ; i < n ; i++ )

{

for( j = 1 ; j <= n - i ; j++ )

{

M[ j ][ i + j ] = Minimum of { M[ i ][ k ] + M[ k + 1 ][ j ] + d[ i - 1 ] * d[ k ] * d[ j ] } for k = i, i + 1, i + 2, ..., j - 1

}

return M[ 1 ][ n ];

}

تابع مقدار [ M[ 1 ][ n را باز می گرداند که همان تعداد ضربهای لازم جهت محاسبه ضرب زنجیره ای n ماتریس در حالت پرانتزبندی بهینه است. این تابع دو حلقه تکرار دارد که مرتبه ( O( n2 را نشان می دهند. اما یافتن مینیمم داده ها درون حلقه داخلی نیز وجود دارد که از مرتبه ( O( n است. در نتیجه مرتبه کل تابع فوق ( O( n3 خواهد بود که در مقایسه با ( O( 3nبهبود چشم گیری را نمایش می دهد.

مزیت دیگر این روش - که از اصل بهینگی ناشی می شود - آن است که با انجام این محاسبات، نه تنها مساله ما به ازای ضرب n ماتریس، که به ازای همه زیر مسائل حل شده است. به عنوان نمونه [ M[ 2 ][ 4 تعداد ضربهای لازم در پرانتزبندی بهینه ماتریسهای دوم تا چهارم را نشان می دهد.

در پایان باید توجه داشته باشید که:

1- در دو تابعی که اینجا آورده شده است، تنها تعداد ضربهای لازم در پرانتزبندی بهینه محاسبه شده است، و شیوه پرانتزبندی مد نظر نیست.

2- به نظر می رسد روش برنامه نویسی پویا از روش تقسیم و حل قدرتمندتر است! اما همیشه اینگونه نیست. ما در همه حال باید به دو شرط اساسی امکان استفاده از برنامه نویسی پویا جهت طراحی الگوریتم توجه داشته باشیم. این روش برای مسائلی کاربرد دارد که آن دو شرط در آنها صدق کنند. در بسیاری از مسائل این دو شرط لزوما برقرار نیستند، و ممکن است طراحی الگوریتم حل آنها با استفاده از روش تقسیم و حل کاراتر باشد.

الگوریتم ضرب زنجیری ماتریس ها

مطالب مشابه :

الگوریتم ضرب زنجیری ماتریس ها

انواع ماتریس ها

تعریف ماتریس ها

ماتریسها

محاسبه ماتریس ها

ماتریس

ماتریس ها

مبحث ماتریس

121- ماتریس هدف ها(OMAX)