بستن پنجره
فرادرس - مجموعه آموزش‌های ویدئویی  مهندسی کامپیوتر - طراحی الگوریتم - ساختمان داده
بستن پنجره     از آخرین نوشته‌ها

»    مسابقه‌ی برنامه‌نویسی CodeCup 2018

»    دوره‌ی طراحی و تحلیل الگوریتم دانشگاه استنفورد

»    مسئله‌ی انتخابات

ضرب زنجیره‌ای ماتریس‌ها - الگوریتمستان
الگوریتمستان
4714.215.00
  »  

       

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

http://www.aachp.ir آنچه می‌خوانید ویراست جدید نوشته‌ای است که اولین بار با عنوان «ضرب زنجیری ماتریسها» مرداد ماه 1387 از طریق وبگاه برنامه‌نویسی و طراحی الگوریتم (عنوان و طرح پیشین وبگاه الگوریتمستان) منتشر شده بود.


آنچه در این نوشته می‌خوانید:

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

    فرض کنید قصد داریم حاصلضرب عبارت ماتریسی $ A_{3 \times 7} \times B_{7 \times 8 } \times C_{8 \times 4} $ را محاسبه کنیم. می‌دانیم که ضرب ماتریس‌ها خاصیت شرکت‌پذیری داشته، اما خاصیت جابجایی ندارد. بنابراین رعایت ترتیب ضرب آنها مهم است. پرانتزبندی‌های مختلف ضرب ماتریس‌ها حالت‌های مختلف محاسبه آن را به ما می‌دهند:

      

\[1: A \times (B \times C) \]

\[2: (A \times B) \times C \]

      

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

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

      

\[1: A \times (B \times C) : 7 \times 8 \times 4 + 3 \times 7 \times 4 = 308 \]

  

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

      

\[2: (A \times B) \times C : 3 \times 7 \times 8 + 3 \times 8 \times 4 = 264 \]

      

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

    ثابت شده است که تعداد کل حالت‌های پرانتزبندی ضرب زنجیری n ماتریس، مطابق با جملات دنباله‌ی اعداد کاتالان هستند:

      

\[C_{n-1} = \frac{1}{n} \begin{pmatrix} 2n - 2 \\ n - 1 \end{pmatrix} \]

      

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

      

استفاده از روش تقسیم و حل

  [بازگشت به فهرست]

ابتدا سعی می‌کنیم با استفاده از روش تقسیم و حل الگوریتمی برای پاسخ مسئله پیدا کنیم. برای این کار عبارت مورد نظر را به دو قسمت تقسیم می‌کنیم. به عنوان مثال فرض کنید n = 7 باشد. در این صورت به شش طریق می‌توان عبارت را به دو دسته تقسیم کرد:

      

\[1: (M_1) \times (M_2 \times M_3 \times M_4 \times M_5 \times M_6 \times M_7) \]

\[2: (M_1 \times M_2) \times (M_3 \times M_4 \times M_5 \times M_6 \times M_7) \]

\[3: (M_1  \times  M_2 \times M_3 ) \times (M_4 \times M_5 \times M_6 \times M_7) \]

\[4: (M_1  \times M_2 \times M_3 \times M_4 ) \times (M_5 \times M_6 \times M_7) \]

\[5: (M_1 \times M_2 \times M_3 \times M_4 \times M_5 ) \times (M_6 \times M_7) \]

\[6: (M_1 \times M_2 \times M_3 \times M_4 \times M_5 \times M_6) \times (M_7) \]

      

    هر کدام از حاصلضرب‌های داخل پرانتزها، زیرمسئله‌ای با n < 7 هستند. همانطور که می‌دانید در ضرب دو ماتریس، تعداد ستون‌های ماتریس اول با تعداد سطرهای ماتریس دوم برابر است. در نتیجه ابعاد هفت ماتریس فوق را به صورت زیر می‌توان خلاصه کرد:

      

\[d_0, d_1, d_2, d_3, d_4,, d_5,, d_6, d_7 \]

      

    که ماتریس اول $ d_0 $ سطر و $ d_1 $ ستون، ماتریس دوم $ d_1 $ سطر و $ d_2 $ ستون ... و ماتریس هفتم $ d_6 $ سطر و $ d_7 $ ستون دارد. حال تابع Mult را به گونه‌ای تعریف می‌کنیم که حداقل ضرب‌های مورد نیاز برای ضرب ماتریس‌های iام تا jام را محاسبه کند. در این صورت برای شش حالت فوق داریم:

      

