تماس با ما

هرگونه پیشنهاد و انتقاد خود را با ما در میان بگذارید

فرض کنید می خواهیم تعدادی ماتریس را در هم ضرب کنیم، آنچه که مسلم است این است که ترتیب ضرب کردن ماتریس ها در نتیجه نهایی تاثیری ندارد مثلا اگر 5 ماتریس M1 و M2 و M3 و M4 و M5 داشته باشیم هر دو ترتیب (M2M3M4M5)(M1) و (M3M4M5)(M1M2) نتیجه نهایی یکسانی تولید می کند، اما سوالی که ممکن است به ذهن برسد این است که آیا تعداد مراحل انجام شده بین ترتیب های مختلف ضرب یکسان است و یا اینکه این تعداد با توجه به هر ترتیب متفاوت است؟

بدیهی است که ابعاد ماتریس های کنار هم بایستی متناسب باشد مثلا تعداد ستون های M1 بایستی با تعداد سطر های ماتریس M2 برابر باشد، در غیر این صورت ضرب تعریف نشده است.

ابتدا با یک مثال نشان میدهیم که تعداد مراحل انجام کار با توجه به ترتیب ضرب متفاوت است ( هرچند نتیجه نهایی ضرب یکسان است) مثلا اگر داشته باشیم:

M1=7*6, M2=6*3, M3=3*1, M4=1*5,M5=5*2

فرض کنید که ماتریس هایی که نام بردم به این صورت باشد:

\( \begin{bmatrix}1&2&3&1&2&1\\1&2&3&4&1&6\\4&2&1&-1&2&4\\-1&-1&0&0&0&1\\0&1&1&-1&3&5\\2&1&-2&7&1&1\\2&1&1&1&-1&-1 \end{bmatrix}*\begin{bmatrix}1&2&3\\1&2&3\\2&2&2\\1&1&-1\\0&0&0\\0&-1&-1\end{bmatrix}*\begin{bmatrix}1\\1\\2\end{bmatrix}*\begin{bmatrix}1&2&3&0&-1\end{bmatrix}*\begin{bmatrix}-1&5\\1&1\\0&4\\2&1\\1&2\end{bmatrix}\)
 
در حالتی که ترتیب ضرب به صورت (M3(M4M5))(M1M2) باشد مجموع تعداد عمل ضرب برابر است با:187=7*6*3+1*5*2+3*1*2+7*3*2

