ضرب زنجیره‌ای ماتریس در Delphi ( دلفی )

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

    فرض کنید قصد داریم حاصلضرب عبارت ماتریسی A_۳x۷ x B_۷x۸ x C_۸x۴ را محاسبه کنیم. می‌دانیم که ضرب ماتریس‌ها خاصیت شرکت‌پذیری داشته، اما خاصیت جابجایی ندارد. بنابراین رعایت ترتیب ضرب آنها مهم است. پرانتزبندی‌های مختلف ضرب ماتریس‌ها حالت‌های مختلف محاسبه آن را به ما می‌دهند:

(۱: A x ( B x C

۲: ( A x B ) x C

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

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

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

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

۲: ( A x B ) x C : 3 x 7 x 8 + 3 x 8 x 4 = 264

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

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