گروه بندی کلیه مطالب

مطالب تخصصی ریاضی در سایت تخصصی رایشمند

برنامه ریزی پویا
مدیر ارشد سایت
/ دسته ها: کتابخانه ریاضی

برنامه ریزی پویا

Dynamic Programming

این کتاب توسط کاربر گرامی نیما علیرضازاده در قسمت همکاری با رایشمند ارسال شده است.بدین وسیله از ایشان کمال سپاس را داریم


در ﻋﻠﻮم ﮐﺎﻣﭙﯿﻮﺗﺮ، ﺑﺮﻧﺎﻣﻪرﯾﺰیِ ﭘﻮﯾﺎ یک روش بهینه سازی است که برای دسته ای از الگوریتم های پس گرد زمانی که زﯾﺮﻣﺴﺄﻟﻪﻫﺎ ﺑﻄﻮر ﻣﮑﺮر ﻓﺮاﺧﻮاﻧﯽ ﻣﯽﺷﻮﻧﺪ اﺳﺘﻔﺎده ﻣﯽﺷﻮد. اﯾﻦ روش در ﺳﺎل ١٩۵٣ ﺗﻮﺳﻂ رﯾﺎﺿﯽداﻧﯽ ﺑﻪ ﻧﺎم رﯾﭽﺎرد ﺑﻠﻤﻦ ﻣﻌﺮﻓﯽ ﺷﺪ. ﺑﺮﻧﺎﻣﻪرﯾﺰیِ ﭘﻮﯾﺎ در رﯾﺎﺿﯽ و ﻋﻠﻮم ﮐﺎﻣﭙﯿﻮﺗﺮ روﺷﯽ ﺷﻨﺎﺧﺘﻪ ﺷﺪه اﺳﺖ ﮐﻪ از آن در ﻧﻮﺷﺘﻦ اﻟﮕﻮرﯾﺘﻢﻫﺎی ﺑﻬﯿﻨﻪ ﺑﺎ اﺳﺘﻔﺎده از ﺣﺬف اﺟﺮای ﭼﻨﺪ ﺑﺎرۀ ﯾﮏ زﯾﺮ ﻣﺴﺄﻟﻪ ﯾﮑﺴﺎن اﺳﺘﻔﺎده ﻣﯽﺷﻮد. ﺗﻌﺮﯾﻒ ﺑﺮﻧﺎﻣﻪرﯾﺰیِ ﭘﻮﯾﺎ در رﯾﺎﺿﯽ و ﻋﻠﻮم ﮐﺎﻣﭙﯿﻮﺗﺮ ﻣﺘﻔﺎوت اﺳﺖ. ﻧﺸﺎن داده ﺷﺪه اﺳﺖ ﮐﻪ روش ﻋﻠﻮم ﮐﺎﻣﭙﯿﻮﺗﺮی ﺑﺮای ﺑﺮﻧﺎﻣﻪرﯾﺰیِ ﭘﻮﯾﺎ ﮐﺎرآﯾﯽ ﺑﺎﻻﺗﺮی دارد زﯾﺮا ﻣﺤﺎﺳﺒﺎت ﺗﮑﺮاری را ﺣﺬف ﻣﯽﮐﻨﺪ در ﺣﺎﻟﯽ ﮐﻪ در روش رﯾﺎﺿﯽ ﺑﺮﻧﺎﻣﻪرﯾﺰیِ ﭘﻮﯾﺎ اﻣﮑﺎن ﮐﺎﻫﺶ ﻓﻀﺎی ﺣﺎﻓﻈﻪ ﺑﯿﺸﺘﺮ اﺳﺖ.
دقت کنید که کلمه پویا را ﻧﺒﺎﯾﺪ ﺑﺎ زﺑﺎن های ﺑﺮﻧﺎﻣﻪﻧﻮﯾﺴﯽ ﭘﻮﯾﺎ ﻧﻈﯿﺮ LISP و Scheme اﺷﺘﺒﺎه ﮔﺮﻓﺖ. ﻫﻤﭽﻨﯿﻦ ﮐﻠﻤﻪﺑﺮﻧﺎﻣﻪرﯾﺰی رﺑﻄﯽ ﺑﻪ ﻣﺒﺤﺚ ﺑﺮﻧﺎﻣﻪﻧﻮﯾﺴﯽ ﮐﺎﻣﭙﯿﻮﺗﺮی ﻧﺪارد. در ﻣﺒﺤﺚ اﻟﮕﻮرﯾﺘﻢ، ﺑﺮﻧﺎﻣﻪرﯾﺰیِ ﭘﻮﯾﺎ ﺑﻪ ﺗﮑﻨﯿﮑﯽ اﺷﺎره ﻣﯽﮐﻨﺪ ﮐﻪﯾﮏ ﺟﺪول را ﺑﺎ اﺳﺘﻔﺎده از ﻣﻘﺎدﯾﺮ ﻣﻮﺟﻮد در ﺳﺎﯾﺮ ﺟﺪاول ﺗﮑﻤﯿﻞ ﻣﯽﮐﻨﺪ. دﻟﯿﻞ اﺳﺘﻔﺎده از ﮐﻠﻤﻪ ﭘﻮﯾﺎ آن اﺳﺖ ﮐﻪ ﻣﻘﺎدﯾﺮ ﯾﮏﺟﺪول ﺑﺎ اﺳﺘﻔﺎده از ﻣﻘﺎدﯾﺮ ﻣﻮﺟﻮد در ﺳﺎﯾﺮ ﺟﺪاول ﻣﺤﺎﺳﺒﻪ ﻣﯽﺷﻮﻧﺪ. ﻫﻤﭽﻨﯿﻦ ﺑﻪ دﻟﯿﻞ اﺳﺘﻔﺎده از ﺟﺪاول ﺑﻪ آن ﺑﺮﻧﺎﻣﻪرﯾﺰیﻣﯽﮔﻮﯾﻨﺪ؛ ﻣﺸﺎﺑﻪ ﺟﺪول ﺑﺮﻧﺎﻣﻪﻫﺎ ﮐﻪ ﺗﻮﺳﻂ ﺷﺒﮑﻪﻫﺎی ﺗﻠﻮﯾﺰﯾﻮﻧﯽ اراﺋﻪ ﻣﯽﺷﻮد.
ﺑﺮﻧﺎﻣﻪرﯾﺰیِ ﭘﻮﯾﺎ ﺷﺒﯿﻪ روش ﺗﻘﺴﯿﻢ و ﺣﻞ ﻣﺴﺎﺋﻞ را ﺑﺎ اﺳﺘﻔﺎده از ﺗﺮﮐﯿﺐ ﮐﺮدن ﺟﻮاب زﯾﺮﻣﺴﺄﻟﻪﻫﺎ ﺣﻞ ﻣﯽﮐﻨﺪ.اﻟﮕﻮرﯾﺘﻢﻫﺎی ﺗﻘﺴﯿﻢ و ﺣﻞ ، ﻣﺴﺄﻟﻪ را ﺑﻪ زﯾﺮ ﻣﺴﺄﻟﻪﻫﺎی ﻣﺴﺘﻘﻞ ﺗﻘﺴﯿﻢ ﻣﯽﮐﻨﺪ و ﭘﺲ از ﺣﻞ زﯾﺮ ﻣﺴﺄﻟﻪﻫﺎ ﺑﻪ ﺻﻮرت ﺑﺎزﮔﺸﺘﯽ، ﻧﺘﺎﯾﺞ را ﺑﺎ ﻫﻢ ﺗﺮﮐﯿﺐ ﮐﺮده و ﺟﻮاب ﻣﺴﺄﻟﻪ اﺻﻠﯽ را ﺑﺪﺳﺖ ﻣﯽآورد. ﺑﻪ ﻋﺒﺎرت دﻗﯿﻖﺗﺮ، ﺑﺮﻧﺎﻣﻪرﯾﺰیِ ﭘﻮﯾﺎ در ﻣﻮاردی ﻗﺎﺑﻞاﺳﺘﻔﺎده اﺳﺖ ﮐﻪ زﯾﺮﻣﺴﺄﻟﻪﻫﺎ ﻣﺴﺘﻘﻞ ﻧﯿﺴﺘﻨﺪ؛ ﯾﻌﻨﯽ زﻣﺎﻧﯽ ﮐﻪ زﯾﺮﻣﺴﺄﻟﻪﻫﺎ دارای زﯾﺮ-زﯾﺮ ﻣﺴﺄﻟﻪﻫﺎی ﯾﮑﺴﺎن ﻫﺴﺘﻨﺪ. در اﯾﻦ ﺣﺎﻟﺖ روش ﺗﻘﺴﯿﻢ و ﺣﻞ ﺑﺎ اﺟﺮای ﻣﮑﺮر زﯾﺮﻣﺴﺄﻟﻪﻫﺎی ﯾﮑﺴﺎن، ﺑﯿﺸﺘﺮ از ﻣﯿﺰان ﻻزم ﻣﺤﺎﺳﺒﺎت اﻧﺠﺎم ﻣﯽدﻫﺪ. ﯾﮏاﻟﮕﻮرﯾﺘﻢ ﺑﺮﻧﺎﻣﻪرﯾﺰیِ ﭘﻮﯾﺎ زﯾﺮﻣﺴﺄﻟﻪﻫﺎ را ﯾﮏ ﺑﺎر ﺣﻞ و ﺟﻮاب آﻧﻬﺎ را در ﯾﮏ ﺟﺪول ذﺧﯿﺮه ﻣﯽﮐﻨﺪ و ﺑﺎ اﯾﻦ ﮐﺎر از ﺗﮑﺮاراﺟﺮای زﯾﺮﻣﺴﺄﻟﻪﻫﺎ در زﻣﺎﻧﯽ ﮐﻪ ﻣﺠﺪداً ﺑﻪ ﺟﻮاب آﻧﻬﺎ ﻧﯿﺎز اﺳﺖ ﺟﻠﻮﮔﯿﺮی ﻣﯽﮐﻨﺪ.

سرفصل های کتاب به شرح زیر می باشد؛

  1. برنامه ریزی خط تولید
  2. ضرب زنجیر ماتریس ها
  3. مبانی برنامه ریزی پویا
  4. طولانی ترین زیر دنباله مشترک
  5. درخت های جستجوی دودویی بهینه
مطلب قبلی روش هایی برای پیدا کردن باقیمانده تقسیم
مطلب بعدی 100 مسئله از ترکیبیات
چاپ
1791 رتبه بندی این مطلب:
2/0
نوعکتاب
مقطعکارشناسی
گرایشریاضیات و کاربردها
زبانفارسی
نوع کاربرددرسی - دانشگاه
نویسندهمحمد فرشی
سال انتشار1390
نوع فایل
  • Pdf
صفحه 47
 

مدیر ارشد سایتمدیر ارشد سایت

سایر نوشته ها توسط مدیر ارشد سایت

نوشتن یک نظر

نام:
ایمیل:
نظر:
افزودن نظر