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

برنامه نویسی پویا به‌عنوان یک تکنیک برنامه نویسی تعریف می‌شود که در آن یک مسئله الگوریتمی ابتدا به زیرمسائل تقسیم می‌شود، نتایج ذخیره می‌شوند و سپس زیرمسائل برای یافتن راه حل کلی بهینه می‌شوند. در این مقاله از نزدیک به بررسی نحوه عملکرد برنامه نویسی پویا با ذکر مثال می‌پردازیم.

نحوه کارکرد برنامه نویسی پویا

برنامه نویسی پویا با ذخیره کردن نتیجه زیرمسائل کار می‌کند تا زمانی که راه‌حل‌های آنها مورد نیاز است، در دسترس باشند و نیازی به محاسبه مجدد آنها نداشته باشیم. در این تکنیک ذخیره‌سازی، با ذخیره مقادیر در آرایهآموزش آرایه در ساختمان داده به زبان ساده و از 0 تا 100در این مقاله موارد زیر بررسی شده است : 1- آرایه چیست 2- انواع اندیس گذاری در آرایه 3- انواع آرایه 4- محاسبه آدرس در آرایه 5- محاسبه شماره در آرایه 6- آرایه در برنامه نویسی 7- مزایای استفاده از آرایه، در زمان محاسبات زیرمسائل که قبلاً با آنها برخورد کرده‌ایم، صرفه‌جویی می‌کنیم. برای مثال در شبه کد زیر که از روش برنامه نویسی پویا برای محاسبه سری فیبوناچی استفاده می‌کند، مقادیر زیرمسائل را در آرایه m ذخیره می‌کنیم.

var m = map(0 → 0, 1 → 1)
function fib(n)
  if key n is not in map m 
    m[n] = fib(n − 1) + fib(n − 2)
  return m[n]

var m = map(0 → 0, 1 → 1)
function fib(n)
  if key n is not in map m 
    m[n] = fib(n − 1) + fib(n − 2)
  return m[n]

کپی کردن کد

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

function fib(n)
if n = 0
  return 0
else
  var prevFib = 0, currFib = 1
  repeat n − 1 times
    var newFib = prevFib + currFib
    prevFib = currFib
    currFib  = newFib
return currentFib

function fib(n)
if n = 0
  return 0
else
  var prevFib = 0, currFib = 1
  repeat n − 1 times
    var newFib = prevFib + currFib
    prevFib = currFib
    currFib  = newFib
return currentFib

کپی کردن کد

مثال برنامه نویسی پویا

حالا که با نحوه کارکرد برنامه نویسی پویا آشنا شدیم، با یک مثال می‌توانیم آن را بهتر درک کنیم. بیایید دنباله فیبوناچیدنباله فیبوناچی یا سری فیبوناچی چیه؟ – آموزش اعداد فیبوناچیاین مقاله عالی دنباله فیبوناچی یا سری فیبوناچی را آموزش داده، سپس الگوریتم فیبوناچی و برنامه بازگشتی محاسبه nامین عدد فیبوناچی در پایتون و C را آورده است را تا جمله پنجم پیدا کنیم. سری فیبوناچی دنباله‌ای از اعداد است که در آن هر عدد حاصل جمع دو عدد قبلی است؛ به عنوان مثال: 0,1,1,2,3 که در این‌جا، هر عدد حاصل جمع دو عدد قبلی است.

فرض کنید جمله nام دنباله را می‌خواهیم پیدا کنیم:

• اگر n = 1 باشد، 1 را برگردانید.
• در غیر این صورت، مجموع دو عدد قبل را برگردانید.

ما دنباله فیبوناچی را تا جمله پنجم محاسبه می کنیم:

• جمله اول 0 است.
• جمله دوم 1 است.
• جمله سوم مجموع 0 (از مرحله 1) و 1 (از مرحله 2) است که 1 است.
• جمله چهارم مجموع جمله سوم (از مرحله 3) و جمله دوم (از مرحله 2) است یعنی 1 + 1 = 2
• جمله پنجم مجموع جمله چهارم (از مرحله 4) و جمله سوم (از مرحله 3) است یعنی 2 + 1 = 3

پس از طی مراحل فوق، ما دنباله 0،1،1،2،3 را داریم. در این مثال از نتایج مراحل قبلی مطابق شکل زیر استفاده کرده ایم. به این روش، برنامه نویسی پویا می‌گویند.

F(0) = 0
F(1) = 1
F(2) = F(1) + F(0)
F(3) = F(2) + F(1)
F(4) = F(3) + F(2)

F(0) = 0
F(1) = 1
F(2) = F(1) + F(0)
F(3) = F(2) + F(1)
F(4) = F(3) + F(2)

کپی کردن کد

مقایسه الگوریتم حریصانه با برنامه نویسی پویا

