برنامه‌نویسی پویا (Dynamic Programming) چیست؟

برنامه‌نویسی پویا بر پایه چه اصولی استوار است؟

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

1. زیرمسئله‌بندی: مسئله اصلی به زیرمسائل کوچک‌تر تقسیم می‌شود.
2. تعریف تابع بازگشتی: تابعی که بر اساس زیرمسائل کوچک‌تر، مقدار مسئله اصلی را محاسبه می‌کند.
3. حفظ و استفاده از جدول: نتایج زیرمسائل در یک جدول ذخیره می‌شوند تا در زمان‌های بعدی قابل استفاده باشند.
4. حل مسئله به صورت بالا به پایین یا پایین به بالا: معمولا روش‌های برنامه‌نویسی پویا به یکی از این دو روش استناد می‌کنند.

چه زبان‌هایی از برنامه‌نویسی پویا پشتیبانی می‌کنند؟

برنامه‌نویسی پویا (Dynamic Programming) یک روش عمومی در علم کامپیوتر است و می‌توان از آن در تقریباً هر زبان برنامه‌نویسی استفاده کرد. برنامه‌نویسی پویا بیشتر یک الگوریتم و روش محاسباتی است تا یک ویژگی خاصی از زبان برنامه‌نویسی. با این حال، برخی از زبان‌های برنامه‌نویسی خاص و کتاب‌خانه‌ها ممکن است ویژگی‌ها و ابزارهای خاصی را برای پیاده‌سازی برنامه‌نویسی پویا در اختیار برنامه‌نویسان قرار دهند. در زیر، چند زبان برنامه‌نویسی معروف را ذکر می‌کنم که از برنامه‌نویسی پویا پشتیبانی می‌کنند:

• پایتون: یک زبان برنامه‌نویسی محبوب است که بسیاری از کتابخانه‌ها و ابزارهای مرتبط با برنامه‌نویسی پویا را دارد. کتابخانه‌هایی مانند NumPy و Pandas برای محاسبات عددی و تحلیل داده‌ها و کتابخانه‌هایی مانند dpdb سرنام Dynamic Programming in Python برای پیاده‌سازی برنامه‌نویسی پویا در Python وجود دارند.
• جاوا: برنامه‌نویسان می‌توانند از جاوا در ارتباط با برنامه‌نویسی پویا استفاده کنند. استفاده از ساختارهای داده مانند آرایه‌ها، ماتریس‌ها و کلاس‌ها در Java می‌تواند به پیاده‌سازی برنامه‌نویسی پویا کمک کند.
• سی‌پلاس‌پلاس: یک زبان قدرتمند است که امکاناتی برای برنامه‌نویسی پویا فراهم می‌کند. می‌توان از آرایه‌ها، ساختارهای داده شخصی‌سازی و کتابخانه‌های مرتبط با برنامه‌نویسی پویا در سی پلاس پلاس استفاده کرد.

علاوه بر این، برنامه‌نویسی پویا در زبان‌های دیگری مانند C#, Ruby، و JavaScript نیز قابل اجرا است. در واقع، در اصل، برنامه‌نویسی پویا یک الگوریتم عمومی است و می‌توان از آن در تقریبا هر زبان برنامه‌نویسی استفاده کرد.

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

استفاده از برنامه‌نویسی پویا (Dynamic Programming) معمولا در موارد زیر توصیه می‌شود:

