ضریب 3 ماتریس ، اولویت ضرب ؟

[saeed7474]

سلام

در ضرب سه ماتریس a5*10 . b10*20 . c20*40 به چه ترتیبی انجام بدیم که سریعتر انجام بشه ؟

و
a13*5
b5*89
c89*3
d3*34

حداقل تعداد ضرب مورد نیاز برای محاسبه a.b.c.d چقده ؟

[omidshaman]

با استفاده از dynamic programing راحت میتونی جواب بگیری
قسمت dynamic programing --Matrix-chain multiplication
کتاب Introduction to algorithms
رو بخون

[sr2m72]

سلام

در ضرب سه ماتریس a5*10 . b10*20 . c20*40 به چه ترتیبی انجام بدیم که سریعتر انجام بشه ؟

و
a13*5
b5*89
c89*3
d3*34

حداقل تعداد ضرب مورد نیاز برای محاسبه a.b.c.d چقده ؟

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


m[i][j]=min(m[j][k]+m[k+1][j]+di * dk * dj)
i <= k <= j-1
-------------
m[i][i]=0


موفق باشید//

[saeed7474]

کدشو نمی خوام دوستان اینکه تئوری رو کاغذ بخوایم ماتریسشو ضرب کنیم چطور ؟

[Simorgh_94]

3 ماتریس A5*10 B10*20 C20*4 داریم :
اگر اول A با B در هم ضرب کنیم بعد در C ضرب کنیم :
1000 = 20*10*5 <== تعداد ضرب ها = [A5*10 * B10*20]
400 = 4*20*5 <== تعداد ضرب ها = A*B]5*20 * C20*4]
1400 = 1000+400 <== عداد ضرب ها = (AB)C))
ولی اگر اول B با C در هم ضرب کنیم بعد در A ضرب کنیم :
800= 4*20*10 <== تعداد ضرب ها = [B10*20 * C20*4]
200= 4*20*5 <== تعداد ضرب ها = A5*10 * [ B*C]10*4
1000= 800+200 <== عداد ضرب ها = A * BC

پس دومی روش سریع تر از اولی :

در کل در ضرب چند ماتریس در همدیگر ابتدا اونهایی رو در هم ضرب می کنیم که بعد وسطی انها بزرگ تر و بعدهای کناری کچکتر باشد در این صورت ماتریس حاصل کوچکتری خواهد داشت.

این مطلب در کتاب ساختمان داده ی اقای مقسمی کاردانی به کار شناسی صفحه ی 77 هستش البته توضیح زیادی نداده حالا اگه کتابش رو داری یه نگاهی بهش بنداز .
امید وارم به دردت بخوره .:لبخندساده: