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

یکی از روش‌های پرکاربرد و مشهور طراحی الگوریتم روش برنامه‌نویسی پویا (یا برنامه‌ریزی پویا، برنامه‌سازی پویا – Dynamic Programming) است. این روش همچون روش تقسیم و حل (Divide and Conquer) بر پایه تقسیم مسئله بر زیرمسئله‌ها کار می‌کند. اما تفاوت‌های چشم‌گیری با آن دارد.

زمانی که یک مسئله به دو یا چند زیرمسئله تقسیم می‌شود، دو حالت ممکن است پیش بیاید:

1- داده‌های زیرمسئله‌ها هیچ اشتراکی با هم نداشته و کاملا مستقل از هم هستند. نمونه چنین مواردی مرتب‌سازی آرایه‌ها با روش ادغام یا روش سریع است که داده‌ها به دو قسمت تقسیم شده و به صورت مجزا مرتب می‌شوند. در این حالت داده‌های یکی از بخش‌ها هیچ ارتباطی با داده‌های بخش دیگر نداشته و در نتیجه حاصل از آن بخش اثری ندارند. معمولا روش تقسیم و حل برای چنین مسائلی کارآیی خوبی دارد.

2- داده‌های زیرمسئله وابسته به هم بوده و یا با هم اشتراک دارند. در این حالت به اصطلاح زیرمسئله‌ها هم‌پوشانی دارند. نمونه بارز چنین مسائلی محاسبه جمله nام دنباله اعداد فیبوناچی است.

برنامه نویسی پویا در علم داده چطور کار می‌کند؟

فرض می‌شود که قرار است nامین عدد فیبوناچی پیدا شود. سری فیبوناچی یک دنباله از اعداد است که در آن، هر عدد (عدد فیبوناچی) مجموعه دو عدد ماقبل خودش است. آغاز سری فیبوناچی به صورت زیر است:

1, 1, 2, 3, 5, 8

برنامه محاسبه سری فیبوناچی در ادامه آمده است.

def fib(n):
    if n<=1:
        return 1
    return fib(n-1) + fib(n-2)