1.  مسئله‌های بهینه‌سازی: وقتی با مسئله‌ای روبرو هستید که به دنبال یافتن راه‌حل بهینه برای یک معیار خاص هستید، برنامه‌نویسی پویا می‌تواند مفید باشد. این مسائل معمولا شامل مسائل مسیریابی، بسته‌بندی، زمان‌بندی و بهینه‌سازی سایر مسائل مشابه هستند.
2.  مسائل با ساختارهای تکراری: وقتی با ساختارهای تکراری در مسئله خود روبرو هستید، برنامه‌نویسی پویا می‌تواند به شما کمک کند. در این صورت، می‌توانید نتایج زیرمسائل را ذخیره کرده و در زمان‌های بعدی استفاده کنید، به جای محاسبه مجدد آن‌ها.
3.  مسائل با ارتباط‌های تداخلی: وقتی مسئله شما دارای ارتباط‌های تداخلی بین زیرمسائل است و حل هر زیرمسئله به حل دیگر زیرمسائل وابسته است، برنامه‌نویسی پویا می‌تواند بهترین راه حل را ارائه دهد. این روش به شما امکان می‌دهد تا از نتایج قبلی استفاده کنید و حل مسئله را به صورت بهینه‌تر انجام دهید.
4.  مسائل با تعداد حالت‌های محدود: وقتی تعداد حالت‌های ممکن در مسئله شما محدود است، برنامه‌نویسی پویا می‌تواند به شما کمک کند. با استفاده از ذخیره نتایج محاسبات قبلی، می‌توانید زمان اجرای الگوریتم را به طور قابل توجهی کاهش دهید.

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

برنامه‌نویسی پویا برای چه مسائلی مناسب است؟

بر مبنای رویکرد برنامه‌نویسی پویا، می‌توان برای مجموعه‌ای از مسائل مختلف از جمله مسائل بهینه‌سازی، جستجو، ترکیبیات و مسائل ساختاری استفاده کرد. در زیر، چند مثال از مسائلی که برنامه‌نویسی پویا برای آن‌ها مناسب است را بررسی می‌کنیم:

1.  مسئله پیدا کردن مسیر کوتاه: وقتی که به دنبال یافتن مسیر کوتاه در یک گراف یا شبکه با شرایط مشخص هستید، می‌توانید از برنامه‌نویسی پویا استفاده کنید. مسائلی مانند مسئله کوتاه‌ترین مسیر در یک گراف و مسئله کوتاه‌ترین زنجیره ماتریسی (Shortest Matrix Chain) می‌توانند با استفاده از برنامه‌نویسی پویا حل شوند.
2.  مسئله بسته‌بندی کالا: در این مسئله، هدف پر کردن یک کیسه (بسته) با کالاهای مختلف است به‌طوری‌که جمع ارزش کالاها حداکثر شود و حجم بسته‌ها از مقدار مجاز عبور نکند. با استفاده از برنامه‌نویسی پویا و روش‌هایی مانند برنامه‌نویسی پویا دو بعدی (2D Dynamic Programming)، می‌توان بهینه‌ترین راه حل را برای این مسئله پیدا کرد.
3.  مسئله برنامه‌ریزی زمانی (Scheduling Problem): در این مسئله، باید یک سری وظایف را در زمان‌بندی مشخصی انجام داد. هدف معمولا کمینه کردن زمان کلی انجام وظایف یا حجم منابع مورد استفاده است. برنامه‌نویسی پویا می‌تواند در حل این نوع مسائل با استفاده از تکنیک‌هایی مانند برنامه‌نویسی پویا تک بعدی به کمکتان بیاید.
4.  مسئله تقسیم و حل (Divide and Conquer): برخی از مسائل تقسیم و حل از طریق برنامه‌نویسی پویا قابل حل هستند. در این روش، مسئله اصلی به زیرمسائل کوچکتر تقسیم می‌شود و سپس نتایج زیرمسائل ذخیره شده و برای حل مسئله اصلی استفاده می‌شوند. مسئله محاسبه بزرگترین زیردنباله مشترک(مثل Longest Common Subsequence) یکی از مثال‌هایی از این دسته از مسائل است که با استفاده از برنامه‌نویسی پویا قابل حل هستند.

موارد یاد شده تنها چند نمونهی از مسائلی هستند که برنامه‌نویسی پویا می‌تواند برای آن‌ها مناسب باشد. هر چند که برنامه‌نویسی پویا در بسیاری از مسائل مختلفی کاربرد دارد و می‌تواند به صورت خلاصه و یا بسیار پیچیده‌تر در راه حل مسائل بهینه و کمک کند.