\[1: (M_1) \times (M_2 \times M_3 \times M_4 \times M_5 \times M_6 \times M_7) : min_1 = Mult(1, 1) + Mult(2, 7) + d_0  d_1 d_7 \]

\[2: (M_1 \times M_2) \times (M_3 \times M_4 \times M_5 \times M_6 \times M_7) : min_2 = Mult(1, 2) + Mult(3, 7) + d_0  d_2 d_7 \]

\[3: (M_1 \times M_2 \times M_3)\times (M_4 \times M_5 \times M_6 \times M_7) : min_3 = Mult(1, 3) + Mult(4, 7) + d_0  d_3 d_7 \]

\[4: (M_1 \times M_2 \times M_3 \times M_4) \times ( M_5 \times M_6 \times M_7) : min_4 = Mult(1, 4) + Mult(5, 7) + d_0  d_4 d_7 \]

\[5: (M_1 \times M_2 \times M_3 \times M_4 \times M_5 ) \times (M_6 \times M_7) : min_5 = Mult(1, 5) + Mult(6, 7) + d_0  d_5 d_7 \]

\[6: (M_1 \times M_2 \times M_3 \times M_4 \times M_5 \times M_6) \times (M_7) : min_6 = Mult(1, 6) + Mult(7, 7) + d_0  d_6 d_7 \]

  

    قسمت اول عبارت‌های فوق مربوط به محاسبه‌ی زیرمسئله‌ی سمت چپ، قسمت دوم برای محاسبه‌ی زیرمسئله‌ی سمت راست و قسمت سوم ضرب دو ماتریس حاصل از زیرمسئله‌ها در یکدیگر است. به عنوان نمونه، در سطر سوم پس از تفکیک مسئله به دو زیرمسئله، دو ماتریس با ابعاد ($ d_0, d_3 $) و ($ d_3, d_7 $) به دست می‌آیند که باید در پایان کار در هم ضرب شوند. حال با مینیمم گرفتن از minkها مسئله‌ی اصلی حل می‌شود:

      

\[Mult(1, 7) = min \{ min_k \} = min \{ Mult(1, k) + Mult(k + 1, 7) + d_0 d_k d_7 \} \; \;, \qquad k = 1, \cdots, 6 \]

      

    این رابطه را می‌توان به صورت کلی برای هر شروع و انتهایی نوشت:

      

\[Mult(i, j) = min \{ min_k \} = min \{ Mult(i, k) + Mult(k + 1, j) + d_{i - 1} d_k d_j \}  \; \;, \qquad k = i, \cdots, j - 1 \]

      

    توجه داشته باشید که اگر i < j نباشد منطق حکم می‌کند که $ Mult(i, j) $ صفر شود.

    با توجه به توضیحات فوق، بدنه‌ی تابع Mult در حالت کلی به این صورت خواهد بود:

      

int Mult(int i, int j){
  int min;
  min = minimum of { Mult(i, k) + Mult(k + 1, j) + d[i - 1] * d[k] * d[j] } for k = i, i + 1, i + 2, . . . , j - 1;
  return min;
}

      

    در این تابع ابعاد ماتریس‌ها در فرم آرایه‌ی d به صورت عمومی تعریف شده‌اند. ثابت شده است مرتبه‌ی اجرای چنین تابعی $ O(3^n)$ است. به نظر می‌رسد که این روش کارا نیست. علت آن هم وجود همپوشانی است که در ادامه به آن می‌پردازیم.

      

استفاده از روش حریصانه

  [بازگشت به فهرست]

