بخشی از پاورپوینت
اسلاید 1 :
روش برنامه نویسی پویا
Dynamic Programming
فصل سوم
درس طراحی الگوریتم ها
اسلاید 2 :
برنامه نویسی پویا (dynamic programming)
یک روش حل مسائل بزرگ و سخت، تقسیم کردن آن به تعدادی نمونه مسئله کوچکتر و سپس حل و ترکیب جواب آنهاست (مثل مرتب سازی ادغامی).
در برخی مسائل زیرمسئله ها مستقل از هم نیستند یعنی زیرمسئله های کوچکتر مشترکی دارند.
در اینگونه مسائل، روش تقسیم و غلبه ناکارآمد است زیرا زیر مسئله ها همواره مستقل فرض شده و در نتیجه هر زیرمسئله مشترک را چندین مرتبه حل می کند (مثلاً الگوریتم بازگشتی فیبوناچی).
برنامه نویسی پویا عملکردی شبیه به تقسیم و غلبه دارد با این تفاوت که هر زیر مسئله را فقط یک بار حل می کند و جواب آن را در یک آرایه جدولی ذخیره می کند.
برنامه نویسی پویا همانند تقسیم و حل، مسئله را با ترکیب جوابهای به دست آمده برای زیرمسئله ها حل می کند.
درس طراحی الگوریتمها - فصل سوم: روش برنامه نویسی پویا - مدرس: بیدکی
اسلاید 3 :
مراحل روش dynamic programming
برنامه نویسی پویا یک روش جزء به کل یا پایین به بالا (bottom-up) است.
به عبارتی تقسیم یک مسئله به زیر مسئله ها با توجه به زیرمسئله های قبلی حل شده، تا جایی که لازم است انجام می شود (بازگشت غیر کورکورانه).
مراحل بسط یک الگوریتم برنامه نویسی پویا
ارائه یک ویژگی بازگشتی برای حل نمونه ای از مسئله
حل نمونه ای از مسئله به شیوه جزء به کل با حل نمونه های کوچکتر
برنامه ریزی برای ایجاد یک جدول به منظور نگهداری جواب زیرمسئله ها
درس طراحی الگوریتمها - فصل سوم: روش برنامه نویسی پویا - مدرس: بیدکی
اسلاید 4 :
ضریب دوجمله ای
محاسبه ضریب دوجمله ای
برای مقادیر بزرگ n و K ضریب دوجمله ای را نمی توان مستقیم از این رابطه بدست آورد زیرا محاسبه n! برای مقادیر نه چندان بزرگ هم وقت گیر است.
استفاده از رابطه بازگشتی
درس طراحی الگوریتمها - فصل سوم: روش برنامه نویسی پویا - مدرس: بیدکی
اسلاید 5 :
مثال از ضریب دوجمله ای
مثال: محاسبه
درس طراحی الگوریتمها - فصل سوم: روش برنامه نویسی پویا - مدرس: بیدکی
اسلاید 6 :
حل با روش Divide & conquer
این الگوریتم از کارایی پایینی برخوردار است.
تعداد فراخوانی ها در الگوریتم برای تعیین برابر است با:
درس طراحی الگوریتمها - فصل سوم: روش برنامه نویسی پویا - مدرس: بیدکی
اسلاید 7 :
اثبات به وسیله استقرا
تعداد فراخوانی ها در روش تقسیم و غلبه
T(n, k) = T(n-1 , k-1) + T(n-1 , k) + 1
درس طراحی الگوریتمها - فصل سوم: روش برنامه نویسی پویا - مدرس: بیدکی
اسلاید 8 :
مثال از ضریب دوجمله ای
مثال: محاسبه
درس طراحی الگوریتمها - فصل سوم: روش برنامه نویسی پویا - مدرس: بیدکی
اسلاید 9 :
حذف تکرار در محاسبات
استفاده از یک ساختمان داده به منظور نگهداری محاسبات پیشین
ایجاد ماتریس Bبرای ذخیره ضرایب
مراحل:
ایجاد یک ویژگی بازگشتی
حل نمونه ای از مسئله به شیوه پایین به بالا با محاسبه سطرهای B به طور متوالي با شروع از سطر اول
درس طراحی الگوریتمها - فصل سوم: روش برنامه نویسی پویا - مدرس: بیدکی
اسلاید 10 :
روند محاسبه
هر یک از سطرها از روی سطر قبلی خود محاسبه می شود.
مقادیر موجود در هر سطر را فقط تا ستون kام محاسبه می کنیم.
جواب نهایی در خانه B[n][k]
می دانیم که:
درس طراحی الگوریتمها - فصل سوم: روش برنامه نویسی پویا - مدرس: بیدکی
اسلاید 11 :
مثال
عناصر مورد نیاز در محاسبه c(n, k)
j = i
j = k
محاسبه c(4, 2)
درس طراحی الگوریتمها - فصل سوم: روش برنامه نویسی پویا - مدرس: بیدکی
اسلاید 12 :
الگوریتم غیربازگشتی
برای محاسبه عناصر ماتریس B نیاز به دو حلقه داریم.
ابتدا عناصری که مقادیر آنها از قبل مشخص است را پر می کنیم.
مقدار جواب که در خانه B[n][k] است را بدست می آوریم.
روش به کار گرفته شده در این الگوریتم به برنامه سازی پویا معروف است.
درس طراحی الگوریتمها - فصل سوم: روش برنامه نویسی پویا - مدرس: بیدکی
اسلاید 13 :
محاسبه هزینه الگوریتم
تعداد گذرها از حلقه j به ازای هر یک از مقادیر i
تعداد کل گذرها
درس طراحی الگوریتمها - فصل سوم: روش برنامه نویسی پویا - مدرس: بیدکی
اسلاید 14 :
مسائل بهینه سازی (optimization)
یافتن بهترین جواب ممکن برای مسئله
کوتاهترین، طولانی ترین،کمترین، بیشترین و .
برنامه نویسی پویا نمی تواند تمام مسائل بهینه سازی را حل کند مگر مسائلی که اصل بهینگی در آنها صدق کند.
گوییم اصل بهینگی در یک مسئله صدق میکند اگر یک حل بهینه برای نمونه ای از مسئله، همواره حاوی حل بهینه برای همه زیرنمونه ها باشد.
قبل از استفاده از برنامه نويسي پويا براي بدست آوردن راه حل، لازم است كه نشان دهيم اصل بهينگي برقرار است.
معمولا از برهان خلف برای اثبات استفاده می شود.
درس طراحی الگوریتمها - فصل سوم: روش برنامه نویسی پویا - مدرس: بیدکی
اسلاید 15 :
اصل بهینگی - مثال
اصل بهینگی در مسئله یافتن طولانی ترین مسیر ساده از هر رأس به تمام رئوس دیگر، برقرار نمی باشد.
مسیر بهینه (طولانی ترین) از v1 به v4 مسیر [v1, v3, v2, v4] می باشد.
زیرمسیر [v1, v3] بهینه نیست زیرا:
درس طراحی الگوریتمها - فصل سوم: روش برنامه نویسی پویا - مدرس: بیدکی
اسلاید 16 :
ضرب زنجیره ای ماتریس ها
هدف بسط الگوریتمی است که ترتیب بهینه را برای ضرب n ماتریس معین کند.
بدین معنی که کمترین تعداد عمل ضرب انجام شود.
برای ضرب یک ماتریس m*n در یک ماتریس n*p به تعداد m*n*p عمل ضرب نیاز است.
از ویژگی های ضرب ماتریس ها این است که ضرب ماتریس ها شرکت پذیر می باشد.
M = M1 * M2 * M3 * . . . * Mn
M = M1 * M2 * M3
M = (M1 * M2 ) * M3 = M1 * (M2 * M3 )
درس طراحی الگوریتمها - فصل سوم: روش برنامه نویسی پویا - مدرس: بیدکی
اسلاید 17 :
مثال
روش اول
روش دوم
درس طراحی الگوریتمها - فصل سوم: روش برنامه نویسی پویا - مدرس: بیدکی
اسلاید 18 :
مثال (ادامه)
روش سوم
روش چهارم
روش پنجم
درس طراحی الگوریتمها - فصل سوم: روش برنامه نویسی پویا - مدرس: بیدکی
اسلاید 19 :
الگوریتم Brute-force
در نظر گرفتن تمام ترتیب های ممکن و پیدا کردن حداقل ضرب های انجام شده
پیچیدگی این الگوریتم حداقل نمایی است
به طور کلی اگر
آنگاه تعداد حالات ممکن برای ضرب
درس طراحی الگوریتمها - فصل سوم: روش برنامه نویسی پویا - مدرس: بیدکی
اسلاید 20 :
روش تقسیم و غلبه
تمرین در خانه:
الگوریتم تقسیم و غلبه ضرب زنجیره ای ماتریس ها را بنویسید.
درس طراحی الگوریتمها - فصل سوم: روش برنامه نویسی پویا - مدرس: بیدکی