برای چه مسائلی نباید از برنامه‌نویسی پویا استفاده کرد؟

برنامه‌نویسی پویا (Dynamic Programming) روشی قدرتمند برای حل مسائل محاسباتی است، اما در برخی موارد ممکن است استفاده از آن نسبت به روش‌های دیگر مناسب نباشد. در زیر چند مثال از مسائلی که ممکن است استفاده از برنامه‌نویسی پویا در آنها موثر نباشد را بررسی می‌کنیم:

1. مسائل با حالت‌های بسیار بزرگ: در صورتی که تعداد حالت‌ها به طور قابل توجهی بزرگ باشد، استفاده از برنامه‌نویسی پویا ممکن است منجر به مصرف زیاد حافظه و زمان اجرا شود. در این موارد، روش‌های دیگر مانند الگوریتم‌های بازگشتی یا الگوریتم‌های تقسیم و حل ممکن است بهترین گزینه باشند.
2.  مسائل با تغییر پویا: در صورتی که ورودی یا شرایط مسئله به طور پویا تغییر کنند، استفاده از برنامه‌نویسی پویا ممکن است منجر به حاشیه‌سازی و محاسبات تکراری شود. در این موارد، روش‌هایی که از حافظه موقت استفاده نمی‌کنند و به صورت داینامیک به تغییرات پاسخ می‌دهند، مثل الگوریتم‌های بازگشتی، ممکن است بهترین گزینه باشند.
3. مسائل با روابط تکراری: در برخی موارد، روابط مسئله به صورت تکراری و خطی نیستند، بلکه به صورت غیرخطی و پیچیده‌تری است. در این صورت، استفاده از روش‌های دیگر مانند تکنیک‌های محاسباتی مانند تقسیم و حل، برنامه‌نویسی خطی، یا الگوریتم‌های ترکیبی ممکن است بهترین راه حل باشد.

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

برنامه‌نویسی پویا و برنامه‌نویسی تابعی چه تفاوت‌ها و شباهت‌هایی دارند؟

برنامه‌نویسی پویا (Dynamic Programming) و برنامه‌نویسی تابعی (Functional Programming) دو روش متفاوت در برنامه‌نویسی هستند که هرکدام ویژگی‌ها و شباهت‌های خود را دارند. در زیر به تفاوت‌ها و شباهت‌های اصلی بین این دو روش می‌پردازم:

تفاوت‌ها:

1.  فلسفه برنامه‌نویسی: برنامه‌نویسی پویا بیشتر در تمرکز بر حل مسائل محور است و برای بهینه‌سازی و حل مسائل پیچیده با استفاده از تکنیک‌های داینامیک طراحی شده است. از طرف دیگر، برنامه‌نویسی تابعی بیشتر در تمرکز بر ساختار داده و تابع‌ها است و برای برنامه‌نویسی با استفاده از توابع بدون حالت (stateless) و ایجاد برنامه‌های بدون اثر جانبی (side-effect free) استفاده می‌شود.
2.  حالت‌دار در مقابل بدون حالت (Stateful vs. Stateless): برنامه‌نویسی پویا معمولا از تغییر وضعیت و حافظه موقت برای ذخیره و استفاده مجدد از نتایج محاسبات استفاده می‌کند. این به معنی ایجاد اثرات جانبی و وابستگی به حالت برنامه است. از طرف دیگر، برنامه‌نویسی تابعی بیشتر از توابع بدون حالت استفاده می‌کند که هیچ تغییر وضعیت مشترکی ندارند و تنها بر اساس ورودی‌های خود عمل می‌کنند.
3.  شیوه برنامه‌نویسی: برنامه‌نویسی پویا معمولا بر اساس الگوریتم‌ها و تکنیک‌های محاسباتی مبتنی بر حلقه (loop-based) است. از این روش برای حل مسائل با تکرار و وابستگی به حالت قبلی استفاده می‌شود. از سوی دیگر، برنامه‌نویسی تابعی بر اساس توابع و ترکیب آنها برای حل مسائل استفاده می‌شود. این شیوه برنامه‌نویسی بر تعریف توابع خالص (pure functions) و استفاده از تکنیک‌های مانند تطبیق الگو و توابع بازگشتی تمرکز دارد.

