پاورپوینت برنامه نویسی پویا

بخشی از پاورپوینت

اسلاید 1 :

فصل سوم:
برنامه نویسی پویا

اسلاید 2 :

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

اسلاید 3 :

مراحل بسط یک الگوریتم برنامه نویسی پویا به شرح زیر است:
1- ارائه یک ویژگی بازگشتی برای حل نمونه ای از مسئله .
2- حل نمونه ای از مسئله به شیوه جزء به کل با حل نمونه های کوچک تر.

اسلاید 4 :

ضريب دوجمله اي با استفاده از تقسيم و حل
فرمول مرسوم بدست آوردن ضريب دو جمله اي براي كليه مقادير n ≥ k ≥0 بصورت روبرو است:
اما همانطور كه مشاهده مي كنيد، بدليل استفاده از عمل فاكتوريل ، حتي براي مقادير كوچك متغيرهاي k و n ، مقدار k! و يا n! بزرگ (و يا حتي بسيار بزرگ) خواهد بود.
پس ما نمي توانيم ضريب دوجمله اي را مستقيماً از اين روش بدست آوريم.

اسلاید 5 :

ضريب دوجمله اي با استفاده از تقسيم و حل
با استفاده از فرمول زير نياز به محاسبه ي n! و يا k! را به (n-1)! و يا (k-1)! تقليل مي دهيم.
0 < k < n
K = 0 يا k = n
همانطور كه ملاحظه مي كنيد، براي محاسبه ي اين عبارت، آن را به دو عبارت كوچكتر تبديل مي كنيم و به محاسبه ي آنها مي پردازيم.
پس همانطور كه ملاحظه مي كنيد به الگوريتم تقسيم و حل مي رسيم.

اسلاید 6 :

ضريب دوجمله اي با استفاده از تقسيم و حل
الگوريتم محاسبه ضريب دو جمله اي در اين روش با استفاده از متد بازگشتي بصورت زير مي باشد:
int bin (int n, int k)
{
if (k == 0 || n == k)
return 1;
else
return bin(n-1, k-1) + bin(n-1, k);
}
ورودي ها: اعداد صحيح و مثبت n و k هستند كه در آن k ≤ n است.
خروجي ها: ضريب دو جمله اي n و k بصورت يك عدد صحيح.

اسلاید 7 :

ضريب دوجمله اي با استفاده از تقسيم و حل
حال با استفاده از يك مثال به توضيح اين الگوريتم مي پردازيم.
فرض كنيد قرار است با استفاده از اين الگوريتم ضريب دو جمله اي (2 ،4) را محاسبه كنيم.
پس n = 4 و k = 2 خواهد بود، بنابراين تابع ما بصورت زير فراخواني خواهد شد:
bin (4, 2)
(بدليل استفاده از فراخواني هاي بازگشتي و درك موضوع، درخت اين سلسله فراخواني ها را ترسيم مي كنيم.)

اسلاید 8 :

ضريب دوجمله اي با استفاده از تقسيم و حل
bin (4, 2)
bin (3,1)
bin (3, 2)
bin (2, 0)
bin (2, 1)
bin (2, 1)
bin (2, 2)
bin (1, 0)
bin (1, 1)
bin (1, 0)
bin (1, 1)

اسلاید 9 :

ضريب دوجمله اي با استفاده از تقسيم و حل
اما همانطور كه مشاهده مي كنيد، در فراخواني هاي بازگشتي، تعدادي از نمونه ها چندين بار حل مي شوند و بطور جداگانه محاسبه مي شوند.
bin (4, 2)
bin (3,1)
bin (3, 2)
bin (2, 0)
bin (2, 1)
bin (2, 1)
bin (2, 2)
bin (1, 0)
bin (1, 1)
bin (1, 0)
bin (1, 1)

اسلاید 10 :

ضريب دوجمله اي با استفاده از تقسيم و حل
هماننده آنچه مشاهده كرديد براي محاسبه bin(n-1, k-1) و bin(n-1, k) هر دو نياز به نتيجه ي bin(n-2, k-1) دارند و اين مورد در هر باز فراخواني به طور جداگانه اي محاسبه مي شود.
پس در روش تقسيم و حل تا زماني كه نمونه به چند نمونه كوچكتر تقسيم شود كه آن نمونه ها تقريباً به بزرگي نمونه اوليه باشند، اين الگوريتم كارايي ندارد، آنچنانكه براي تعيين نياز به محاسبه ي جمله خواهد بود.
حال با استفاده از الگوريتم پويا، الگوريتمي با كارايي بيشتر و بالاتر طراحي ميكنيم.

اسلاید 11 :