الگوریتم های حریصانه شبیه برنامه نویسی پویا هستند، به این معنا که هر دو ابزاری برای بهینه‌سازی هستند. با این حال، الگوریتم‌های حریصانه به دنبال راه‌حل‌های بهینه محلی یا به عبارت دیگر، یک انتخاب حریصانه هستند؛ به امید یافتن یک بهینه جهانی، از این رو الگوریتم‌های حریصانه می‌توانند حدس‌هایی را ایجاد کنند که در آن زمان بهینه به نظر می‌رسند، اما در نهایت گران‌تر می‌شوند و بهینه جهانی را تضمین نمی‌کنند. از سوی دیگر، برنامه نویسی پویا راه‌حل بهینه را برای زیرمسائل پیدا می‌کند و سپس یک انتخاب آگاهانه برای ترکیب نتایج آن زیرمسائل برای یافتن بهینه‌ترین راه‌حل انجام می‌دهد.

مقایسه الگوریتم تقسیم و غلبه با برنامه نویسی پویا

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

کاربردهای برنامه نویسی پویا

کاربردهای مختلف برنامه نویسی پویا عبارتند از:

• پیدا کردن طولانی‌ترین دنباله متداول
• یافتن کوتاه‌ترین مسیر
• یافتن حداکثر سود با سایر محدودیت‌های ثابت
• برنامه‌ریزی کارها در پردازندهپردازنده (CPU) چیست؟ بررسی انواع، وظایف و کاربردهاسی پی یو قلب کامپیوتر و کامپیوتر قلب دنیای کنونی است، بنابراین در این صفحه به معرفی و بررسی سی‌پی‌یو یا همان پردازنده مرکزی (CPU) پرداخته‌ شده، و بطور کامل توضیح داده‌ایم که CPU از چه بخش هایی تشکیل شده و هر بخش چه وظایف و مشخصاتی دارد. 
• بیوانفورماتیک
• راه حل‌های جستجوی بهینه
• الگوریتم بلمن فورد

مزایا و معایب برنامه نویسی پویا

برنامه نویسی پویا مزایای بسیاری دارد، از جمله موارد زیر:

• درک و پیاده‌سازی رویکرد از بالا به پایین آسان است. در این رویکرد، مسائل به بخش‌های کوچک‌تری تقسیم می‌شوند که به کاربران کمک می‌کند تا کارهایی را که باید انجام دهند، شناسایی کنند. با هر مرحله مسائل پیچیده، کوچک‌تر، ساده‌تر و در نتیجه حل آنها آسان‌تر می‌شوند، حتی ممکن است برخی از قطعات برای همین مسئله قابل استفاده مجدد باشند.
• رویکرد بالا به پایین اجازه می دهد تا زیرمسائل در صورت درخواست حل شوند. رویکرد بالا به پایین باعث می‌شود مسائل به بخش‌های کوچک‌تر تقسیم شوند و راه‌حل‌های آنها برای استفاده مجدد ذخیره شوند سپس کاربران می‌توانند راه‌حل‌های مربوط به هر بخش را جستجو کنند.
• اشکال زدایی (Debugging)دیباگ چیست؟ معرفی روش‌‌ها و ابزارهای دیباگینگ(اشکال زدایی)این مقاله عالی مفاهیم دیباگ (debug)، دیباگینگ (Debugging) یا همان اشکال زدایی، دیباگر (Debugger) را معرفی و همچنین روش‌‌ها و ابزارهای دیباگینگ را بررسی کرده در رویکرد بالا به پایین آسان است. بخش‌بندی مسائل به بخش‌های کوچک به کاربران اجازه می‌دهد تا راه‌حل را به سرعت دنبال کنند و محل وقوع خطا را تعیین کنند.
• رویکرد پایین به بالا در مورد زیرمسائل کوچک قابل استفاده مجدد، تصمیم‌گیری می‌کند و سپس تصمیم می‌گیرد که چگونه آنها را در کنار هم قرار دهند تا یک مسئله بزرگ را حل کنند.
• رویکرد پایین به بالا، بازگشت را حذف می‌کند بنابراین استفاده کارآمد از فضای حافظهحافظه در کامپیوتر، همه چیز در مورد حافظه در معماری کامپیوتردر این مقاله به بررسی کامل حافظه در کامپیوتر، انواع حافظه در کامپیوتر، کش، روش‌های آدرس دهی کش، نگاشت آدرس و موارد دیگر می‌پردازیم را ارتقا می‌دهد. علاوه بر این، منجر به کاهش پیچیدگی زمانی هم می‌شود.

معایب برنامه نویسی پویا به پایین عبارتند از:

• رویکرد بالا به پایین، از تکنیک بازگشتی استفاده می‌کند که حافظه بیشتری را در پشتهساختمان داده پشته ⚡️ پشته چیست؟ کاربرد پشته در ساختمان دادهاین مقاله عالی توضیح داده که پشته چیست و کاربرد پشته در ساختمان داده چیست، همچنین نحوه کارکرد پشته، پیاده سازی پشته و عملیات های پشته را معرفی کرده اشغال می‌کند که منجر به کاهش عملکرد کلی می‌شود. علاوه بر این، هنگامی که بخش بازگشتی خیلی عمیق است، سرریز پشته رخ می‌دهد.

جمع‌بندی

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

مطالب مرتبط

همه مقالات

معرفی انواع عملگرها در برنامه نویسی⚡️منطقی، محاسباتی و بیتی

هکرها از چه زبان برنامه نویسی استفاده میکنند

معروف ترین الگوریتم ‌های برنامه نویسی

کاربرد الگوریتم در برنامه نویسی