شباهت‌ها:

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

یک مثال عملی از برنامه‌نویسی پویا

یک مثال عملی و کاربردی از برنامه‌نویسی پویا می‌تواند مسئله پیدا کردن تعداد روش‌های ممکن برای پرداخت یک مبلغ به واحدهای سکه‌ای مشخص باشد. فرض کنید می‌خواهید یک مبلغ مشخص را با استفاده از واحدهای سکه‌ای مانند 1، 5 و 10 به چند روش ممکن پرداخت کنید. برای حل این مسئله، می‌توان از روش برنامه‌نویسی پویا بهره برد. فرض کنید  amount  مبلغ مورد نظر باشد و  coins  لیست واحدهای سکه‌ای باشد. در این صورت، می‌توانیم یک آرایه دیگر به نام  dp  ایجاد کنیم که در آن  dp[i]  تعداد روش‌های ممکن برای پرداخت مبلغ  i  با استفاده از واحدهای سکه‌ای مشخص است. الگوریتم برنامه‌نویسی پویا برای این مسئله به صورت زیر است:

1. مقدار اولیه  dp[0]  برابر 1 قرار می‌دهیم، زیرا تنها یک روش ممکن برای پرداخت مبلغ صفر است و آن هم عدم استفاده از هیچ سکه‌ای است.

2. برای هر  coin  در  coins  و برای هر  i  در بازه  [coin, amount] ، عملیات زیر را انجام می‌دهیم:

   -  dp[i]  را با  dp[i]  جمع می‌کنیم (به عبارت دیگر، تعداد روش‌های قبلی را با تعداد روش‌های جدید جمع می‌کنیم).

   -  dp[i]  را با  dp[i-coin]  جمع می‌کنیم. این عملیات نشان می‌دهد که می‌توانیم یک سکه به مبلغ  coin  را به تعداد  dp[i-coin]  روش به مبلغ  i  اضافه کنیم.

در نهایت،  dp[amount]  تعداد روش‌های ممکن برای پرداخت مبلغ  amount  با استفاده از واحدهای سکه‌ای مشخص است.

به عنوان مثال، فرض کنید می‌خواهید مبلغ 15 را با استفاده از واحدهای سکه‌ای {1, 5, 10} پرداخت کنید. با استفاده از الگوریتم برنامه‌نویسی پویا، مقدار  dp[15]  برابر 4 خواهد بود، که نشان می‌دهد چهار روش ممکن برای پرداخت مبلغ 15 وجود دارد. الگوریتم برنامه‌نویسی پویا برای مسئله پرداخت مبلغ با واحد سکه‌ به زبان پایتون به صورت زیر است:

def coin_change(amount, coins):

    dp = [0] * (amount + 1)

    dp[0] = 1

    for coin in coins:

        for i in range(coin, amount + 1):

            dp[i] += dp[i - coin]

    return dp[amount]

اکنون می‌توانید از این تابع برای محاسبه تعداد روش‌های ممکن برای پرداخت مبلغ مورد نظر استفاده کنید. به عنوان مثال، برای پرداخت مبلغ 15 با استفاده از واحدهای سکه‌ای {1، 5، 10}، کد زیر را می‌توانید اجرا کنید:

amount = 15

coins = [1, 5, 10]

result = coin_change(amount, coins)

print("Number of ways to make change:", result)

این کد خروجی "Number of ways to make change: 4" را نمایش خواهد داد، که نشان می‌دهد که چهار روش ممکن برای پرداخت مبلغ 15 با واحدهای سکه‌ای {1، 5، 10} وجود دارد.

