الگوریتم MinMull

[bghad1]

سلام...خوب هستین که ایشالا؟

یه سوال داشتم...میشه لطفاً یکی راهنمایی کنه و بگه که برای الگوریتم زیر باید چیکار کنم؟!

الگوریتمشو نمی دونم از کجا باید پیدا کنم...
استاد نگفته توی کدوم کتاب داره!!

توی اینترنتم پیدا نکردم:ناراحت:

الگوريتم MinMullو برنامه آن رو براي زنجيره ي 5 ماتريس A 10*4,A 4*5,A 5*20 , A 20*2 , A 2 * 50 اجرا کنه و ماتريسه M و P رو حساب کنه...( به ترتيب عدد , سطر , و ستون هاي ماتريس هستند)

( A= عدد , و به ترتيب از چپ به راست سطر و ستون مي باشد)

[bghad1]

یعنی کسی نیست که این الگوریتم رو بشناسه و یا بلد باشه؟!؟!؟؟!؟!؟1:افسرده::افسرد ه::متعجب:

کمککککککککککککک:عصبانی++:

[xxxxx_xxxxx]

سلام،
من فکر می کنم اسم الگوریتم رو اشتباه متوجه شدید. احیاناً MinMax نبود؟:متفکر:

[bghad1]

الگوریتم miniMal هست اسم درستش...خودم امروز متوجه شدم!!!!!

حالا چطور؟!؟؟!

[xxxxx_xxxxx]

اوه، ظاهراً اوضاع وخیم تر شد.:اشتباه:

Minimal اسم یک الگوریتم خاص نیست. یک الگوریتم میتونه Minimal باشه، به این معنی که با "کمترین هزینه" به انجام برسه.
حالا تو هر مسئله ای این "کمترین هزینه" معنی خودش رو داره. تو این مسئله‌ی شما که ضرب زنجیره ماتریس ها هست، منظور از Minimal این هست که با کمترین تعداد عمل ضرب، الگوریتم کار خودش رو به پایان برسونه.

حالا شما باید یک الگوریتم برای ضرب ماتریس ها بنویسید که Minimal باشه.

پ.ن: شاید هم اینجا منظور Minimal بودن سایز ماتریس هست.

[farzad1389]

اوه، ظاهراً اوضاع وخیم تر شد.:اشتباه:

Minimal اسم یک الگوریتم خاص نیست. یک الگوریتم میتونه Minimal باشه، به این معنی که با "کمترین هزینه" به انجام برسه.
حالا تو هر مسئله ای این "کمترین هزینه" معنی خودش رو داره. تو این مسئله‌ی شما که ضرب زنجیره ماتریس ها هست، منظور از Minimal این هست که با کمترین تعداد عمل ضرب، الگوریتم کار خودش رو به پایان برسونه.

حالا شما باید یک الگوریتم برای ضرب ماتریس ها بنویسید که Minimal باشه.

پ.ن: شاید هم اینجا منظور Minimal بودن سایز ماتریس هست.
بله احتمالا زنجیره ضرب ماتریسها منظور دوستمون بوده که تعداد ضربها باید مینیمال باشه
اینطور هستش یا نه؟

[bghad1]

نه... منظورم الگوریتم Minimul هستش....همچین الگوریتمی داریم دیگه!!!

نداریم؟!

اگه نداریم بگین لطفاً!!!!!

استادمون گفته باید پیاده سازیش کنیم برای این ماتریسایی که عرض کردم خدمتتون!!!!!

منم پیداش نکردم اصلاً!!!!

[xxxxx_xxxxx]

نه... منظورم الگوریتم Minimul هستش....همچین الگوریتمی داریم دیگه!!!

نداریم؟!

اگه نداریم بگین لطفاً!!!!!

دوست عزیز، خدمتتون عرض کردم که الگوریتمی با نام Minimal وجود ندارد.



استادمون گفته باید پیاده سازیش کنیم برای این ماتریسایی که عرض کردم خدمتتون!!!!!

