advertise laitec sharif univercity
دانلود پروژه وب سایت هتل با HTML و ASP.NET

دانلود پروژه وب سایت هتل با HTML و ASP.NET

10000 تومان
دانلود پروژه مدیریت کتابخانه با سی شارپ و SQL سرور

دانلود پروژه مدیریت کتابخانه با سی شارپ و SQL سرور

10000 تومان
دانلود سورس پروژه سی شارپ شبیه سازی صف بانک تحت شبکه

دانلود سورس پروژه سی شارپ شبیه سازی صف بانک تحت شبکه

10000 تومان
دانلود سورس پروژه پایانی وب سایت بنگاه املاک با php

دانلود سورس پروژه پایانی وب سایت بنگاه املاک با php

68000 تومان
دانلود سورس اندروید اپلیکیشن افزایش سرعت گوشی

دانلود سورس اندروید اپلیکیشن افزایش سرعت گوشی

18000 تومان

روش برنامه نویسی پویا در طراحی الگوریتم

در الگوریتم برنامه نویسی پویا، ابتدا مسائل کوچک حل میشوند و در یک مکان ذخیره میشوند و سپس به تدریج به حل مسئله اصلی میرسیم. روش پویا یک روش جزء به کل یا پایین به بالا (bottom - up) است و بصورت بازگشتی به جواب میرسد
روش برنامه نویسی پویا در طراحی الگوریتم

روش برنامه نویسی پویا در طراحی الگوریتم

در طراحی الگوریتم ها، روش تقسیم و غلبه یک روش کل به جز یا بالا به پایین (top - down) بود. ولی روش برنامه نویسی پویا یک روش جزء به کل یا پایین به بالا (bottom - up) میباشد. در تکنیک تقسیم وغلبه از مسئله اصلی شروع میکردیم و سپس آن را به اجزای کوچکتر تقسیم میکردیم و تقسیم را تا زمانی ادامه میدادیم که به مسائل کوچک قابل حل برسیم و سپس با حل آنها به تدریج مسئله اصلی حل میشد.

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

شباهت تقسیم و غلبه و برنامه نویسی پویا این است که هر دو نیاز به یک رابطه بازگشتی دارند و تفاوت آنها این است که تقسیم وغلبه مسئله را از بالا به پایین حل میکند، در صورتی که برنامه نویسی پویا آن را از پایین به بالا حل میکند.

 

برای مثال، حل رابطه بازگشتی T(n) = T(n-1) +2  را با فرض T(1) = 1 به دو روش بالا به پایین و پایین به بالا ببینید:

روش اول (بالا به پایین) :

T(n) = T(n-1) +2 = ( T(n-2) +2 ) +2  

= T(n-3) +2 +2 +2 = T(n-3) + 3*2 =… =

= T(n- (n-1) ) + (n-1) *2 = T(1) + (n-1) *2 = 2n-1

روش دوم (پایین به بالا) :

T(1) = 1

T(2) = T(1) + 2 = 1 + 2 = 3

T(3) = T(1) + 2 = 3 + 2 = 5

T(4) = T(3) + 2 = 5 + 2 = 7

.

.

.

T(n) = 2n – 1

 

اگر بخواهیم جمله nام سری فیبوناچی را با روش برنامه نویسی پویا بیابیم، الگوریتم زیر را ارائه میدهیم:

int  fib (int n)

{

        int i , f [0…n];

        f[0] = 0;

        if (n>0)

        {

               f[1] = 1;

               for ( i=2 ; i<=n ; i++)

                          f[i] = f[i-1] + f[i-2];

        }

        return  f[n];

}

 

با توجه به الگوریتمی که مشاهده کردید در این الگوریتم به روش برنامه نویسی پویا ، مرتبه اجرایی θ(n) میباشد.

مسئله فیبوناچی بازگشتی دارای مرتبه نمایی و فیبوناچی غیربازگشتی دارای مرتبه خطی است چون در فیبوناچی بازگشتی زیر مسائل به هم ارتباط دارند. مثلا fib(3) و fib(4) هر دو دارای زیر مسائل مشترک هستند.

اصولا روش تقسیم و غلبه برای الگوریتم هایی مناسب است که زیر مسائل آنها با هم اشتراک نداشته باشند مثل مرتب سازی ادغامی که نمونه های تقسیم شده ارتباطی با هم ارتباط ندارند.

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

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

► مسائل را از پایین ترین سطح به طرف بالاترین سطح حل میکنیم (پایین به بالا).

► برخلاف روش تقسیم و حل که برای هر مسئله در سطح L تنها از مسائل سطح L-1 استفاده میکنیم، در روش برنامه سازی پویا، برای حل هر مسئله در سطح L میتوانیم از کلیه مسائل سطوح پایین تر که لازم باشد، استفاده کنیم.

► در هر سطح کلیه مسائل موجود آن سطح حل میگردند و نتایج نگهداری میشود.

توجه داشته باشید که در کلیه مسائل بهینه سازی که با روش برنامه سازی پویا قابل حل هستند باید اصل بهینگی (Principle  of  optimality) برقرار باشد. اصل بهینگی در صورتی برقرار است که زیر مسائل یک مسائل بهینه خود باشند. بعنوان مثال اگر کوتاهترین مسیر از a به b حتما از c میگذرد آنگاه باید مسیر از a به c و از c به b خود کوتاهترین باشند. ولی در مسئله یافتن طولانی ترین مسیر بین دو راس اصل بهینگی صادق نیست و نمیتوان آن را از طریق برنامه ریزی پویا حل کرد.

 

 



1
نظرات
  • user avatar حسین:
    ۱۰:۵۴:۵۰ __ ۱۳۹۵/۱۰/۱۴

    خسته نباشیدبسیار کوتاه و مفیدعالی

نظر خود را ارسال کنید



نام:
ایمیل:
دیدگاه:
captcha
کد امنیتی :


advertise
آموزش الگوریتم به روش پویاآشنایی با برنامه نویسی پویاالگوریتم پایین به بالاالگوریتم بازگشتی برنامه نویسی پویاتکنیک برنامه نویسی پویابرنامه نویسی پویا چیست؟الگوریتم جزء به کل برنامه نویسی پویاروش الگوریتم bottom-upتبلیغات ارزان سایت آموزش برنامه نویسیتبلیغات مخصوص طراحان وب سایتتبلیغات در سایت برنامه نویسیتبلیغات اینترنتی برای برنامه نویساندر آغوش مینیمالیسممنوی همبرگر با سه خط افقی که روی یکدیگر قرار گرفته اند نشانه چیست؟ سوئیچ به یک ستون واحدتبدیل متن ساده به وبلاگ و سایت های پویا با React.jsکتابخانه sass برای استفاده آسان تر از آنکتابخانه سطح بالا برای اتوماتیک سازی اعمال مرورگر لیست برچسب ها
تمامی حقوق این سایت اعم از محتوی ، تصاویر ، قالب و ... متعلق به گروه مهندسی وب سایت سورس کد می باشد.
SourceCodes.ir ، افقی روشن برای برنامه نویسان ، از مبتدی تا حرفه ای

پیشنهادات ویژه سورس کد

پکیج ویژه پروژه پایانی رشته کامپیوتر دانلود مجموعه 70 پروژه کاربردی سی شارپ وب سایت فروشگاه با php