الگوریتم برنامه‌نویسی پویا برای مسئله پرداخت مبلغ با سکه‌ به صورت زیر عمل می‌کند:

1. ابتدا یک آرایه به نام  dp  ایجاد می‌کنیم که طول آن برابر با مبلغ  amount  است. همچنین، تمام عناصر  dp  را به صفر مقداردهی اولیه می‌کنیم.

2. مقدار اولیه  dp[0]  را برابر 1 قرار می‌دهیم زیرا تنها یک روش ممکن برای پرداخت مبلغ صفر وجود دارد که عدم استفاده از هیچ سکه‌ای است.

3. سپس برای هر واحد سکه در لیست  coins ، و برای هر  i  در بازه  [coin, amount] ، عملیات زیر را انجام می‌دهیم:

   -  dp[i]  را با  dp[i]  جمع می‌کنیم، یعنی تعداد روش‌های قبلی برای پرداخت مبلغ  i  را به جواب کلی اضافه می‌کنیم.

   -  dp[i]  را با  dp[i-coin]  جمع می‌کنیم. این عملیات نشان می‌دهد که می‌توانیم یک سکه به مبلغ  coin  را به تعداد  dp[i-coin]  روش به مبلغ  i  اضافه کنیم.

4. پس از اتمام حلقه‌ها،  dp[amount]  حاوی تعداد روش‌های ممکن برای پرداخت مبلغ  amount  با استفاده از واحدهای سکه‌ای مشخص است.

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

می‌توانیم تابع coin_change را برای مبلغ و واحدهای سکه‌ای دلخواهی استفاده کنیم؟

بله، می‌توانیم تابع coin_change را به گونه‌ای تغییر دهیم که مبلغ و لیست واحدهای سکه‌ای را به عنوان ورودی دریافت کند. در ادامه، نسخه اصلاح شده‌ تابع coin_change را برای استفاده با مبلغ و واحدهای سکه‌ای دلخواه بازنویسی می‌کنیم.

def coin_change(amount, coins):

    dp = [0] * (amount + 1)

    dp[0] = 1

    for coin in coins:

        for i in range(coin, amount + 1):

            dp[i] += dp[i - coin]

    return dp[amount]

شما می‌توانید این تابع را با مبلغ مورد نظر و لیست واحدهای سکه‌ای مورد نظر فراخوانی کنید. به عنوان مثال، برای پرداخت مبلغ 25 با استفاده از واحدهای سکه‌ای {1، 5، 10، 25}، می‌توانید کد زیر را استفاده کنید:

amount = 25

coins = [1, 5, 10, 25]

result = coin_change(amount, coins)

print("Number of ways to make change:", result)

این کد خروجی "Number of ways to make change: 13" را نمایش خواهد داد، که نشان می‌دهد که 13 روش ممکن برای پرداخت مبلغ 25 با واحدهای سکه‌ای {1، 5، 10، 25} وجود دارد.

می‌توانیم تابع coin_change را با واحدهای سکه‌ای دیگری از جمله {1، 2، 5، 10} استفاده کنیم؟

پاسخ مثبت است. در واقع، الگوریتم coin_change قابلیت استفاده با هر مجموعه واحدهای سکه‌ای صحیحی را دارد. برای استفاده از واحدهای سکه‌ای {1، 2، 5، 10}، می‌توانیم از کد زیر استفاده کنیم:

amount = 15

coins = [1, 2, 5, 10]

result = coin_change(amount, coins)

print("Number of ways to make change:", result)

این کد خروجی "Number of ways to make change: 22" را نمایش خواهد داد، که نشان می‌دهد که 22 روش ممکن برای پرداخت مبلغ 15 با واحدهای سکه‌ای {1، 2، 5، 10} وجود دارد.

بنابراین، با تغییر واحدهای سکه‌ای در لیست coins، می‌توانیم از تابع coin_change برای محاسبه تعداد روش‌های ممکن برای پرداخت هر مبلغ دلخواه با استفاده از واحدهای سکه‌ای مورد نظر استفاده کنیم.