ضرب زنجیره‌ای ماتریس

ضرب زنجیره‌ای ماتریس مسئله‌ای است که می‌تواند با استفاده از برنامه‌سازی پویا حل شود. وقتی یک توالی از ماتریس‌ها را داریم ما می‌خواهیم موثرترین راه را برای ضرب این ماتریس‌ها را با هم پیدا کنیم. مسئله اجرای ضرب‌ها نیست مسئله ترتیب اجرای ضرب‌ها است. ما انتخاب‌های زیادی داریم به خاطر این که ضرب ماتریس‌ها با هم در ارتباطند به عبارتی دیگر اهمیتی ندارد که ما چگونه جمله را پرانتز گذاری کنیم زیرا نتیجه یکسان خواهد بود. برای مثال اگر چهار ماتریس A،B،C،Dداشته باشیم به این صورت خواهد بود:

(ABC)D = (AB)(CD) = A(BCD) = A(BC)D =...

به هر حال ترتیب پرانتز گذاری جمله روی تعداد عملیات ریاضی ساده‌ای که برای محاسبهٔ نتیجه نیاز است تاثیر خواهد گذاشت. برای مثال فرض کنید A یک ماتریس ۱۰ × ۳۰ وB یک ماتریس ۳۰ ×۵ وCیک ماتریس ۵× ۶۰است سپس

AB)C = (۱۰×۳۰×۵) + (۱۰×۵×۶۰) = ۱۵۰۰ + ۳۰۰۰ = ۴۵۰۰ )

A(BC) = (۳۰× 10×۶۰) + ( 5×۳۰×۶۰) = ۹۰۰۰ + ۱۸۰۰۰ = ۲۷۰۰۰