ضريب دوجمله اي با استفاده از برنامه نويسي پويا
با استفاده از همان فرمولي كه در الگوريتم قبلي بيان كرديم:
0 < k < n
K = 0 يا k = n
اين بار با استفاده از برنامه نويسي پويا پياده سازي مي كنيم.
با آرايه اي دو بعدي مثلاً با نام B كه B[i][j] مبين است.
0 < j < i
j = i يا j = 0

اسلاید 12 :

ضريب دوجمله اي با استفاده از برنامه نويسي پويا
مسئله را به شيوه ي جزء به كل حل كرده و به پيش مي رويم.
سلولهاي آرايه را به ترتيب از سطر و ستونهاي كوچك شروع كرده و به جلو ميرويم، تا آنجا كه به B[n][k] كه همان است برسيم.

اسلاید 13 :

الگوریتم 2-3: ضریب دو جمله ای با استفاده از برنامه نویسی پویا
int bin2 ( int n , int k )
{
index i , j ;
int B [0..n][0..k]
for ( i = 0; i ≤ n ; i ++)
if ( j == 0 || j == i )
B [i] [j] = 1;
else
B [i] [j] = B [ i – 1 ] [ j -1 ] + B [ i -1 ] [j];
return B[n] [k]:
}

اسلاید 14 :

ضريب دوجمله اي با استفاده از برنامه نويسي پويا
حال با ذكر يك مثال به توضيح اين الگوريتم نيز مي پردازيم.
فرض كنيد بخواهيم ضريب دوجمله اي (4, 2) را اين بار با استفاده از اين الگوريتم بدست آوريم.
همانطور كه مي دانيد: n = 4 و k = 2
B[0][0] = 1
B[1][0] = 1
B[1][1] = 1
B[2][0] = 1
B[2][1] = B[1][0]+B[1][1]
= 1 + 1 = 2
B[2][2] = 1
B[3][0] = 1
B[4][0] = 1
B[3][1] = B[2][0]+B[2][1]
= 1 + 2 = 3
B[3][2] = B[2][1]+B[2][2]
= 2 + 1 = 3
B[4][1] = B[3][0]+B[3][1]
= 1 + 3 = 4
B[4][2] = B[3][1]+B[3][2]
= 3 + 3 = 6

اسلاید 15 :

ضريب دوجمله اي با استفاده از برنامه نويسي پويا
همانطور كه مشاهده كرديد با استفاده از آرايه اي دو بعدي و الگوريتم برنامه نويسي پويا به حل مسئله پرداختيم.
ديديم كه در اين روش برخلاف روش قبلي سربار اضافي نداشتيم (محاسبه ي مجدد موردهاي محاسبه شده) چرا كه اين الگوريتم جزء به كل بوده و براي محاسبه مقادير جديد مورد نياز، آنها را از مقادير قبلي بدست مي آورد. (نه آنكه مجدداً به محاسبه آنها از نو بپردازد)
در نهايت به مقايسه ي كارايي دو الگوريتم مي پردازيم.

اسلاید 16 :

مقايسه الگوريتم هاي ضريب دوجمله اي
همانطور كه قبلاً بيان شد، در الگوريتم تقسيم و حل، تعداد جملاتي كه الگوريتم براي تعيين محاسبه مي كند است.
اين در حالي است كه تعداد كل گذرها در الگوريتم برنامه نويسي پويا با اثبات زير برابر خواهد بود.

تعداد گذرها از حلقه j : 1+2+3+4+.+k+(k+1)+(k+1)+.+(k+1)
پس:
n-k+1 بار

اسلاید 17 :

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

اسلاید 18 :

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

مسئله کو تاه ترین مسیر که یک مسئله بهینه سازی می باشد شامل موارد زیر است:
از یک نود به نود دیگر
از یک نود به تمامی نودها
از تمامی نودها به همدیگر

اسلاید 19 :

روش محاسبه تمامی مسیرها
فرض کنید از هر راس به همه رئوس دیگر یک یال وجود دارد
در این صورت , زیر مجموعه ای از همه مسیر ها , عبارت از مجموعه ای خواهد بود که راس نخست شروع می شود و به راسی دیگر ختم می شود واز همه رئوس دیگر عبور می کنند. چون راس دوم در چنین مسیری می تواند هر یک از n-2 راس باشد, راس سوم در چنین مسیری می تواند هر یک ازn-3 راس باشد, . وراس دومی به آخری روی چنین مسیری فقط می تواند یک راس باشد, تعداد کل مسیرها از یک راس که از همه رئوس دیگر بگذرد

(n-2)(n-3)…1=(n-2)!

اسلاید 20 :

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