همانگونه که عنوان شد، در ضرب دو ماتریس $ M_{R \times L} $ و $ N_{L \times C} $ تعداد $ R \times L \times C $ عمل ضرب انجام می‌شود و حاصل ماتریسی با ابعاد $ R \times C $ است. پس اگر این حاصلضرب در ماتریس جدیدی ضرب شود، مقدار L نقشی نخواهد داشت. از این تحلیل این ایده مطرح می‌گردد که در ضرب زنجیره‌ای ماتریس‌ها ابتدا بهتر است ابعاد بزرگ را از زنجیره حذف کنیم. به عنوان مثال در ضرب $ A_{ 1 \times 3} \times B_{3 \times 2} \times C_{2 \times 5 } $ ابتدا ضرب $ D_{ 1 \times 2 } = A_{ 1 \times 3} \times B_{3 \times 2} $ انجام شده و سپس $ D_{ 1 \times 2 } \times C_{2 \times 5 } $ محاسبه شود. این ترتیب ضرب نسبت به ترتیب $ A_{ 1 \times 3} \times (B_{3 \times 2} \times C_{2 \times 5 }) $ عملیات ضرب کمتری دارد. چنین الگوریتمی همواره به پاسخ درست منتهی نمی‌شود. در مثال ابتدای نوشته مشخص شد که محاسبه‌ی $ (A_{3 \times 7} \times B_{7 \times 8 }) \times C_{8 \times 4} $ تعداد ضرب کمتری نسبت به $ A_{3 \times 7} \times (B_{7 \times 8 } \times C_{8 \times 4}) $ نیاز دارد؛ اما بر اساس ایده‌ی مطرح شده ترتیب $ A_{3 \times 7} \times (B_{7 \times 8 } \times C_{8 \times 4}) $ برای ضرب انتخاب می‌شود.

  

استفاده از روش برنامه‌نویسی پویا

  [بازگشت به فهرست]

    حال به سراغ برنامه‌نویسی پویا رفته و دو شرط لازم این روش برای حل مسائل بهینه‌سازی را بررسی می‌کنیم:

    1- همپوشانی: برای بررسی وجود همپوشانی در تابع فوق دو روش وجود دارد. اول اینکه درخت فراخوانی‌های بازگشتی تابع را به ازای یک n کوچک رسم کرده و فراخوانی‌های تکراری را مشاهده کنید. دومین روش این است که به مرتبه تعداد فراخوانی‌ها توجه کنید. با توجه به اینکه مقادیر i و j اعداد طبیعی کوچکتر از n هستند، تعداد کل حالت‌های فراخوانی تابع Mult با پارامترهای مختلف از مرتبه‌ی $O(n^2)$ خواهد بود. در حالی که ثابت شده است تعداد کل فراخوانی‌های تابع از مرتبه‌ی $ O(3^n)$ است. این اختلاف تنها می‌تواند ناشی از فراخوانی‌های تکراری باشد.

    2- اصل بهینگی: اگر بنا باشد پرانتزبندی کل عبارت بهینه شود، پرانتزبندی زیرمسئله‌ها هم باید بهینه باشند. یعنی بهینه بودن مسئله، بهینه بودن زیرمسئله‌ها را ایجاب می‌کند.

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

    در روش برنامه‌نویسی پویا اغلب از یک آرایه برای ذخیره نتایج جهت استفاده‌ی مجدد استفاده شده و زیرمسائل به صورت جزء به کل حل می‌شوند. در مورد این مسئله، ابتدا زیرمسائلی که تنها از دو ماتریس تشکیل شده‌اند محاسبه می‌شوند. سپس زیرمسائلی که از سه ماتریس تشکیل شده‌اند محاسبه می‌شوند. این دسته از زیرمسائل به زیرمسائلی متشکل از دو ماتریس تجزیه می‌شوند که قبلا محاسبات آنها صورت گرفته و نتایج آنها در آرایه ذخیره شده‌اند. در نتیجه نیاز به محاسبه‌ی مجدد آنها نیست. به همین ترتیب در مرحله‌ی بعد زیرمسائل با چهار ماتریس محاسبه می‌شوند و الی آخر.

    برای پیاده‌سازی این روش، آرایه‌ی دو بعدی M را منطبق با عملکرد تابع Mult تعریف می‌کنیم:

      

M[i][j] = Min { M[i][k] + M[k + 1][j] + d[ i] * d[k + 1] * d [j] }
   i ≤ k ≤ j - 1, 0 < i < j < n + 1, M[i][i] = 0

      

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

      

