<div dir='rtl>
در علوم رایانه و ریاضیات، برنامه‌ریزی پویا یا داینامیک روشی کارآمد برای حل مسائل جستجو و بهینه‌سازی با استفاده از دو ویژگی زیرمسئله‌های
هم‌پوشان و زیرساخت‌های بهینه است. بر خلاف برنامه‌ریزی خطی، چارچوب استانداردی برای فرموله کردن مسائل برنامه‌ریزی پویا وجود ندارد. در واقع، آنچه برنامه‌ریزی پویا انجام می‌دهد ارائه روش برخورد کلی جهت حل این نوع مسائل است. در هر مورد، باید معادلات و روابط ریاضی مخصوصی که با شرایط آن مسئله تطبیق دارد نوشته شود
اصل بهینگی
اگر بنا باشد پرانتزبندی کل عبارت بهینه شود، پرانتزبندی زیرمسئله‌ها هم باید بهینه باشند. یعنی بهینه بودن مسئله، بهینه بودن زیرمسئله‌ها را ایجاب میکند. پس می‌توان از روش برنامه‌نویسی پویا استفاده کرد.
حل بهینه، سومین مرحله از بسط یک الگوریتم برنامه‌نویسی پویا برای مسائل بهینه‌سازی است. مراحل بسط چنین الگوریتمی به شرح زیر است:
ارائه یک ویژگی بازگشتی که حل بهینهٔ نمونه‌ای از مسئله را به دست می‌دهد.
محاسبه مقدار حل بهینه به شیوهٔ جزء به کل.
بنا کردن یک حل نمونه به شیوهٔ جزء به کل.
تمام مسائل بهینه‌سازی را نمی‌توان با برنامه‌نویسی پویا حل کرد چرا که باید اصل بهینگی در مسئله صدق کند.
اصل بهینگی در یک مسئله صدق میکند اگر یک حل بهینه برای نمونه ای از مسئله، همواره حاوی حل بهینه برای همهٔ زیر نمونه‌ها باشد.
در روش برنامه‌نویسی پویا اغلب از یک آرایه برای ذخیره نتایج جهت استفاده مجدد استفاده شده، و زیرمسائل به صورت جزء به کل حل می‌شوند. در مورد این مسئله، ابتدا زیرمسائلی که تنها از دو ماتریس تشکیل شده‌اند محاسبه می‌شوند. سپس زیرمسائلی که از سه ماتریس تشکیل شده‌اند محاسبه می‌شوند. این دسته از زیرمسائل به زیرمسائلی متشکل از دو ماتریس تجزیه می‌شوند که قبلاً محاسبات آن‌ها صورت گرفته، و نتایج آن‌ها در آرایه ذخیره شده‌اند. در نتیجه نیاز به محاسبه مجدد آن‌ها نیست. به همین ترتیب در مرحله بعد زیرمسائل با چهار ماتریس محاسبه می‌شوند، و الی آخر.
درختهای جستجوی دودویی بهینه
درخت جستجوی دودویی یک درخت دودویی از عناصر است که معمولاً کلید نامیده می‌شوند به قسمی که:
هر گره حاوی یک کلید است.
کلیدهای موجود در زیردرخت چپ هر گره، کوچکتر یا مساوی کلید آن گره هستند.
کلیدهای موجود در زیردرخت راست هر گره، بزرگتر یا مساوی کلید آن گره هستند
برنامه نویسی پویا در علم داده چطور کار میکند؟
فرض میشود که قرار است nامین عدد فیبوناچی پیدا شود. سری فیبوناچی یک دنباله از اعداد است که در آن، هر عدد (عدد فیبوناچی) مجموعه دو عدد ماقبل خودش است. آغاز سری فیبوناچی به صورت زیر است:
1, 1, 2, 3, 5, 8
برنامه محاسبه سری فیبوناچی در ادامه آمده است.
def fib(n):
if n<=1:
return 1
return fib(n-1) + fib(n-2)
def fib(n):
if n<=1:
return 1
return fib(n-1) + fib(n-2)
کد ارائه شده در بالا برای ارائه اعداد فیبوناچی، به صورت بازگشتی است. اما مشکلی در روش ارائه شده در بالا وجود دارد. اگر فرد تلاش کند که fib(n=7) را محاسبه کند، باید fib(5) را دو بار، fib(4) سه بار و fib(3) را پنج بار اجرا کند. هر چه n بزرگتر میشود، فراخوانی‌های زیادتری برای اعداد مشابه انجام میشود و تابع بازگشتی آن را بارها و بارها محاسبه میشود.
برنامه نویسی پویا در علم داده -- راهنمای کاربردی
در حال حاضر، بازگشت یک رویکرد بالا به پایین است. همچون هنگامی که عدد فیبوناچی n محاسبه میشود، کار از n آغاز میشود و سپس، فراخوانی بازگشتی برای n-2 و n-1 و به همین صورت، انجام میشود. در برنامه‌نویسی پویا، یک رویکرد پایین به بالا اتخاذ میشود. این راهکاری برای انجام بازگشت‌ها به صورت تکرار شونده است. کار با محاسبه fib(0) و fib(1) آغاز میشود و سپس، با استفاده از نتایج قبلی، نتایج جدید تولید می‌شوند.
def fib_dp(n):
dp_sols = {0:1,1:1}
for i in range(2,n+1):
dp_sols[i] = dp_sols[i-1] + dp_sols[i-2]
return dp_sols[n]
def fib_dp(n):
dp_sols = {0:1,1:1}
for i in range(2,n+1):
dp_sols[i] = dp_sols[i-1] + dp_sols[i-2]
return dp_sols[n]
زیرمسئله‌های هم‌پوشان
زیرمسئله‌های هم‌پوشان به معنای کوچک بودن فضای زیرمسئله‌هاست، به این معنا که هر الگوریتم بازگشتی برای حل این مسئله، باید به جای ایجاد زیرمسئله‌های جدید، زیرمسئله‌های تکراری را بارها حل کند. برای مثال، به فرمول بازگشی دنبالهٔ فیبوناچی دقت کنید: Fi = Fi−1 + Fi−2، با حالات پایهٔ F1 = F2 = ۱. آنگاه F43 = F42 + F41، و F42 = F41 + F40. اکنون F41 در زیردرخت‌های هر دوی F43 و F42 محاسبه میشود. در صورت اتخاذ چنین رویکرد ساده‌انگارانه‌ای، نهایتاً زیرمسئله‌های یکسانی را بارها حل می‌کنیم، در صورتی که تعداد کل زیرمسئله‌ها در واقعیت کم است (تنها ۴۳تا). برنامه‌نویسی پویا به این حقیقت دقت میکند و هر زیرمسئله را تنها یک بار حل میکند.[۴]
گفته میشود مسئله‌ای دارای زیرمسئله‌های هم‌پوشان است، اگر بتوان مسئله را به زیرمسئله‌های کوچکتری شکست که پاسخ هرکدام چند بار در طول فرایند حل مورد استفاده قرار بگیرد.[۵] برنامه‌ریزی پویا کمک میکند تا هر کدام از این پاسخ‌ها فقط یک بار محاسبه شوند و فرایند حل از بابت دوباره‌کاری هزینه‌ای را متحمل نشود. برای مثال در دنباله فیبوناچی برای محاسبهٔ عدد چهارم دنباله به دانستن عدد سوم نیاز داریم. برای محاسبهٔ عدد پنجم هم باز به عدد سوم نیاز داریم. حال اگر مثلاً در شرایطی بخواهیم عدد ششم دنبالهٔ فیبوناچی را حساب کنیم، در این محاسبه هم مقدار عدد پنجم را می‌خواهیم و هم مقدار عدد چهارم را. اگر تصمیم بگیریم اعداد چهارم و پنجم را به نوبت حساب کنیم در هنگام محاسبهٔ هرکدام به مقدار عدد سوم نیاز پیدا می‌کنیم و باید دوباره آن را محاسبه کنیم. برای جلوگیری از این محاسبات چندباره، الگوریتمهایی که مبتنی بر برنامه‌ریزی پویا هستند، معمولاً یکی از دو راه زیر را استفاده می‌کنند.
رویکرد بالا به پایین: راه درروی مستقیم از صورت‌بندی بازگشتی هر مسئله‌ای است. اگر جواب مسئله‌ای را بتوان به صورت بازگشتی با جواب زیرمسئله‌های آن به دست آورد، و در صورت هم‌پوشانی زیرمسئله‌ها، می‌توان جواب زیرمسئله‌ها را در یک جدول به خاطر سپرد. هر گاه که برای حل یک زیرمسئله اقدام می‌کنیم، ابتدا بررسی می‌کنیم که آیا این زیرمسئله قبلاً حل شده یا نه؛ اگر جواب آن را داشتیم، می‌توانیم آن را مستقیماً استفاده کنیم؛ در غیر این صورت، زیرمسئله را حل می‌کنیم و جواب آن را به جدول اضافه می‌کنیم. در این رویکرد مسئله به زیرمسئله‌هایی شکسته میشود و پاسخ هر زیرمسئله پس از محاسبه در جایی ذخیره میشود. در مراحل بعدی هر وقت به آن پاسخ نیاز بود پاسخ از روی حافظه خوانده میشود. این فرایند ترکیبی از الگوریتم بازگشتی و ذخیره‌سازی در حافظه است.
رویکرد پایین به بالا: پس از آن که جواب یک مسئله را به صورت بازگشتی با استفاده از زیرمسئله‌های آن صورت‌بندی کردیم، می‌توانیم مسئله را از پایین به بالا نگاه کنیم: ابتدا زیرمسئله‌ها را حل می‌کنیم و سپس جواب آن‌ها را برای به دست آوردن جواب زیرمسئله‌های بزرگتر استفاده می‌کنیم تا نهایتاً به مسئلهٔ اصلی برسیم. این روش نیز معمولاً به کمک یک جدول با تولید مرحله به مرحلهٔ زیرمسئله‌های بزرگتر و بزرگتر به کمک جواب زیرمسئله‌های کوچکتر انجام میشود؛ برای مثال، اگر مقادیر F41 و F40 را بدانیم، می‌توانیم مستقیماً مقدار F42 را به دست آوریم. در این رویکرد همهٔ زیرمسئله‌های مورد نیاز از کوچک به بزرگ حل می‌شوند و از جواب‌ها «بلافاصله» برای محاسبهٔ بعدی‌ها استفاده میشود و فرایند محاسبه تا رسیدن به زیرمسئلهٔ مورد نیاز (که در واقع مسئلهٔ اصلی ماست) ادامه می‌یابد. بدیهی است که در این حالت استفاده از الگوریتم بازگشتی ضروری نیست. مثال زیر این تفاوت‌ها را روشن‌تر میکند. برخی از زبان‌های برنامه‌نویسی می‌توانند به‌طور خودکار جواب صدا زدن یک تابع با ورودی‌های مشخص را به خاطر بسپارند تا صدا زدن با نام را سرعت ببخشند (این فرایند با نام صدا زدن با نیاز شناخته‌می‌شود). برخی زبان‌ها به شکل سیار این امکان را در اختیار برنامه‌نویس قرار می‌دهند (مانند Scheme ,Common Lisp ,[۶]Perl و D). برخی زبان‌های نیز به صورت خودکار به‌خاطرسپاری را در خود دارند: مانند Prolog جدول‌دار و J، که به‌خاطرسپاری را با قید .M پشتیبانی میکند.[۷] در هر صورت، این تنها برای یک تابع با شفافیت ارجاعی امکان دارد. به‌خاطرسپاری به عنوان یک الگوی طراحی در دسترس نیز در زبان‌های بازنویسی جملات مانند زبان ولفرام یافت‌می‌شود.
گراف زیرمسئله‌ها
زمانی که به یک مسئلهٔ برنامه‌نویسی پویا می‌اندیشیم، باید مجموعهٔ زیرمسئله‌های موجود و چگونگی وابستگی آن‌ها را درک کنیم.
گراف زیرمسئله‌ها دقیقاً همین اطلاعات را برای یک مسئله در بر می‌گیرد گراف زیرمسئله‌ها یک گراف جهت‌دار، شامل یک رأس به ازای هر زیرمسئلهٔ متمایز است و در صورتی یک یال جهت‌دار از رأس زیرمسئلهٔ x به رأس زیرمسئلهٔ y دارد که برای تعیین یک جواب بهینه برای زیرمسئلهٔ x مستقیماً نیاز به در نظر گرفتن یک جواب بهینه برای زیرمسئلهٔ y داشته‌باشیم. برای نمونه، گراف زیرمسئله دارای یک یال از x به y است، در صورتی که یک رویهٔ (procedure) بازگشتی بالا به پایین برای حل x، مستقیماً خود را برای حل y صدا بزند. می‌توان گراف زیرمسئله‌ها را یک نسخهٔ کاهش‌یافتهٔ درخت بازگشتی برای روش بازگشتی بالا به پایین در نظر گرفت، به گونه‌ای که همهٔ رئوس مربوط به یک زیرمسئله را یکی کنیم و یال‌ها را از والد به فرزند جهت‌دار کنیم.
روش پایین به بالا برای برنامه‌نویسی پویا رئوس گراف زیرمسئله‌ها را به ترتیبی در نظر می‌گیرد که همهٔ زیرمسئله‌های مجاور یک زیرمسئله، پیش از آن حل شوند. در یک الگوریتم برنامه‌نویسی پویای پایین به بالا، رئوس گراف زیرمسئله‌ها را به صورتی در نظر می‌گیریم که «معکوس مرتب توپولوژیکی» یا «مرتب توپولوژیک وارون» زیرگراف مسئه‌ها است. به زبان دیگر، هیچ زیرمسئله‌ای تا زمانی که همهٔ زیرمسئله‌هایی که به آن‌ها وابسته است حل نشده‌اند، در نظر گرفته‌نمی‌شود. به‌طور مشابه، می‌توانیم رویکرد بالا به پایین (همراه به‌خاطرسپاری) برای برنامه‌نویسی پویا را به شکل جستجوی ژرفانخست گراف زیرمسئله‌ها ببینیم.
اندازهٔ گراف زیرمسئله‌ها میتواند ما را در تعیین زمان اجرای الگوریتم برنامه‌نویسی پویا یاری کند. از آنجایی که هر زیرمسئله را فقط یک بار حل می‌کنیم، زمان اجرا برابر است با مجموع تعداد بارهایی که نیاز است هر زیرمسئله را حل کنیم. به‌طور معمول، زمان محاسبهٔ جواب یک زیرمسئله، متناسب با درجهٔ رأس متناظر در گراف، و تعداد زیرمسئله‌ها برابر با تعداد رئوس گراف است.[۸]
مثال
یک پیاده‌سازی ساده از یک تابع برای یافتن عدد فیبوناچی nام میتواند به شکل زیر باشد.
function fib(n)
if n = 0
return 0
if n = 1
return 1
return fib(n − 1) + fib(n − 2)
برای مثال اگر از چنین تابعی (fib(5 را بخواهیم، تابع‌هایی که صدا می‌شوند به شکل زیر خواهند بود.
fib(5)
fib(4) + fib(3)
(fib(3) + fib(2)) + (fib(2) + fib(1))
((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
(((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
مشخص است که چنین فرایندی پر از محاسبات تکراری است. مثلاً عدد فیبوناچی دوم به تنهایی سه بار حساب شده‌است. در محاسبات بزرگتر چنین تکرارهایی برنامه را به شدت کند می‌کنند. این الگوریتم دارای پیچیدگی زمانی نمایی است. حال فرض کنید ما یک آرایه دوتایی map داریم که عدد n را به مقدار عدد فیبوناچی nام مربوط کرده و ذخیره میکند. پیچیدگی زمانی چنین الگوریتمی n خواهد بود. همچنین میزان فضای اشغال‌شده‌اش هم از مرتبه n خواهد بود.
var m := map(0 → 1, 1 → 1)
function fib(n)
if map m does not contain key n
m[n] := fib(n − 1) + fib(n − 2)
return m[n]
این نمونه‌ای از فرایند بالا به پایین بود. چون ابتدا مسئله را شکستیم و بعد به محاسبه و ذخیرهٔ پاسخ زیرمسئله‌ها پرداختیم.
در فرایند پایین به بالا برای حل چنین مسئله‌ای از عدد فیبوناچی یکم شروع می‌کنیم تا به عدد خواسته‌شده برسیم.
function fib(n)
var previousFib := 0, currentFib := 1
if n = 0
return 0
if n = 1
return 1
repeat n − 1 times
var newFib := previousFib + currentFib
previousFib := currentFib
currentFib := newFib
return currentFib
برتری این روش به روش قبلی در این است که در این روش حتی به فضای ذخیره از مرتبه n. فضای ذخیره از مرتبه ۱ کفایت میکند. علت این که همیشه از رویکرد پایین به بالا استفاده نمی‌کنیم این است که گاهی از قبل نمی‌دانیم باید کدام زیرمسئله‌ها را حل کنیم تا به مرحله اصلی برسیم، یا این که مجبوریم زیرمسئله‌هایی که استفاده نمی‌شوند را هم حل کنیم.
تفاوت این روش و روش تقسیم و غلبه (تقسیم و حل)
یکی از روش‌های پرکاربرد و مشهور طراحی الگوریتم روش برنامه‌نویسی پویا (یا برنامه‌ریزی پویا - Dynamic Programming) است. این روش همچون روش تقسیم و حل (Divide and Conquer) بر پایه تقسیم مسئله بر زیرمسئله‌ها کار میکند. اما تفاوت‌های چشم‌گیری با آن دارد.
زمانی که یک مسئله به دو یا چند زیرمسئله تقسیم میشود، دو حالت ممکن است پیش بیاید:
داده‌های زیرمسئله‌ها هیچ اشتراکی با هم نداشته و کاملاً مستقل از هم هستند. نمونه چنین مواردی مرتب‌سازی آرایه‌ها با روش ادغام یا روش سریع است که داده‌ها به دو قسمت تقسیم شده و به صورت مجزا مرتب می‌شوند. در این حالت داده‌های یکی از بخش‌ها هیچ ارتباطی با داده‌های بخش دیگر نداشته و در نتیجهٔ حاصل از آن بخش، اثری ندارند. معمولاً روش تقسیم و حل برای چنین مسائلی کارایی خوبی دارد.
داده‌های زیرمسئله وابسته به هم بوده یا با هم اشتراک دارند. در این حالت به اصطلاح زیرمسئله‌ها هم‌پوشانی دارند. نمونه بارز چنین مسائلی محاسبه جمله nام دنباله اعداد فیبوناچی است.
روش برنامه‌نویسی پویا غالباً برای الگوریتمهایی به کار برده میشود که در پی حل مسئله‌ای به صورت بهینه می‌باشند.
در روش تقسیم و غلبه ممکن است برخی از زیرمسائلِ کوچکتر، با هم برابر باشند که در این صورت زیرمسائلِ برابر، به‌طور تکراری چندین مرتبه حل می‌شوند که این یکی از معایب روش تقسیم و غلبه است.
ایده‌ای که در فرایِ روش برنامه‌نویسی پویا نهفته‌است، جلوگیری از انجام این محاسبات تکراری است و روشی که معمولاً برای این عمل به کارگرفته میشود استفاده از جدولی برای نگهداری نتایج حاصل از حل زیرمسائل است. در این صورت اگر الگوریتم به زیرمسئله‌ای برخورد کرد که پیش از این حل شده است، به جای حل مجدد آن، نتیجه محاسبه قبلی را از جدول برداشته و کار را با زیرمسئله بعدی دنبال میکند.
روش برنامه‌نویسی پویا یک روش پایین به بالا است (البته همان‌طور که گفته شد، اگر از قبل بدانیم باید کدام زیرمسئله‌ها را حل کنیم تا به مرحله اصلی برسیم، یا این که مجبور نباشیم زیرمسئله‌هایی که استفاده نمی‌شوند را هم حل کنیم) به این معنی که از حل مسائل کوچکتر به حل مسائل بزرگتر می‌رسیم. در حالیکه از نظر ساختاری، روش تقسیم و غلبه روشی است از بالا به پایین، یعنی به‌طور منطقی (نه عملی) پردازش از مسئله اولیه آغاز شده و به سمت پایین و حل مسائلِ کوچکتر، به پیش می‌رود.
مجموع زیرمجموعه و کوله پشتی: اضافه کردن یک متغیر
ما بیشتر و بیشتر می‌بینیم که مسائل مربوط به برنامه‌ریزی منبع خیلی خوبی از مسایل الگوریتمی را با انگیزهٔ عملی ارائه می‌دهد. تاکنون مشکلاتی را در نظر گرفتیم که در آن درخواست‌ها با فاصلهٔ زمانی مشخص از یک منبع مشخص‌شده و همچنین مشکلاتی که در آن درخواست‌ها دارای مدت و مهلت هستند، اما فواصل خاصی را که در طی آن باید انجام شود تعیین نشده‌است. در این بخش، ما نسخه‌ای از نوع دوم مشکل را با مدت زمان و مهلت در نظر می‌گیریم، که حل مستقیم با استفاده از تکنیک‌هایی که تاکنون دیده‌ایم، دشوار است.
ما برای حل مسئله از برنامه‌نویسی پویا استفاده خواهیم کرد، اما با یک تغییر: مشخص میشود مجموعه زیرمسئله‌ها به اندازه کافی نخواهدبود، و بنابراین ما در نهایت به ایجاد یک مجموعه غنی‌تر از زیرمسئله‌ها می‌پردازیم. همان‌طور که خواهیم‌دید، این کار با اضافه کردن یک متغیر جدید به بازگشت در زیربرنامهٔ پویا انجام میشود.
سه قدم کلی برای برنامه نویسی داینامیک وجود دارد:
بازگشتی (Recursion)
ذخیره سازی(store)
Bottom-Up
بازگشتی (Recursion)
بازگشتی از محاسبه معادله ای که قبلا انجام شده جلو گیری میکند.
به این طریق که وقتی یک معادله انجام می شود در بخش ذخیره سازی یا store ، ذخیره می شود و زمانی که صدا زده می شود دیگه نیازی به محاسبه مجدد نیست. به نحوی وقتی برنامه ای بدون استفاده از dynamic programming نوشته می شود هیچ فضایی گرفته نمی شود اما با استفاده از dynamic programming فضایی برای سرعت بخشیدن به برنامه ایجاد می شود که مقادیر memoize می شود( با memorize اشتباه نگیرید) به معنای یادآوری.
زمانی که (fib(3 یک بار برای (fib(4 محاسبه میشود دیگر برای (fib(5 محاسبه نمیشود و memoize می شود.
ذخیره سازی
ذخیره سازی همان فضایی است که برای نگه داشتن معادله های محاسبه شده از آن استفاده می کنیم.(برای memoize کردن)
Bottom-Up
یک روش سریع تر از store یا ذخیره سازیست که با استفاده از آرایه ها انجام می شود.
``
به این صورت که برنامه ها در آرایه ها ذخیره می شوند و زمان نیاز صدا زده می شوند و باعث جلو گیری از بار اضافه در برنامه می شوند به نوعی شبیه به store است اما با این تفاوت که همه این ها در یک آرایه ذخیره می شود و نیاز به چند آرایه نیست. همچنین تا مقدار بیشتری میتواند پیشروی کند.
Going bottom-up is a way to avoid recursion, saving the memory cost that recursion incurs when it builds up the call stack.
Put simply, a bottom-up algorithm "starts from the beginning," while a recursive algorithm often "starts from the end and works backwards."
For example, if we wanted to multiply all the numbers in the range 1..n1..n, we could use this cute, top-down, recursive one-liner:
public static int product1ToN(int n) {
// we assume n >= 1
return (n > 1) ? (n * product1ToN(n-1)) : 1;
}
This approach has a problem: it builds up a call stack of size O(n)O(n), which makes our total memory cost O(n)O(n). This makes it vulnerable to a stack overflow error, where the call stack gets too big and runs out of space.
To avoid this, we can instead go bottom-up:
public static int product1ToN(int n) {
// we assume n >= 1
int result = 1;
for (int num = 1; num <= n; num++) {
result *= num;
}
return result;
<div dir='rtl> در علوم رایانه و ریاضیات، برنامه‌ریزی پویا یا داینامیک روشی کارآمد برای حل مسائل جستجو و بهینه‌سازی با استفاده از دو ویژگی زیرمسئله‌های هم‌پوشان و زیرساخت‌های بهینه است. بر خلاف برنامه‌ریزی خطی، چارچوب استانداردی برای فرموله کردن مسائل برنامه‌ریزی پویا وجود ندارد. در واقع، آنچه برنامه‌ریزی پویا انجام می‌دهد ارائه روش برخورد کلی جهت حل این نوع مسائل است. در هر مورد، باید معادلات و روابط ریاضی مخصوصی که با شرایط آن مسئله تطبیق دارد نوشته شود اصل بهینگی اگر بنا باشد پرانتزبندی کل عبارت بهینه شود، پرانتزبندی زیرمسئله‌ها هم باید بهینه باشند. یعنی بهینه بودن مسئله، بهینه بودن زیرمسئله‌ها را ایجاب میکند. پس می‌توان از روش برنامه‌نویسی پویا استفاده کرد.
حل بهینه، سومین مرحله از بسط یک الگوریتم برنامه‌نویسی پویا برای مسائل بهینه‌سازی است. مراحل بسط چنین الگوریتمی به شرح زیر است:
ارائه یک ویژگی بازگشتی که حل بهینهٔ نمونه‌ای از مسئله را به دست می‌دهد. محاسبه مقدار حل بهینه به شیوهٔ جزء به کل. بنا کردن یک حل نمونه به شیوهٔ جزء به کل. تمام مسائل بهینه‌سازی را نمی‌توان با برنامه‌نویسی پویا حل کرد چرا که باید اصل بهینگی در مسئله صدق کند.
اصل بهینگی در یک مسئله صدق میکند اگر یک حل بهینه برای نمونه ای از مسئله، همواره حاوی حل بهینه برای همهٔ زیر نمونه‌ها باشد.
در روش برنامه‌نویسی پویا اغلب از یک آرایه برای ذخیره نتایج جهت استفاده مجدد استفاده شده، و زیرمسائل به صورت جزء به کل حل می‌شوند. در مورد این مسئله، ابتدا زیرمسائلی که تنها از دو ماتریس تشکیل شده‌اند محاسبه می‌شوند. سپس زیرمسائلی که از سه ماتریس تشکیل شده‌اند محاسبه می‌شوند. این دسته از زیرمسائل به زیرمسائلی متشکل از دو ماتریس تجزیه می‌شوند که قبلاً محاسبات آن‌ها صورت گرفته، و نتایج آن‌ها در آرایه ذخیره شده‌اند. در نتیجه نیاز به محاسبه مجدد آن‌ها نیست. به همین ترتیب در مرحله بعد زیرمسائل با چهار ماتریس محاسبه می‌شوند، و الی آخر.
درختهای جستجوی دودویی بهینه
درخت جستجوی دودویی یک درخت دودویی از عناصر است که معمولاً کلید نامیده می‌شوند به قسمی که:
هر گره حاوی یک کلید است. کلیدهای موجود در زیردرخت چپ هر گره، کوچکتر یا مساوی کلید آن گره هستند. کلیدهای موجود در زیردرخت راست هر گره، بزرگتر یا مساوی کلید آن گره هستند برنامه نویسی پویا در علم داده چطور کار میکند؟ فرض میشود که قرار است nامین عدد فیبوناچی پیدا شود. سری فیبوناچی یک دنباله از اعداد است که در آن، هر عدد (عدد فیبوناچی) مجموعه دو عدد ماقبل خودش است. آغاز سری فیبوناچی به صورت زیر است:
1, 1, 2, 3, 5, 8
برنامه محاسبه سری فیبوناچی در ادامه آمده است.
def fib(n): if n<=1: return 1 return fib(n-1) + fib(n-2) def fib(n): if n<=1: return 1 return fib(n-1) + fib(n-2) کد ارائه شده در بالا برای ارائه اعداد فیبوناچی، به صورت بازگشتی است. اما مشکلی در روش ارائه شده در بالا وجود دارد. اگر فرد تلاش کند که fib(n=7) را محاسبه کند، باید fib(5) را دو بار، fib(4) سه بار و fib(3) را پنج بار اجرا کند. هر چه n بزرگتر میشود، فراخوانی‌های زیادتری برای اعداد مشابه انجام میشود و تابع بازگشتی آن را بارها و بارها محاسبه میشود.
برنامه نویسی پویا در علم داده -- راهنمای کاربردی در حال حاضر، بازگشت یک رویکرد بالا به پایین است. همچون هنگامی که عدد فیبوناچی n محاسبه میشود، کار از n آغاز میشود و سپس، فراخوانی بازگشتی برای n-2 و n-1 و به همین صورت، انجام میشود. در برنامه‌نویسی پویا، یک رویکرد پایین به بالا اتخاذ میشود. این راهکاری برای انجام بازگشت‌ها به صورت تکرار شونده است. کار با محاسبه fib(0) و fib(1) آغاز میشود و سپس، با استفاده از نتایج قبلی، نتایج جدید تولید می‌شوند. def fib_dp(n): dp_sols = {0:1,1:1} for i in range(2,n+1): dp_sols[i] = dp_sols[i-1] + dp_sols[i-2] return dp_sols[n] def fib_dp(n): dp_sols = {0:1,1:1} for i in range(2,n+1): dp_sols[i] = dp_sols[i-1] + dp_sols[i-2]
return dp_sols[n] زیرمسئله‌های هم‌پوشان زیرمسئله‌های هم‌پوشان به معنای کوچک بودن فضای زیرمسئله‌هاست، به این معنا که هر الگوریتم بازگشتی برای حل این مسئله، باید به جای ایجاد زیرمسئله‌های جدید، زیرمسئله‌های تکراری را بارها حل کند. برای مثال، به فرمول بازگشی دنبالهٔ فیبوناچی دقت کنید: Fi = Fi−1 + Fi−2، با حالات پایهٔ F1 = F2 = ۱. آنگاه F43 = F42 + F41، و F42 = F41 + F40. اکنون F41 در زیردرخت‌های هر دوی F43 و F42 محاسبه میشود. در صورت اتخاذ چنین رویکرد ساده‌انگارانه‌ای، نهایتاً زیرمسئله‌های یکسانی را بارها حل می‌کنیم، در صورتی که تعداد کل زیرمسئله‌ها در واقعیت کم است (تنها ۴۳تا). برنامه‌نویسی پویا به این حقیقت دقت میکند و هر زیرمسئله را تنها یک بار حل میکند.[۴]
گفته میشود مسئله‌ای دارای زیرمسئله‌های هم‌پوشان است، اگر بتوان مسئله را به زیرمسئله‌های کوچکتری شکست که پاسخ هرکدام چند بار در طول فرایند حل مورد استفاده قرار بگیرد.[۵] برنامه‌ریزی پویا کمک میکند تا هر کدام از این پاسخ‌ها فقط یک بار محاسبه شوند و فرایند حل از بابت دوباره‌کاری هزینه‌ای را متحمل نشود. برای مثال در دنباله فیبوناچی برای محاسبهٔ عدد چهارم دنباله به دانستن عدد سوم نیاز داریم. برای محاسبهٔ عدد پنجم هم باز به عدد سوم نیاز داریم. حال اگر مثلاً در شرایطی بخواهیم عدد ششم دنبالهٔ فیبوناچی را حساب کنیم، در این محاسبه هم مقدار عدد پنجم را می‌خواهیم و هم مقدار عدد چهارم را. اگر تصمیم بگیریم اعداد چهارم و پنجم را به نوبت حساب کنیم در هنگام محاسبهٔ هرکدام به مقدار عدد سوم نیاز پیدا می‌کنیم و باید دوباره آن را محاسبه کنیم. برای جلوگیری از این محاسبات چندباره، الگوریتمهایی که مبتنی بر برنامه‌ریزی پویا هستند، معمولاً یکی از دو راه زیر را استفاده می‌کنند.
رویکرد بالا به پایین: راه درروی مستقیم از صورت‌بندی بازگشتی هر مسئله‌ای است. اگر جواب مسئله‌ای را بتوان به صورت بازگشتی با جواب زیرمسئله‌های آن به دست آورد، و در صورت هم‌پوشانی زیرمسئله‌ها، می‌توان جواب زیرمسئله‌ها را در یک جدول به خاطر سپرد. هر گاه که برای حل یک زیرمسئله اقدام می‌کنیم، ابتدا بررسی می‌کنیم که آیا این زیرمسئله قبلاً حل شده یا نه؛ اگر جواب آن را داشتیم، می‌توانیم آن را مستقیماً استفاده کنیم؛ در غیر این صورت، زیرمسئله را حل می‌کنیم و جواب آن را به جدول اضافه می‌کنیم. در این رویکرد مسئله به زیرمسئله‌هایی شکسته میشود و پاسخ هر زیرمسئله پس از محاسبه در جایی ذخیره میشود. در مراحل بعدی هر وقت به آن پاسخ نیاز بود پاسخ از روی حافظه خوانده میشود. این فرایند ترکیبی از الگوریتم بازگشتی و ذخیره‌سازی در حافظه است. رویکرد پایین به بالا: پس از آن که جواب یک مسئله را به صورت بازگشتی با استفاده از زیرمسئله‌های آن صورت‌بندی کردیم، می‌توانیم مسئله را از پایین به بالا نگاه کنیم: ابتدا زیرمسئله‌ها را حل می‌کنیم و سپس جواب آن‌ها را برای به دست آوردن جواب زیرمسئله‌های بزرگتر استفاده می‌کنیم تا نهایتاً به مسئلهٔ اصلی برسیم. این روش نیز معمولاً به کمک یک جدول با تولید مرحله به مرحلهٔ زیرمسئله‌های بزرگتر و بزرگتر به کمک جواب زیرمسئله‌های کوچکتر انجام میشود؛ برای مثال، اگر مقادیر F41 و F40 را بدانیم، می‌توانیم مستقیماً مقدار F42 را به دست آوریم. در این رویکرد همهٔ زیرمسئله‌های مورد نیاز از کوچک به بزرگ حل می‌شوند و از جواب‌ها «بلافاصله» برای محاسبهٔ بعدی‌ها استفاده میشود و فرایند محاسبه تا رسیدن به زیرمسئلهٔ مورد نیاز (که در واقع مسئلهٔ اصلی ماست) ادامه می‌یابد. بدیهی است که در این حالت استفاده از الگوریتم بازگشتی ضروری نیست. مثال زیر این تفاوت‌ها را روشن‌تر میکند. برخی از زبان‌های برنامه‌نویسی می‌توانند به‌طور خودکار جواب صدا زدن یک تابع با ورودی‌های مشخص را به خاطر بسپارند تا صدا زدن با نام را سرعت ببخشند (این فرایند با نام صدا زدن با نیاز شناخته‌می‌شود). برخی زبان‌ها به شکل سیار این امکان را در اختیار برنامه‌نویس قرار می‌دهند (مانند Scheme ,Common Lisp ,[۶]Perl و D). برخی زبان‌های نیز به صورت خودکار به‌خاطرسپاری را در خود دارند: مانند Prolog جدول‌دار و J، که به‌خاطرسپاری را با قید .M پشتیبانی میکند.[۷] در هر صورت، این تنها برای یک تابع با شفافیت ارجاعی امکان دارد. به‌خاطرسپاری به عنوان یک الگوی طراحی در دسترس نیز در زبان‌های بازنویسی جملات مانند زبان ولفرام یافت‌می‌شود. گراف زیرمسئله‌ها زمانی که به یک مسئلهٔ برنامه‌نویسی پویا می‌اندیشیم، باید مجموعهٔ زیرمسئله‌های موجود و چگونگی وابستگی آن‌ها را درک کنیم.
گراف زیرمسئله‌ها دقیقاً همین اطلاعات را برای یک مسئله در بر می‌گیرد گراف زیرمسئله‌ها یک گراف جهت‌دار، شامل یک رأس به ازای هر زیرمسئلهٔ متمایز است و در صورتی یک یال جهت‌دار از رأس زیرمسئلهٔ x به رأس زیرمسئلهٔ y دارد که برای تعیین یک جواب بهینه برای زیرمسئلهٔ x مستقیماً نیاز به در نظر گرفتن یک جواب بهینه برای زیرمسئلهٔ y داشته‌باشیم. برای نمونه، گراف زیرمسئله دارای یک یال از x به y است، در صورتی که یک رویهٔ (procedure) بازگشتی بالا به پایین برای حل x، مستقیماً خود را برای حل y صدا بزند. می‌توان گراف زیرمسئله‌ها را یک نسخهٔ کاهش‌یافتهٔ درخت بازگشتی برای روش بازگشتی بالا به پایین در نظر گرفت، به گونه‌ای که همهٔ رئوس مربوط به یک زیرمسئله را یکی کنیم و یال‌ها را از والد به فرزند جهت‌دار کنیم.
روش پایین به بالا برای برنامه‌نویسی پویا رئوس گراف زیرمسئله‌ها را به ترتیبی در نظر می‌گیرد که همهٔ زیرمسئله‌های مجاور یک زیرمسئله، پیش از آن حل شوند. در یک الگوریتم برنامه‌نویسی پویای پایین به بالا، رئوس گراف زیرمسئله‌ها را به صورتی در نظر می‌گیریم که «معکوس مرتب توپولوژیکی» یا «مرتب توپولوژیک وارون» زیرگراف مسئه‌ها است. به زبان دیگر، هیچ زیرمسئله‌ای تا زمانی که همهٔ زیرمسئله‌هایی که به آن‌ها وابسته است حل نشده‌اند، در نظر گرفته‌نمی‌شود. به‌طور مشابه، می‌توانیم رویکرد بالا به پایین (همراه به‌خاطرسپاری) برای برنامه‌نویسی پویا را به شکل جستجوی ژرفانخست گراف زیرمسئله‌ها ببینیم.
اندازهٔ گراف زیرمسئله‌ها میتواند ما را در تعیین زمان اجرای الگوریتم برنامه‌نویسی پویا یاری کند. از آنجایی که هر زیرمسئله را فقط یک بار حل می‌کنیم، زمان اجرا برابر است با مجموع تعداد بارهایی که نیاز است هر زیرمسئله را حل کنیم. به‌طور معمول، زمان محاسبهٔ جواب یک زیرمسئله، متناسب با درجهٔ رأس متناظر در گراف، و تعداد زیرمسئله‌ها برابر با تعداد رئوس گراف است.[۸]
مثال یک پیاده‌سازی ساده از یک تابع برای یافتن عدد فیبوناچی nام میتواند به شکل زیر باشد.
function fib(n) if n = 0
return 0
if n = 1
return 1
return fib(n − 1) + fib(n − 2)
برای مثال اگر از چنین تابعی (fib(5 را بخواهیم، تابع‌هایی که صدا می‌شوند به شکل زیر خواهند بود.
fib(5) fib(4) + fib(3) (fib(3) + fib(2)) + (fib(2) + fib(1)) ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1)) (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1)) مشخص است که چنین فرایندی پر از محاسبات تکراری است. مثلاً عدد فیبوناچی دوم به تنهایی سه بار حساب شده‌است. در محاسبات بزرگتر چنین تکرارهایی برنامه را به شدت کند می‌کنند. این الگوریتم دارای پیچیدگی زمانی نمایی است. حال فرض کنید ما یک آرایه دوتایی map داریم که عدد n را به مقدار عدد فیبوناچی nام مربوط کرده و ذخیره میکند. پیچیدگی زمانی چنین الگوریتمی n خواهد بود. همچنین میزان فضای اشغال‌شده‌اش هم از مرتبه n خواهد بود.
var m := map(0 → 1, 1 → 1) function fib(n) if map m does not contain key n m[n] := fib(n − 1) + fib(n − 2) return m[n] این نمونه‌ای از فرایند بالا به پایین بود. چون ابتدا مسئله را شکستیم و بعد به محاسبه و ذخیرهٔ پاسخ زیرمسئله‌ها پرداختیم.
در فرایند پایین به بالا برای حل چنین مسئله‌ای از عدد فیبوناچی یکم شروع می‌کنیم تا به عدد خواسته‌شده برسیم. function fib(n) var previousFib := 0, currentFib := 1 if n = 0 return 0 if n = 1 return 1 repeat n − 1 times var newFib := previousFib + currentFib previousFib := currentFib currentFib := newFib return currentFib برتری این روش به روش قبلی در این است که در این روش حتی به فضای ذخیره از مرتبه n. فضای ذخیره از مرتبه ۱ کفایت میکند. علت این که همیشه از رویکرد پایین به بالا استفاده نمی‌کنیم این است که گاهی از قبل نمی‌دانیم باید کدام زیرمسئله‌ها را حل کنیم تا به مرحله اصلی برسیم، یا این که مجبوریم زیرمسئله‌هایی که استفاده نمی‌شوند را هم حل کنیم. تفاوت این روش و روش تقسیم و غلبه (تقسیم و حل) یکی از روش‌های پرکاربرد و مشهور طراحی الگوریتم روش برنامه‌نویسی پویا (یا برنامه‌ریزی پویا - Dynamic Programming) است. این روش همچون روش تقسیم و حل (Divide and Conquer) بر پایه تقسیم مسئله بر زیرمسئله‌ها کار میکند. اما تفاوت‌های چشم‌گیری با آن دارد.
زمانی که یک مسئله به دو یا چند زیرمسئله تقسیم میشود، دو حالت ممکن است پیش بیاید:
داده‌های زیرمسئله‌ها هیچ اشتراکی با هم نداشته و کاملاً مستقل از هم هستند. نمونه چنین مواردی مرتب‌سازی آرایه‌ها با روش ادغام یا روش سریع است که داده‌ها به دو قسمت تقسیم شده و به صورت مجزا مرتب می‌شوند. در این حالت داده‌های یکی از بخش‌ها هیچ ارتباطی با داده‌های بخش دیگر نداشته و در نتیجهٔ حاصل از آن بخش، اثری ندارند. معمولاً روش تقسیم و حل برای چنین مسائلی کارایی خوبی دارد. داده‌های زیرمسئله وابسته به هم بوده یا با هم اشتراک دارند. در این حالت به اصطلاح زیرمسئله‌ها هم‌پوشانی دارند. نمونه بارز چنین مسائلی محاسبه جمله nام دنباله اعداد فیبوناچی است. روش برنامه‌نویسی پویا غالباً برای الگوریتمهایی به کار برده میشود که در پی حل مسئله‌ای به صورت بهینه می‌باشند.
در روش تقسیم و غلبه ممکن است برخی از زیرمسائلِ کوچکتر، با هم برابر باشند که در این صورت زیرمسائلِ برابر، به‌طور تکراری چندین مرتبه حل می‌شوند که این یکی از معایب روش تقسیم و غلبه است.
ایده‌ای که در فرایِ روش برنامه‌نویسی پویا نهفته‌است، جلوگیری از انجام این محاسبات تکراری است و روشی که معمولاً برای این عمل به کارگرفته میشود استفاده از جدولی برای نگهداری نتایج حاصل از حل زیرمسائل است. در این صورت اگر الگوریتم به زیرمسئله‌ای برخورد کرد که پیش از این حل شده است، به جای حل مجدد آن، نتیجه محاسبه قبلی را از جدول برداشته و کار را با زیرمسئله بعدی دنبال میکند.
روش برنامه‌نویسی پویا یک روش پایین به بالا است (البته همان‌طور که گفته شد، اگر از قبل بدانیم باید کدام زیرمسئله‌ها را حل کنیم تا به مرحله اصلی برسیم، یا این که مجبور نباشیم زیرمسئله‌هایی که استفاده نمی‌شوند را هم حل کنیم) به این معنی که از حل مسائل کوچکتر به حل مسائل بزرگتر می‌رسیم. در حالیکه از نظر ساختاری، روش تقسیم و غلبه روشی است از بالا به پایین، یعنی به‌طور منطقی (نه عملی) پردازش از مسئله اولیه آغاز شده و به سمت پایین و حل مسائلِ کوچکتر، به پیش می‌رود.
مجموع زیرمجموعه و کوله پشتی: اضافه کردن یک متغیر ما بیشتر و بیشتر می‌بینیم که مسائل مربوط به برنامه‌ریزی منبع خیلی خوبی از مسایل الگوریتمی را با انگیزهٔ عملی ارائه می‌دهد. تاکنون مشکلاتی را در نظر گرفتیم که در آن درخواست‌ها با فاصلهٔ زمانی مشخص از یک منبع مشخص‌شده و همچنین مشکلاتی که در آن درخواست‌ها دارای مدت و مهلت هستند، اما فواصل خاصی را که در طی آن باید انجام شود تعیین نشده‌است. در این بخش، ما نسخه‌ای از نوع دوم مشکل را با مدت زمان و مهلت در نظر می‌گیریم، که حل مستقیم با استفاده از تکنیک‌هایی که تاکنون دیده‌ایم، دشوار است.
ما برای حل مسئله از برنامه‌نویسی پویا استفاده خواهیم کرد، اما با یک تغییر: مشخص میشود مجموعه زیرمسئله‌ها به اندازه کافی نخواهدبود، و بنابراین ما در نهایت به ایجاد یک مجموعه غنی‌تر از زیرمسئله‌ها می‌پردازیم. همان‌طور که خواهیم‌دید، این کار با اضافه کردن یک متغیر جدید به بازگشت در زیربرنامهٔ پویا انجام میشود.
سه قدم کلی برای برنامه نویسی داینامیک وجود دارد:
بازگشتی (Recursion) ذخیره سازی(store) Bottom-Up بازگشتی (Recursion) بازگشتی از محاسبه معادله ای که قبلا انجام شده جلو گیری میکند. به این طریق که وقتی یک معادله انجام می شود در بخش ذخیره سازی یا store ، ذخیره می شود و زمانی که صدا زده می شود دیگه نیازی به محاسبه مجدد نیست. به نحوی وقتی برنامه ای بدون استفاده از dynamic programming نوشته می شود هیچ فضایی گرفته نمی شود اما با استفاده از dynamic programming فضایی برای سرعت بخشیدن به برنامه ایجاد می شود که مقادیر memoize می شود( با memorize اشتباه نگیرید) به معنای یادآوری.
زمانی که (fib(3 یک بار برای (fib(4 محاسبه میشود دیگر برای (fib(5 محاسبه نمیشود و memoize می شود.
ذخیره سازی ذخیره سازی همان فضایی است که برای نگه داشتن معادله های محاسبه شده از آن استفاده می کنیم.(برای memoize کردن) Bottom-Up یک روش سریع تر از store یا ذخیره سازیست که با استفاده از آرایه ها انجام می شود. `` به این صورت که برنامه ها در آرایه ها ذخیره می شوند و زمان نیاز صدا زده می شوند و باعث جلو گیری از بار اضافه در برنامه می شوند به نوعی شبیه به store است اما با این تفاوت که همه این ها در یک آرایه ذخیره می شود و نیاز به چند آرایه نیست. همچنین تا مقدار بیشتری میتواند پیشروی کند.
Put simply, a bottom-up algorithm "starts from the beginning," while a recursive algorithm often "starts from the end and works backwards."
For example, if we wanted to multiply all the numbers in the range 1..n1..n, we could use this cute, top-down, recursive one-liner:
public static int product1ToN(int n) { // we assume n >= 1 return (n > 1) ? (n * product1ToN(n-1)) : 1; }
This approach has a problem: it builds up a call stack of size O(n)O(n), which makes our total memory cost O(n)O(n). This makes it vulnerable to a stack overflow error, where the call stack gets too big and runs out of space.
To avoid this, we can instead go bottom-up:
public static int product1ToN(int n) { // we assume n >= 1
}