طراحی الگوریتم برنامه نویسی پویا
یکی از روشهای پرکاربرد و مشهور طراحی الگوریتم روش برنامهنویسی پویا (یا برنامهریزی پویا – Dynamic Programming) است. این روش همچون روش تقسیم و حل (Divide and Conquer) بر پایهی تقسیم مسأله بر زیرمسألهها کار میکند. اما تفاوتهای چشمگیری با آن دارد.
زمانی که یک مسأله به دو یا چند زیرمسأله تقسیم میشود، دو حالت ممکن است پیش بیاید:
۱- دادههای زیرمسألهها هیچ اشتراکی با هم نداشته و کاملا مستقل از هم هستند. نمونهی چنین مواردی مرتبسازی آرایهها با روش ادغام یا روش سریع است که دادهها به دو قسمت تقسیم شده و به صورت مجزا مرتب میشوند. در این حالت دادههای یکی از بخشها هیچ ارتباطی با دادههای بخش دیگر نداشته و در نتیجه حاصل از آن بخش اثری ندارند. معمولا روش تقسیم و حل برای چنین مسائلی کارآیی خوبی دارد.
۲- دادههای زیرمسأله وابسته به هم بوده و یا با هم اشتراک دارند. در این حالت به اصطلاح زیرمسألهها همپوشانی دارند. نمونهی بارز چنین مسائلی محاسبهی جملهی nام دنبالهی اعداد فیبوناچی است.
این جزوه طراحی الگوریتم در ۳۵ صفحه می باشد از کتاب طراحی الگوریتم مقسمی که به برنامه نویسی پویا پرداخته است.
دیدگاه خود را بیان کنید