int Mult(int n){
  int i, j;
  for(i = 1 ; i <= n ; i++)
    M[i][i] = 0;
  for(i = 1 ; i < n ; i++)
    for(j = 1 ; j <= n - i ; j++)
       M[j][i + j] = Minimum of { M[i][k] + M[k + 1][j] + d[i - 1] * d[k] * d[j] } for k = i, i + 1, i + 2, ..., j - 1
  return M[1][n];
}

      

    تابع مقدار [M[1][n را باز می‌گرداند که همان تعداد ضربهای لازم جهت محاسبه‌ی ضرب زنجیره‌ای n ماتریس در حالت پرانتزبندی بهینه است. این تابع دو حلقه‌ی تکرار دارد که مرتبه‌ی $ O(n^2)$ را نشان می‌دهند. اما یافتن مینیمم داده‌ها درون حلقه‌ی داخلی نیز وجود دارد که از مرتبه‌ی $O(n)$ است. در نتیجه مرتبه‌ی کل تابع فوق $O(n^3)$ خواهد بود که در مقایسه با $O(3^n)$ بهبود چشم‌گیری را نشان می‌دهد.

    مزیت دیگر این روش - که از اصل بهینگی ناشی می‌شود - این است که با انجام این محاسبات، نه تنها مسئله‌ی اصلی که حالت بهینه‌ی همه‌ی زیرمسائل حل شده است. به عنوان نمونه، [M[2][4 تعداد ضرب‌های لازم در پرانتزبندی بهینه‌ی ماتریس‌های دوم تا چهارم را نشان می‌دهد.

    در پایان باید توجه داشته باشید که:

    1- در دو تابعی که اینجا آورده شده است، تنها تعداد ضرب‌های لازم در پرانتزبندی بهینه محاسبه گشته و شیوه‌ی پرانتزبندی مد نظر نیست.

    2- به نظر می‌رسد روش برنامه‌نویسی پویا از روش تقسیم و حل قدرتمندتر است! اما همیشه اینگونه نیست. ما در همه حال باید به دو شرط اساسی امکان استفاده از برنامه‌نویسی پویا جهت طراحی الگوریتم توجه داشته باشیم. در بسیاری از مسائل این دو شرط برقرار نیستند و ممکن است طراحی الگوریتم حل آنها با استفاده از روش تقسیم و حل کاراتر باشد.


این نوشته آخرین بار در تاریخ مورد بازنویسی علمی قرار گرفته است.
نوشته‌های مرتبط
        بررسی مسئله‌ی انتخابات، از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2016 سایت تهران
        معرفی کتاب Concrete Mathematics برای علاقه‌مندان حل سوالات الگوریتمی و شرکت‌کنندگان مسابقات برنامه‌نویسی
        بررسی مسئله‌ی اعداد اردوش (Erdos Numbers) یا فاصله‌ی همکاری اردوش از سوالات آمادگی مسابقات برنامه‌نویسی موجود در کتاب Programming Challenges و وبسایت UVa Online Judge
        آشنایی با الگوریتم استراسن برای محاسبه‌‌ی حاصلضرب ماتریس‌ها
        بررسی مسئله‌ی حداکثر مجموع، از سوالات آمادگی مسابقات برنامه‌نویسی
        بررسی روش‌های بسط لاپلاس، گاوس، فرمول تحویل و ساروس، برای محاسبه‌ی دترمینان ماتریس مربعی و پیچیده‌گی زمانی آنها
        بررسی الگوریتم‌های محاسبه‌ی دنباله‌ی اعداد فیبوناچی و کارایی آنها
        آشنایی با روش مرتب‌سازی ادغامی با قطعه کدهایی به زبان برنامه‌نویسی ++C
        آشنایی با الگوریتم فلوید-وارشال برای یافتن کوتاهترین مسیرهای گراف با قطعه کد نمونه به زبان برنامه‌نویسی ++C
        آشنایی با روش مرتب‌سازی سریع، همراه با قطعه کدهای نمونه به زبان برنامه‌نویسی ++C
پیوند کوتاه صفحه دسته‌بندی
امتیاز نوشته
  • 1
  • 2
  • 3
  • 4
  • 5
ارسال پیام

نام: *  

پست الکترونیک:

وبگاه:

متن پیام: *

right 01 02 03 04 05 06 07 08 09 10 11 12 13 14 left

 


» shamisa

پنجشنبه، ۲۵ آذر ماه ۱۳۹۵، ساعت ۱۲:۰۳
سلام
بسیار مفید بود
سپاسگزارم01010101

» پانیذ

شنبه، ۲۹ آذر ماه ۱۳۹۳، ساعت ۰۳:۰۰
سلام
ضمن تشکر از مطالب آموزندتون یه اشکال ریز تو این مطلب به چشمم خورد گفتم بگم
همون اول مطلب که تعداد ضرب های ماتریس های A B C رو محاسبه میکنید تو راه حل دوم باید نوشته بشه:
( A x B ) x C : 3 x 7 x 8 + 3 x 8 x 4 = 264
چونکه تعداد ستون های ماتریس C  برابر 4 هست نه 3

البته این تغییر تاثیر تو جواب نهایی که کمتر بودن تعداد ضرب ها توی حالت دومه ، نمیذاره...
بازم ممنون بابت آموزش های جامع تون


شنبه، ۲۹ آذر ماه ۱۳۹۳، ساعت ۱۳:۳۵
مسعود:
سلام
ممنون از لطف و تذکرتون. اصلاح شد.

» taniya

شنبه، ۵ بهمن ماه ۱۳۹۲، ساعت ۱۹:۲۶
الگوريتم بهينه سازي ترتيب ضرب ماتريسي را پياده سازي و براي ماتريسهاي با ابعاد مشخص داده شده، از طریق پرانتزگذاري، ترتيب بهينه را نشان دهيد
لطفا کمکم کنید

» فرزانه

شنبه، ۱۶ دی ماه ۱۳۹۱، ساعت ۱۰:۰۱
سلام خواهش میکنم کمکم کنین
من یه پروزه دارم واسه 20 دی ماه باید ارائه بدم که در اون مرتبه زمانی کوله پشتی از (o(n2  به مرتبه (o(n   برسه
لطفا کمکم کنین
0707070707

» money71

پنجشنبه، ۱۴ دی ماه ۱۳۹۱، ساعت ۱۲:۲۴
در کد الگوریتم پویا باید به جای d[j]  قرار دهید d[i+j]

» سایه

سه‌شنبه، ۱۲ دی ماه ۱۳۹۱، ساعت ۱۳:۳۶
لطفا جواب سوالاتم رو بدید خیلی نیاز دارم.

1-الگوریتم کروسکال را تحلیل کرده و نحوه تشخیص دور را در آن مشخص کنید؟

2-شبه کد الگوریتم ضرب زنجیره ای را به همراه مرتبه ی زمانی آن پیدا کنید؟و تعیین کنید برای ضرب زنجیره ایn  ماتریس چند بار ارجاع به ماتریس هزینه انجام میشود؟

» کاظم

یکشنبه، ۱۲ آذر ماه ۱۳۹۱، ساعت ۲۳:۵۸
سلام
لطفا در مورد تجزیه ماتریس ها توضیح  داده شود.
با تشکر

» منا

جمعه، ۱۱ آذر ماه ۱۳۹۰، ساعت ۱۸:۳۷
سلام ، لطفا منابع مهم و کاربردی طراحی الگوریتم را درصورت امکان برایم میل کنید، شدیدا نیازمند این منابع هستم،ممنون

» همایون

یکشنبه، ۱ خرداد ماه ۱۳۹۰، ساعت ۰۱:۲۰
اگه ممکنه کمکم کنید. سورس ضرب زنجیره ای ماتریس ها رو با لیست پیوندی توسط برنامه های سی یا سی ++ رو بذارین تو سایت.ممنون

» رسول منصوری

جمعه، ۱۶ اردیبهشت ماه ۱۳۹۰، ساعت ۱۷:۵۳
سلام دوست عزیز خسته نباشید من یک کارمند هستم و وقت مطالعه به اندازه کافی ندارم لطفا به من در تهیه این پروژه ها کمک کنید---------------------ضرب اعداد بزرگ با تقسیم و غلبه -------ضرب زنجیره ای ماتریسها با برنامه نویسی پویا -------الگوریتم ضرب استراسن با تقسیم و غلبه

» fatemeh

شنبه، ۱۴ آذر ماه ۱۳۸۸، ساعت ۱۲:۲۰
سلام
می خواستم اگه ممکنه برتامه ای که الگوریتم ضرب ذنجیره ای ماتریس ها رو پیاده سازی کرده باشه تو سایتتون بزارید