واضح است که اولین روش بهینه‌است. حالا که ما مسئله را شناختیم چطور ما پرانتز سازی یک نتیجه یn ماتریس را مشخص کنیم. ما می‌توانیم هر کدام از پرانتز سازی ممکن را انجام بدهیم اما نیاز به زمان (O(۲ ⁿ دارد که برای nهای بزرگ خیلی آهسته خواهد بود.راه حل همان طور که خواهیم دید مسئله ر ا به مسائل کوچکتر مرتبط بشکنیم. به وسیلهٔ حل کردن مسائل کوچکتر برای یک بار و استفاده دوباره این راه حل‌ها ما می‌توانیم به طور قابل توجهی زمان مورد نیاز را کاهش دهیم این به عنوان برنامه سازی پویا شناخته شده‌است.

الگوریتم برنامه سازی دینامیک

برای شروع فرض کنید که ما می‌خواهیم کمترین هزینه یا کمترین تعداد عملیات ریاضی را که برای ضرب ماتریس‌ها نیاز داریم را بدانیم.اگر ما فقط دو ماتریس را می‌خواهیم ضرب کنیم فقط یک راه برای ضرب آنها وجود دارد بنابراین کمترین هزینه فقط هزینهٔ انجام این عمل خواهد بود. معمولاً ما می‌توانیم برای پیدا کردن کمترین هزینه از الگوریتم بازگشتی به صورت زیر استفاده کنیم:

• توالی ماتریس‌ها را گرفته و به دو زیر رشته جدا کنید
• کمترین هزینه را از ضرب کردن هر توالی فرعی پیدا کنید
• این هزینه‌ها را جمع کرده و با هزینهٔ ضرب دو حاصل ماتریس جمع کنید
• این عمل را برای هر وضیعت ممکنی که توالی ماتریس‌ها از هم جدا شود انجام دهید و مینیمم همهٔ آنها را بگیرید.

برای مثال اگر ما چهار ماتریس ABCD داشته باشیم ما هزینه‌ای که برای هرکدام (CD)(AB) ، (BCD)(A)،(D)(ABC)نیاز هست را محاسبه می‌کنیم. از بازگشتی برای پیدا کردن کمترین هزینه برای محاسبهٔ BCD استفاده می‌کنیم. سپس بهترین را انتخاب می‌کنیم نه تنها کمترین هزینه را شامل می‌گردد بلکه بهترین راه برای نشان دادن ضرب است: آنها را طوری گروه بندی کنید که کمترین هزینهٔ کل را بدهد و این کار را برای هر عامل انجام بدهید متأسفانه اگر این الگوریتم را اجرا کنیم می‌فهمیم که آهسته خواهد بود مانند راه قدیمی که ما سعی کردیم تمام تبدیل‌ها را انجام دهیم.چه اشتباهی کرده ایم؟ جواب این است که ما کار تکراری را انجام داده‌ایم. اما برای اینکه بهترین هزینه را برای ABC به دست بیاوریم نیاز داریم که بهترین هزینه را برای AB به دست بیاوریم. همینطور که بازگشت عمیق تر می‌شود این نوع از تکرارها بیشتر و بیشتر اتفاق می‌افتد. یک راه حل سادهmemoization است. هر وقت ما حد اقل هزینهٔ مورد نیاز را برای ضرب یک زیر توالی‌های فرعی محاسبه می‌کنیم ما آنها را ذخیره می‌کنیم.هر وقت از ما خواسته شود دوباره آن را محاسبه کنیم به سادگی جوابی را که محاسبه کردیم را می‌دهیم و محاسبه‌ای را انجام نمی‌دهیم. وقتی که در حدود n ^۲ /۲ (به طوری که«n» تعداد ماتریس‌ها می‌باشد).فضایی که برای این کار مورد نیاز است منطقی به نظر می‌رسد.می توان نشان داد که این حقهٔ ساده زمان را از(O(۲ ⁿ به(O(n ^۳ کاهش می‌دهد که برنامه ریزی پویا از بالا به پایین می‌باشد. راه حل دیگر این است که پیش بینی کنیم که به کدام هزینه‌ها نیاز خواهیم داشت و پیش محاسبه انجام دهیم.

Matrix-Chain-Order(int p[])
{
    n = p.length - 1;
    for (i = 1; i <= n; i++) 
       m[i,i] = 0;

    for (l=2; l<=n; l++) { // l is chain length
        for (i=1; i<=n-l+1; i++) {
            j = i+l-1;
            m[i,j] = MAXINT;
            for (k=i; k<=j-1; k++) {
                q = m[i,k] + m[k+1,j] + p[i-1]*p[k]*p[j];//Matrix Ai has the dimension  p[i-1] x p[i].
                if (q <m[i,j]) {
                    m[i,j] = q;
                    s[i,j] = k;
                }
            }
        }
    }
}

• برای هرk از 2 تاً n ماتریس:
  • محاسبه کنیم حداقل هزینه‌های هر توالی فرعی از طول k را با استفاده از هزینه‌هایی که قبلاً محاسبه شده‌است.برای محاسبهٔ هزینه هر توالی فرعی طول k از محاسبهٔ قبلی استفاده کنیم.

موقعی که این را انجام دادیم ما حداقل هزینه را برای تمام آن توالی داریم.اگر چه این زیر روال به زمان ( O(n³ نیاز دارد مزیت این روش این است که نیازی به آزمایش ندارد اگر مقدار قبلاً محاسبه شده باشد و ما می‌توانیم فضایی را به وسیلهٔ دور ریختن بعضی از نتایج فرعی که به آن نیازی نیست ذخیره کنیم این برنامه‌ریزی پایین به بالاست.

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

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

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

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

یک الگوریتم موثرتر

الگوریتمی که در سال 1984 توسط هو و شینگ انتشار یافت که زمان اجرایش $n\cdot log(n)$ است.اگر چه این الگوریتم به خوبی برای مسائلی که ضرب زنجیره‌ای ماتریس‌ها اجرا می‌شود محققینی مانند جرالد بوم گاردنر فهمید که می‌توان آنرا برای حل مسائل انتزاعی هم تعمیم داد: دادن یک توالی رشته خطی از شی‌ها و عملیات دودویی مرتبط روی این شی‌ها وراهی برای محاسبه هزینهٔ اجرای آن عملیات روی هر ذو شی داده شده.

منابع

• Wikipedia contributors, "Matrix chain multiplication," Wikipedia, The Free Encyclopedia, http://en.wikipedia.org/w/index.php?title=Matrix_chain_multiplication&oldid=287183531 (accessed May 15, 2009).

www.docs.linux.cz/programming/Algorithem-Morris/mat_chain.html

پیوند به بیرون

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