شما یک الگوریتم برای ضرب ماتریس ها بنویسید که نتیجه آن Minimal باشد. مثلاً با الگوریتم استراسن (Strassen) میشه این کارو انجام داد، اما نتیجه آن Minimal نیست، پس باید مکانیزم دیگری برای حل مسئله پیدا کنید تا نتیجه Minimal باشد.

این صفحه رو ببینید:
Matrix Chain Multiplication (http://en.wikipedia.org/wiki/Matrix_chain_multiplication)

[دلفــي]

ضرب زنجیره ای ماتریس ها


#include //Prograer : Alireza Talebivoid
matrixchainorder(int); // for calculating m(i,j) & s(i,j)
void printparens(int,int); //for printinglong
m[10][10];int s[10][10];int p[10];void main(){ int n; printf("enter no of matrixes"); scanf("%d",&n);
printf("enter chain"); for(int i=0;i<=n;i++) { scanf("%d",&p[i]); } matrixchainorder(n);
printparens(1,n);}void matrixchainorder(int n){ long i,l,k,x; x=n; for(i=1;i<=x;i++) m[i][i]=0; for(l=2;l<=x;l++) { for(i=1;i<=x-l+1;i++) { int j=i+l-1; m[i][j]=1000000; for(k=i;k<=j-1;k++) {
long a=m[i][k];
long b=m[k+1][j];
long c=p[i-1]*p[k]*p[j]; long q=a+b+c;
if(q { m[i][j]=q; s[i][j]=k;
} } } }}

void printparens(int i,int j){ if(i==j) printf("A%d",i); else { printf("("); printparens(i,s[i][j]); printparens(s[i][j]+1,j); printf(")"); }}

[bootshow]

#include <cstdlib>
#include <iostream>

using namespace std;

int p[10][10];

int minmult(int n,int *,int p[][10]);

void order(int,int);

int main(int argc, char *argv[])
{

int i,j,n,*d,result;


printf("Welcome, Please enter the number of Matrix (Max 10):");

scanf("%d",&n);

printf("Ok, You enter %d, that meaning you have %d Matrix for multiplication.\n",n,n);

printf("Now, please enter the number of rows and columns for each matrix.\n\n");

d=(int *)malloc(sizeof(int) * (n+1));

for(i=0;i<n;i++){

printf("The number of rows for Matrix%d:",i+1); scanf("%d",&d[i]);

printf("The number of columns for Matrix%d:",i+1); scanf("%d",&d[i+1]);

printf("\n");

}

result=minmult(n,d,p);

printf("The best order for multiplication is: ");

order(1,n);

printf("\nThe number of multiplication is: M[1][n]=%d",result);

scanf("%d",&n);
}//end of main

int minmult(int n,int *d,int p[][10]){

int i,j,k,diagonal,temp;

int M[10][10];

for(i=0;i<10;i++) for(j=0;j<10;j++) M[i][j]=0;

for(diagonal=1;diagonal<=n-1;diagonal++)

for(i=1;i<=n-diagonal;i++){

j=i+diagonal;

temp=k=i; M[i][j]=M[i][k]+M[k+1][j]+d[i-1]*d[k]*d[j];

for(k=i+1;k<j;k++)

if((M[i][k]+M[k+1][j]+d[i-1]*d[k]*d[j])<M[i][j]){

M[i][j]=M[i][k]+M[k+1][j]+d[i-1]*d[k]*d[j];

temp=k;

}

p[i][j]=temp;

}

return M[1][n];

}//end of minmult

void order(int i,int j){

int k;

if(i==j)

printf("A%d",i);

else{

k=p[i][j];

printf("(");

order(i,k);

order(k+1,j);

printf(")");

}


}//end of order

/*int r,t;

printf("n=%d\n",n);

for(r=0;r<=n;r++) printf("d[%d]=%d ",r,d[r]); printf("\n");

printf("p\n"); for(r=1;r<10;r++){ for(t=1;t<10;t++) printf("%d ",p[r][t]); printf("\n"); }

printf("M\n"); for(r=1;r<10;r++){ for(t=1;t<10;t++) printf("%d ",M[r][t]); printf("\n"); }*/