advertise laitec sharif univercity تبلیغات در سایت سورس کد تبلیغات در سایت سورس کد
دانلود پروژه مهندسی نرم افزار ، سیستم داروخانه

دانلود پروژه مهندسی نرم افزار ، سیستم داروخانه

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

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

15000 تومان
دانلود پروژه وب سایت اشعار با ASP.NET و SQL

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

3000 تومان
دانلود پروژه آموزش چندرسانه ای با دایرکتور Director

دانلود پروژه آموزش چندرسانه ای با دایرکتور Director

3000 تومان
دانلود برنامه آزمون تستی در مالتی مدیا بیلدر MMb

دانلود برنامه آزمون تستی در مالتی مدیا بیلدر MMb

3000 تومان

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

در الگوریتم برنامه نویسی پویا، ابتدا مسائل کوچک حل میشوند و در یک مکان ذخیره میشوند و سپس به تدریج به حل مسئله اصلی میرسیم. روش پویا یک روش جزء به کل یا پایین به بالا (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