موضوع مقاله: ضرب زنجیره‌ای ماتریس | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # ضرب زنجیره‌ای ماتریس | مقدمه: ضرب زنجیره‌ای ماتریس مسئله‌ای است که می‌تواند با استفاده از برنامه‌سازی پویا حل شود. | ## بخش 1: ضرب زنجیره‌ای ماتریس | وقتی یک توالی از ماتریس‌ها را داریم ما می‌خواهیم موثرترین راه را برای ضرب این ماتریس‌ها را با هم پیدا کنیم. ما انتخاب‌های زیادی داریم به خاطر این که ضرب ماتریس‌ها با هم در ارتباطند به عبارتی دیگر اهمیتی ندارد که ما چگونه جمله را پرانتز گذاری کنیم زیرا نتیجه یکسان خواهد بود. به هر حال ترتیب پرانتز گذاری جمله روی تعداد عملیات ریاضی ساده‌ای که برای محاسبهٔ نتیجه نیاز است تاثیر خواهد گذاشت. برای مثال فرض کنید A یک ماتریس ۱۰ × ۳۰ وB یک ماتریس ۳۰ ×۵ وCیک ماتریس ۵× ۶۰است سپس AB)C = (۱۰×۳۰×۵) + (۱۰×۵×۶۰) = ۱۵۰۰ + ۳۰۰۰ = ۴۵۰۰ ) A(BC) = (۳۰× 10×۶۰) + ( 5×۳۰×۶۰) = ۹۰۰۰ + ۱۸۰۰۰ = ۲۷۰۰۰ واضح است که اولین روش بهینه‌است. حالا که ما مسئله را شناختیم چطور ما پرانتز سازی یک نتیجه یn ماتریس را مشخص کنیم. ما می‌توانیم هر کدام از پرانتز سازی ممکن را انجام بدهیم اما نیاز به زمان (O(۲ n دارد که برای nهای بزرگ خیلی آهسته خواهد بود.راه حل همان طور که خواهیم دید مسئله ر ا به مسائل کوچکتر مرتبط بشکنیم. به وسیلهٔ حل کردن مسائل کوچکتر برای یک بار و استفاده دوباره این راه حل‌ها ما می‌توانیم به طور قابل توجهی زمان مورد نیاز را کاهش دهیم این به عنوان برنامه سازی پویا شناخته شده‌است. | ## بخش 2: ضرب زنجیره‌ای ماتریس | الگوریتم برنامه سازی دینامیک برای شروع فرض کنید که ما می‌خواهیم کمترین هزینه یا کمترین تعداد عملیات ریاضی را که برای ضرب ماتریس‌ها نیاز داریم را بدانیم.اگر ما فقط دو ماتریس را می‌خواهیم ضرب کنیم فقط یک راه برای ضرب آنها وجود دارد بنابراین کمترین هزینه فقط هزینهٔ انجام این عمل خواهد بود. معمولاً ما می‌توانیم برای پیدا کردن کمترین هزینه از الگوریتم بازگشتی به صورت زیر استفاده کنیم: توالی ماتریس‌ها را گرفته و به دو زیر رشته جدا کنید کمترین هزینه را از ضرب کردن هر توالی فرعی پیدا کنید این هزینه‌ها را جمع کرده و با هزینهٔ ضرب دو حاصل ماتریس جمع کنید این عمل را برای هر وضیعت ممکنی که توالی ماتریس‌ها از هم جدا شود انجام دهید و مینیمم همهٔ آنها را بگیرید. سپس بهترین را انتخاب می‌کنیم نه تنها کمترین هزینه را شامل می‌گردد بلکه بهترین راه برای نشان دادن ضرب است: آنها را طوری گروه بندی کنید که کمترین هزینهٔ کل را بدهد و این کار را برای هر عامل انجام بدهید متأسفانه اگر این الگوریتم را اجرا کنیم می‌فهمیم که آهسته خواهد بود مانند راه قدیمی که ما سعی کردیم تمام تبدیل‌ها را انجام دهیم.چه اشتباهی کرده ایم؟ اما برای اینکه بهترین هزینه را برای ABC به دست بیاوریم نیاز داریم که بهترین هزینه را برای AB به دست بیاوریم. همینطور که بازگشت عمیق تر می‌شود این نوع از تکرارها بیشتر و بیشتر اتفاق می‌افتد. هر وقت ما حد اقل هزینهٔ مورد نیاز را برای ضرب یک زیر توالی‌های فرعی محاسبه می‌کنیم ما آنها را ذخیره می‌کنیم.هر وقت از ما خواسته شود دوباره آن را محاسبه کنیم به سادگی جوابی را که محاسبه کردیم را می‌دهیم و محاسبه‌ای را انجام نمی‌دهیم. وقتی که در حدود n ۲ /۲ (به طوری که«n» تعداد ماتریس‌ها می‌باشد).فضایی که برای این کار مورد نیاز است منطقی به نظر می‌رسد.می توان نشان داد که این حقهٔ ساده زمان را از(O(۲ n به(O(n ۳ کاهش می‌دهد که برنامه ریزی پویا از بالا به پایین می‌باشد. | ## بخش 3: ضرب زنجیره‌ای ماتریس | راه حل دیگر این است که پیش بینی کنیم که به کدام هزینه‌ها نیاز خواهیم داشت و پیش محاسبه انجام دهیم. if (q <m[i,j { m[i,j] = q; s[i,j] = k; } } } } } برای هرk از 2 تاً n ماتریس: محاسبه کنیم حداقل هزینه‌های هر توالی فرعی از طول k را با استفاده از هزینه‌هایی که قبلاً محاسبه شده‌است.برای محاسبهٔ هزینه هر توالی فرعی طول k از محاسبهٔ قبلی استفاده کنیم. موقعی که این را انجام دادیم ما حداقل هزینه را برای تمام آن توالی داریم.اگر چه این زیر روال به زمان ( O(n''3 نیاز دارد مزیت این روش این است که نیازی به آزمایش ندارد اگر مقدار قبلاً محاسبه شده باشد و ما می‌توانیم فضایی را به وسیلهٔ دور ریختن بعضی از نتایج فرعی که به آن نیازی نیست ذخیره کنیم این برنامه‌ریزی پایین به بالاست. به سراغ برنامه‌نویسی پویا رفته و دو شرط لازم این روش برای حل مسائل بهینه‌سازی را بررسی می‌کنیم: 1- همپوشانی: برای بررسی وجود همپوشانی در تابع فوق دو روش وجود دارد. اول اینکه درخت فراخوانی‌های بازگشتی تابع را به ازای یک n کوچک رسم کرده و فراخوانی‌های تکراری را مشاهده کنید. با توجه به اینکه مقادیر i و j اعداد طبیعی کوچکتر از n هستند، تعداد کل حالت‌های فراخوانی تابع Mult با پارامترهای مختلف از مرتبه ( O( n2 خواهد بود. 2- اصل بهینگی: اگر بنا باشد پرانتزبندی کل عبارت بهینه شود، پرانتزبندی زیرمسئله‌ها هم باید بهینه باشند. | ## جمع‌بندی | یک الگوریتم موثرتر الگوریتمی که در سال 1984 توسط هو و شینگ انتشار یافت که زمان اجرایش است.اگر چه این الگوریتم به خوبی برای مسائلی که ضرب زنجیره‌ای ماتریس‌ها اجرا می‌شود محققینی مانند جرالد بوم گاردنر فهمید که می‌توان آنرا برای حل مسائل انتزاعی هم تعمیم داد: دادن یک توالی رشته خطی از شی‌ها و عملیات دودویی مرتبط روی این شی‌ها وراهی برای محاسبه هزینهٔ اجرای آن عملیات روی هر ذو شی داده شده.