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

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

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

برای مثال اگر ما چهار ماتریس 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 توسط هو و شینگ انتشار یافت که زمان اجرایش ${\displaystyle n\cdot log(n)}$

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