اما در حالتی که ترتیب ضرب به صورت (M1(M2((M3M4)M5)   باشد مجموع تعداد عمل ضرب برابر است با : 165= 3*1*5+3*5*2+6*3*2+7*6*2

یادآوری: در ضرب دو ماتریس تعداد عمل ضرب انجام شده برابر است با:  تعداد سطر ماتریس اول * تعداد ستون ماتریس اول * تعداد ستون ماتریس ماتریس دوم

واضح است که ترتیب دوم از ترتیب اول بهتر است اما آیا می توان گفت که این ترتیب بهترین حالت است؟ و اینکه چند حالت را باید بررسی کنیم تا بهترین حالت را پیدا کنیم؟

ابتدا تعداد کل حالت ها را به دست می آوریم: برای این منظور فرض کنید که ماتریس های ما از M1 تا Mn هستند و همچنین ابعاد ماتریس ها را به صورت D1 تا Dn+1 در نظر میگیریم ( توجه کنید که تعداد ستون هر ماتریس با تعداد سطر ماتریس بعدی برابر است، بنابراین نیازی به نوشتن این اعداد تکراری نیست و در نتیجه به ازای n ماتریس، n+1 عدد وجود دارد که به غیر از عدد اول و عدد آخر بقیه اعداد هر کدام به دو ماتریس تعلق دارد). فرض کنید که آخرین طبقه پرانتز گذاری به صورت (M1M2....Mk-2Mk-1) (MkMk+1....Mn) باشد،واضح است که در حالت بهینه k می تواند از 2 تا n-1 باشد، برای راحتی کار حداقل تعداد ضرب در n ماتریس را با P(1..n) نشان میدهیم پس در این حالت خاص داریم :

P(1..n)=P(1..k)+P(k..n)+D1DkDn

دقت کنید که D1DkDn تعداد ضرب مورد نیاز برای مرحله آخر از ضرب n ماتریس است زیرا در نهایی ترین مرحله ضرب دو ماتریس D1*Dk و Dk*Dn بُعدی داریم که باید در هم ضرب شوند، پس اگر k را از 2 تا n-1 تغییر دهیم و از مجموعه اعداد به دست آمده  کمترین عدد را بیابیم حد اقل تعداد ضرب به دست می آید، در ضمن داریم: P(x..x+1)=1 چون برای 1 ماتریس اصلا ضربی انجام نمیشه پس تعداد کل حالت ها از این فرمول به دست می آید:

\(P(1..n)=\min_{k=1}^n(P(1..k) + P(k..n)+D_1 D_k D_n ) \)

با توجه به این فرمول اگر بخواهیم از الگوریتم بازگشتی برای حل این مساله استفاده کنیم مساله بسیار پیچیده میشه بنابراین محاسبه کل حالت ها برای پیدا کردن ترتیب بهینه عاقلانه نیست و بهتره از روش دیگری برای پیدا کردن ترتیب بهینه استفاده بشه، در اینجا من به روش برنامه نویسی پویا راه حل ساده ای را نشان میدهم.

برای استفاده از برنامه نویسی پویا اول باید نشان دهیم در این مساله اصل بهینگی برقراره، پس ابتدا فرض میکنیم در ضرب ماتریس های M1 تا Mn فرم بهینه به صورت (Mk ... Mn)(M1... Mk) انجام میشه،یعنی حداقل تعداد ضرب در این حالت اتفاق می افته (دقت کنید که منظور از فرم (Mk ... Mn)(M1... Mk) اینه که اول (M1... Mk) رو انجام میدیم بعد (Mk ... Mn) رو انجام میدیم و بعد ماتریس های نهایی رو در هم ضرب میکنیم و فرض ما اینه که این ترتیب بهینه است).

سوال مهم اینه که آیا ترتیب ضرب کردن ماتریس های هر پرانتز به تنهایی ترتیب بهینه است؟ یعنی درون هر پرانتز باید ترتیبی با حداقل تعداد ضرب باشه تا ضرب دو تا ماتریس در نهایت ترتیب بهینه رو ایجاد کنه یا اینکه حتی اگر هر پرانتز ترتیب بهینه نباشه هم در نهایت این ترتیب بهینه میشه؟

واضحه که با توجه به فرمول \(P(1..n)=\min_{k=1}^n(P(1..k) + P(n-k..n)+D_1 D_k D_n ) \)  هر کدوم از پرانتزها هم باید بهینه باشه چون اگر نباشه میتونید بدون اینکه ترتیب (Mk ... Mn)(M1... Mk) تغییری بکنه میشه ترتیب داخل پرانتزها رو تغییر بدید و ترتیب بهینه رو در هر پرانتز جایگزین کنید در نهایت دو پرانتز رو  در هم ضرب کنید و در نتیجه با تعداد کمتری مرحله کل ضرب رو انجام بدید که با فرض اینکه ترتیب بالا بهینه است تناقض داره پس میشه با قاطعیت گفت ترتیب (Mk ... Mn)(M1... Mk) بهینه است اگر هریک از ترتیب های (Mk ... Mn) و(M1... Mk) بهینه باشند، پس اصل بهینگی برقراره و میشه از برنامه نویسی پویا برای حل این مساله استفاده کرد.

برای اینکه ورودی الگوریتم ما تا حد امکان ساده باشه تنها ابعاد ماتریس ها رو به عنوان ورودی در نظر میگیریم چون مقادیر ماتریس تاثیری در نتیجه نهایی نداره، همچنین چون در دو ماترس متوالی بایستی تعداد ستون ماتریس اول برابر تعداد سطر ماتریس دوم باشد نیازی به نوشن این اعداد تکراری نیست و در نهایت ورودی الگوریتم یک دنباله از اعداد میشود که هر دو عدد متوالی بیانگر ابعاد یک ماتریس است، به این ترتیب برای ماتریس های بالا باید دنباله رو به این شکل بنویسیم:

7,6,3,1,5,2

ملاحظه میکنید که برای ضرب 5 ماتریس به یک دنباله 6 تایی از اعداد میرسیم، به این ترتیب اگر بخواهیم ترتیب بهینه رو از روش عادی و با لیست کردن حالت های مختلف ضرب بدست بیاریم باید در هر مرحله 3 عدد متوالی رو (که نماینده دو ماتریس متوالی میشه) انتخاب کنیم و اونها رو در هم ضرب کنیم تا تعداد ضرب لازم برای یک ضرب بدست بیاد و در مرحله بعد عدد وسط رو از دنباله حذف کنیم مثلا در دنباله ماتریس های بالا اگر بخواهیم که دو ماتریس انتهایی رو در هم ضرب کنیم ابتدا سه عدد 1 و 5 و 2 را ضرب میکنیم که حاصل 10 ضرب است که تعداد مرحله لازم برای ضرب دو ماتریس 5*1 و 2*5 است و عدد 5 رو از دنباله حذف میکنیم که دنباله به صورت 7,6,3,1,2 در میاد یعنی ماتریس اخر 2*1 خواهد بود.

\( \begin{bmatrix}1&2&3&1&2&1\\1&2&3&4&1&6\\4&2&1&-1&2&4\\-1&-1&0&0&0&1\\0&1&1&-1&3&5\\2&1&-2&7&1&1\\2&1&1&1&-1&-1 \end{bmatrix}*\begin{bmatrix}1&2&3\\1&2&3\\2&2&2\\1&1&-1\\0&0&0\\0&-1&-1\end{bmatrix}*\begin{bmatrix}1\\1\\2\end{bmatrix}*\begin{bmatrix}0&17\end{bmatrix}\)

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

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

اولین کاری که میکنیم اینه که تعداد ضرب بهینه رو پیدا میکنیم و سپس الگوریتم رو جوری بهبود میدیم که ترتیب بهینه رو هم تولید کنه، برای این کار اول یک ماتریس دو بعدی میسازیم که مشخص کننده تعداد ضرب بهینه همه ماتریس های بین دو ماتریس است (منظور از بین دو ماتریس اینه که تمامی ماتریس های بین دو ماتریس رو درهم ضرب کنیم)، ماتریس اولیه خالیه اما الگوریتم به تدریج اون رو پر میکنه:

 7 0 0  126 60    
6   0 0 18    
3     0 0 15  
1       0 0 10
5         0 0
2           0
  7 6 3 1 5 2

 برای درک بهتر مفهوم این ماتریس یکی از خانه های اون رو به رنگ صورتی در اوردم و قراره که پس از پایان اجرای الگوریتم در این خانه مشخص بشه که حداقل تعداد ضرب زمانی که به ترتیب ماتریس های 3*6 و 1*3 و 5*1 در هم ضرب میشود چقدره.

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

در قطر سوم چون در ضرب دو ماتریس متوالی فقط یک حالت وجود داره اون یک حالت همون حالت بهینه است که طبق فرمول میشه ضرب سه عدد متوالی مربوط به ابعاد ماتریس ها.

در مرحله بعد به سراغ قطر چهارم میریم که مربوط به سه ماتریس متوالی هست، برای سه ماتریس متوالی تنها دو حالت وجود داره که باید بررسی بشه و دقت کنید که در حین بررسی نیاز به بررسی تعداد حالت دو ماتریس متوالی رو نداریم چون قبلا در قطر سوم ماتریس مقادیر آن محاسبه شده است، مثلا فرض کنید که میخواهیم حداقل تعداد ضرب رو در سه ماتریس نخست که ماتریس های 6*7 و 3*6 و 1*3 هستند را بیابیم (همون خونه ی قرمز رنگ که در شکل مشخص شده) در این حالت داریم:

تعداد مرحله لازم برای ضرب دو ماتریس اول و دوم= 126 ، ماتریس حاصل=3*7 ، تعداد مرحله لازم برای ضرب ماتریس حاصل در ماتریس سوم که ماتریس 1*3 است= 1*3*7=21 ، نتیجه نهایی= 21+126=147
تعداد مرحله لازم برای ضرب دو ماتریس دوم و سوم=18 ، ماتریس حاصل=1*6،تعداد مرحله لازم برای ضرب ماتریس حاصل در ماتریس اول که ماتریس 6*7 است= 7*6*1=42، نتیجه نهایی=42+18=60
در نهایت از بین دو عدد بدست آمده یعنی 60 و 147 عدد کوچکتر رو در سطر 1 ستون 4 قرار میدیم که با رنگ قرمز در جدول بالا مشخص شده.(دقت کنید که اعداد کنار ماتریس که با رنگ زرد مشخص شده شماره سطر و ستون نیست بلکه مربوط به ابعاد ماتریس هاست)

دقت کنید که در هر مرحله از نتیجه کار مرحله قبل استفاده میشه، مثلا برای پیدا کردن تعداد مرحله لازم برای ضرب دو ماتریس اول و دوم به جای اینکه از عمل 3*6*7 استفاده کنیم مستقیما به سراغ جدول میریم و عدد واقع در سطر اول، ستون 3 استفاده میکنیم.

معنی عدد قرمز مشخص شده در جدول اینه که اگر بخواهیم سه ماتریس 1*3 و 3*6 و 6*7 رو در هم ضرب کنیم حداقل تعداد مراحل لازم 60 مرحله است.

به همین ترتیب برای بقیه خانه های قطر چهارم عمل میکنیم و جدول به این شکل در میاد:

7 0 0 126 60  95 84
6   0 0 18 48 40
3     0 0 15 16
1       0 0 10
5         0 0
2           0
  7 6 3 1 5 2

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

کد زیر که به زبان ++c نوشتم همین کار رو میکنه با این تفاوت که به جای 5 تا ماتریس در این کد برای 6 تا ماتریس حداقل تعداد ضرب رو بدست میاره که 5 تای اولش همین ماتریس هاییه که در بالا اوردم:

int minvalue[6][6]={{0,9999,9999,9999,9999,9999},
                    {9999,0,9999,9999,9999,9999},
                    {9999,9999,0,9999,9999,9999},
                    {9999,9999,9999,0,9999,9999},
                    {9999,9999,9999,9999,0,9999},
                    {9999,9999,9999,9999,9999,0}};
int solve[6][6]={{0,0,0,0,0,0},
                 {0,0,0,0,0,0},
                 {0,0,0,0,0,0},
                 {0,0,0,0,0,0},
                 {0,0,0,0,0,0},
                 {0,0,0,0,0,0}};
int chain[6][2]=   {{7,6},{6,3},{3,1},{1,5},{5,2},{2,8}};


int main()
{
    int temp,row,col;
    for(int i=5;i>=0;i--)
        for(row=0,col=5-i;row<=i;row++,col++)
            for(int k=row+1;k<=col;k++)
            {
                temp=minvalue[row][k-1]+minvalue[k][col]+chain[row][0]*chain[k][0]*chain[col][1];
                if(minvalue[row][col]>temp) minvalue[row][col]=temp;
            }
    return 0;
}

 دقت کنید که این الکوریتم جواب رو چاپ نمیکنه بلکه فقط در آرایه minvalue ذخیره میکنه، و یک نکته مهم دیگه این که این الگوریتم به ما نمیگه که چطور ضرب رو انجام بدیم بلکه فقط حداقل تعداد ضرب رو حساب میکنه، اگر میخواهید که الگوریتم روش کار رو هم بگه باید کمی تغییر در این الگوریتم بدید تا هرگاه سطری از آرایه minvalue تغییر کرد جایی که تغییر در اون رخ داده رو در یک آرایه جداگانه ذخیره کنیم که این آرایه رو در الگوریتم بالا گذاشتم و اسمش هم solve هست. به این ترتیب آرایه ی solve به ما میگه در زنجیره ضرب ماتریس ها هر گاه بخواهیم حداقل تعداد ضرب رو در بخشی از زنجیره داشته باشیم ابتدا باید کدوم دو ماتریس رو در هم ضرب کنیم.

اینم از الگوریتمی که آرایه solve رو مخاسبه میکنه:

void printsolve(int i,int j);
int minvalue[6][6]={{0,9999,9999,9999,9999,9999},
                    {9999,0,9999,9999,9999,9999},
                    {9999,9999,0,9999,9999,9999},
                    {9999,9999,9999,0,9999,9999},
                    {9999,9999,9999,9999,0,9999},
                    {9999,9999,9999,9999,9999,0}};
int solve[6][6]={{0,0,0,0,0,0},
                 {0,0,0,0,0,0},
                 {0,0,0,0,0,0},
                 {0,0,0,0,0,0},
                 {0,0,0,0,0,0},
                 {0,0,0,0,0,0}};
int chain[6][2]=   {{7,6},{6,3},{3,1},{1,5},{5,2},{2,8}};


int main()
{
    int temp,row,col;
    for(int i=5;i>=0;i--)
        for(row=0,col=5-i;row<=i;row++,col++)
            for(int k=row+1;k<=col;k++)
            {
                temp=minvalue[row][k-1]+minvalue[k][col]+chain[row][0]*chain[k][0]*chain[col][1];
                if(minvalue[row][col]>temp)
                {
                    minvalue[row][col]=temp;
                    solve[row][col]=k;
                }
            }

    printsolve(0,5);
    return 0;
}
void printsolve(int i,int j)
{
    if(i==j)
        cout <<"M"<<i;
    else
    {
        cout<<"<";
        int temp=solve[i][j];
        printsolve(i,temp-1);
        printsolve(temp,j);
        cout<<">";
    }
}

 اما فقط یک سوال نهایی باقی مونده و اونم اینه که چطور با کمک ماتریس solve میشه راه حل بهینه رو بدست اورد؟

برای اینکه ببینیم چطور میشه به کمک آرایه solve میشه روش ضرب بهینه رو بدست آورد ابتدا دقت کنید که این آرایه چطور بدست میاد. اگر با دقت به برنامه نگاه کنید متوجه میشید که این آرایه زمانی مقدار دهی میشه که مقدار آرایه minvalue تغیییر میکنه و دلیل تغییر این آرایه هم با توجه به الگوریتم اینه که مقدار جدید محاسبه شده از مقدار قبلی که برای حداقل تعداد ضرب محاسبه شده کمتره پس میشه اینطور تصور کرد که آرایه solve مشخص کننده جاییه که باید ماتریس ها به دو بخش تقسیم بشه، بنابراین با کمک یک الگوریتم بازگشتی ساده میشه جواب نهایی رو چاپ کرد که در این مورد اسم اون رو گذاشتم printsolve و اگر دقت کنید این الگوریتم پرانتزگذاری هم میکنه.

 


منابع بیشتر:

الگوریتمستان

ویکیپدیا

بی کارت

 مدیریت کارت های بانکی

دانلود اپلیکیشن بی کارت از بازار:
https://goo.gl/cyNai2

تبلیغات


  تهران هاست
ارائه کننده خدمات میزبانی وب

 


 

مهندس رضا زنگنه

انجام هرگونه تعمیرات PC و لب تاپ در اصفهان

09387652826