. متن داده‌شده را خلاصه کن

متن: برای شروع فرض کنید که ما می‌خواهیم کمترین هزینه یا کمترین تعداد عملیات ریاضی را که برای ضرب ماتریس‌ها نیاز داریم را بدانیم. اگر ما فقط دو ماتریس را می‌خواهیم ضرب کنیم فقط یک راه برای ضرب آنها وجود دارد بنابراین کمترین هزینه فقط هزینه انجام این عمل خواهد بود. معمولا ما می‌توانیم برای پیدا کردن کمترین هزینه از الگوریتم بازگشتی به صورت زیر استفاده کنیم: توالی ماتریس‌ها را گرفته و به دو زیر رشته جدا کنید کمترین هزینه را از ضرب کردن هر توالی فرعی پیدا کنید این هزینه‌ها را جمع کرده و با هزینه ضرب دو حاصل ماتریس جمع کنید این عمل را برای هر وضیعت ممکنی که توالی ماتریس‌ها از هم جدا شود انجام دهید و مینیمم همه آنها را بگیرید. برای مثال اگر ما چهار ماتریس abcd داشته باشیم ما هزینه‌ای که برای هرکدام (cd) (ab)، (bcd) (a)، (d) (abc) نیاز هست را محاسبه می‌کنیم. از بازگشتی برای پیدا کردن کمترین هزینه برای محاسبه bcd استفاده می‌کنیم. سپس بهترین را انتخاب می‌کنیم نه‌تنها کمترین هزینه را شامل می‌گردد بلکه بهترین راه برای نشان دادن ضرب است: آنها را طوری گروه‌بندی کنید که کمترین هزینه کل را بدهد و این کار را برای هر عامل انجام بدهید متأسفانه اگر این الگوریتم را اجرا کنیم می‌فهمیم که آهسته خواهد بود مانند راه قدیمی که ما سعی کردیم تمام تبدیل‌ها را انجام دهیم. چه اشتباهی کرده‌ایم؟ جواب این است که ما کار تکراری را انجام داده‌ایم. اما برای اینکه بهترین هزینه را برای abc به دست بیاوریم نیاز داریم که بهترین هزینه را برای ab به دست بیاوریم. همینطور که بازگشت عمیق‌تر می‌شود این نوع از تکرارها بیشتر و بیشتر اتفاق می‌افتد. یک راه‌حل سادهmemoization است. هر وقت ما حد اقل هزینه مورد نیاز را برای ضرب یک زیر توالی‌های فرعی محاسبه می‌کنیم ما آنها را ذخیره می‌کنیم. هر وقت از ما خواسته شود دوباره آن را محاسبه کنیم به سادگی جوابی را که محاسبه کردیم را می‌دهیم و محاسبه‌ای را انجام نمی‌دهیم. وقتی‌که در حدود n ۲ / ۲ (به طوری که «n» تعداد ماتریس‌ها می‌باشد). فضایی که برای این کار مورد نیاز است منطقی به نظر می‌رسد. می‌توان نشان داد که این حقه ساده زمان را از (o (۲ n به (o (n ۳ کاهش می‌دهد که برنامه‌ریزی پویا از بالا به پایین می‌باشد. راه‌حل دیگر این است که پیش‌بینی کنیم که به کدام هزینه‌ها نیاز خواهیم داشت و پیش محاسبه انجام …
خلاصه:
ضرب زنجیره‌ای ماتریس مسئله‌ای است که می‌تواند با استفاده از برنامه‌سازی پویا حل شود . وقتی یک توالی از ماتریس‌ها را داریم ما می‌خواهیم موثرترین راه را برای ضرب این ماتریس‌ها را با هم پیدا کنیم . مسئله اجرای ضرب‌ها نیست مسئله ترتیب اجرای ضرب‌ها است . ما انتخاب‌های زیادی داریم به خاطر این که ضرب ماتریس‌ها با هم در ارتباطند به عبارتی دیگر اهمیتی ندارد که ما چگونه جمله را پرانتز گذاری کنیم زیرا نتیجه یکسان خواهد بود . برای مثال اگر چهار ماتریس a ، b ، c ، dداشته باشیم به این صورت خواهد بود : به هر حال ترتیب پرانتز گذاری جمله روی تعداد عملیات ریاضی ساده‌ای که برای محاسبهٔ نتیجه نیاز است تاثیر خواهد گذاشت .