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

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

10000 تومان
دانلود مجموعه 100 سورس ساده و ابتدایی با سی پلاس پلاس

دانلود مجموعه 100 سورس ساده و ابتدایی با سی پلاس پلاس

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

دانلود مجموعه 70 پروژه مفید و کاربردی سی شارپ #C

28000 تومان
پکیج ویژه پروژه پایانی و پایان نامه رشته کامپیوتر

پکیج ویژه پروژه پایانی و پایان نامه رشته کامپیوتر

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

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

10000 تومان

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

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