(۲۸ خرداد ۱۳۹۳ ۱۱:۰۹ ق.ظ)sipser نوشته شده توسط:  حداقل تعداد ضرب ها برای ماتریس زیر کدام است ؟

۱۹۴ ضرب
روش پرانتز گذاری به صورت [tex](A((BC)D))[/tex]
باید سعی کنیم اعداد بزرگی مانند ۱۵ و ۱۰ تنها یک بار استفاده شوند چون ۱۵ از ابعاد وسطی است می توان با یک ضرب آن را از بین برد در داخلی ترین ضرب [tex]B_{2\times15}\ast C_{15\times3}[/tex] تعداد ضرب ها برابر است با ۲*۱۵*۳
حالا ماتریس حاصل از ضرب BC یک ماتریس [tex]2\times3[/tex] است و وقتی در D ضرب شود تعدا د ضرب های آن برابر است با ۲*۳*۴/
ماتریس حاصله تا اینجای کار [tex]2\times4[/tex] خواهد بود که برای ضرب A در آن به ۱۰*۲*۴ ضرب نیاز است
پس تعداد کل ضرب ها برابر است با :
[tex]2\ast15\ast3 2\ast3\ast4 10\ast2\ast4[/tex]
این کمترین تعداد ضرب هاست و اگر ترتیب پرانتزگذاری عوض شود تعداد ضرب ها نیز تغییر می کند و بیشتر می شود برای مثال در پرانتزگذاری [tex]((A(BC))D)[/tex] تعداد ضرب ها برابر است با:
[tex]2\ast15\ast3 2\ast3\ast10 4\ast3\ast10[/tex] که از قبلی بیشتر است.

[undefined=undefined]عجب سرعت عملی ایول الله داری خیلی ممنون فدا [/undefined]- (نمیدونم چرا انجمن لایک،تشکر نداره این مثبته هم میزنم اما اعمال نمیشه)