Dynamic programming — برنامه‌نویسی پویا

برنامه‌نویسی پویا (DP؛ انگلیسی: dynamic programming, DP) روشی برای حل مسائل پیچیده بهینه‌سازی است که بر پایه تجزیه مسئله اصلی به دنباله‌ای از زیرمسائل ساده‌تر استوار است. این روش برای فرآیندهای چندمرحله‌ای تصمیم‌گیری به کار می‌رود، جایی که راه‌حل بهینه کل مسئله از راه‌حل‌های بهینه زیرمسائل آن ساخته می‌شود.

این اصطلاح توسط ریاضیدان آمریکایی ریچارد بلمن در دهه ۱۹۵۰ معرفی شد. در این زمینه، واژه «programming» به معنای «برنامه‌ریزی» یا «تدوین طرح بهینه اقدام» به کار می‌رود و نه نوشتن کد رایانه‌ای.

ویژگی‌ها و قضایای کلیدی

قابلیت اعمال برنامه‌نویسی پویا بر یک مسئله با وجود دو ویژگی بنیادی در آن تعیین می‌شود.

اصل بهینگی بلمن

مفهوم محوری این روش اصل بهینگی بلمن (انگلیسی: Bellman's principle of optimality) است. این اصل بیان می‌کند: صرف‌نظر از حالت اولیه و تصمیم اولیه، تصمیم‌های بعدی باید استراتژی بهینه‌ای را نسبت به حالتی که در نتیجه تصمیم اول حاصل شده، تشکیل دهند.

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

Overlapping Subproblems - زیرمسائل همپوشان

یک مسئله دارای ویژگی زیرمسائل همپوشان (انگلیسی: overlapping subproblems) است، اگر در حل بازگشتی آن، زیرمسائل یکسان بارها و بارها پدیدار شوند. DP با ذخیره راه‌حل زیرمسائلی که پیش از این حل شده‌اند (این فن مموایزیشن یا جدول‌بندی نامیده می‌شود) از محاسبات تکراری اجتناب می‌کند و بدین ترتیب کارایی را در مقایسه با جستجوی بازگشتی ساده به طور چشمگیری افزایش می‌دهد.

معادله بلمن

از اصل بهینگی، رابطه بازگشتی اساسی این روش یعنی معادله بلمن استخراج می‌شود. این معادله «ارزش» (بهترین سود یا هزینه) حالت جاری را به ارزش‌های حالت‌های بعدی مرتبط می‌سازد. به طور کلی برای یک فرآیند چندمرحله‌ای قطعی با تابع هدف افزایشی، این معادله به شکل زیر است:

$V_{k-1}(x)=\underset{y\in U(x)}{max}\{{\phi }_k(x,y)+V_k(f_k(x,y))\}$

که در آن:

• $k$ — شماره گام (از $m$ تا ۱)؛
• $x$ — حالت سیستم در گام $k-1$؛
• $y$ — تصمیم کنترلی که در گام $k$ اتخاذ می‌شود؛
• ${\phi }_k(x,y)$ — سود (یا هزینه) در گام k-ام؛
• $f_k(x,y)$ — تابعی که حالت جدید سیستم را تعیین می‌کند؛
• $V_k(s)$ — مقدار بهینه تابع هدف برای زیرمسئله‌ای که از گام $k$ در حالت $s$ آغاز می‌شود.

معادله به صورت متوالی، معمولاً «از انتها» و با حرکت از گام آخر به گام اول، حل می‌شود.

نمونه‌های کاربرد

• مسئله کوتاه‌ترین مسیر در گراف: این مسئله دارای ویژگی زیرساختار بهینه است، زیرا هر بخشی از کوتاه‌ترین مسیر خود کوتاه‌ترین است. الگوریتم‌های Bellman-Ford و Floyd-Warshall نمونه‌های کلاسیک کاربرد DP برای حل این مسئله هستند.
• مسئله کوله‌پشتی: مسئله پر کردن بهینه کوله‌پشتی با ظرفیت محدود با اشیایی که ارزش و وزن متفاوت دارند. DP با بررسی متوالی اشیا و محاسبه حداکثر ارزش برای تمام مقادیر ممکن ظرفیت باقی‌مانده در هر گام، این مسئله را حل می‌کند.
• مسئله تخصیص منابع: توزیع منابع محدود (مثلاً سرمایه‌گذاری) میان چندین پروژه به منظور بیشینه کردن اثر کلی.

محدودیت‌ها

محدودیت اصلی این روش لعنت ابعاد (انگلیسی: curse of dimensionality) است — اصطلاحی که بلمن برای نامیدن رشد نمایی تعداد حالت‌ها و در نتیجه پیچیدگی محاسباتی با افزایش تعداد متغیرهای توصیف‌کننده حالت سیستم معرفی کرد. این امر کاربرد عملی DP دقیق را برای مسائل با ابعاد بسیار بزرگ محدود می‌سازد.

مفاهیم مرتبط

• تحقیق در عملیات
• نظریه کنترل بهینه
• فرآیند تصمیم‌گیری مارکوف (تعمیم تصادفی)
• معادله Hamilton–Jacobi–Bellman (معادل برای زمان پیوسته)

یادداشت‌ها

</references>