Dynamic programming — متحرک پروگرامنگ

متحرک پروگرامنگ (ایم پی؛ انگ. dynamic programming, DP) — یہ پیچیدہ اصلاحی مسائل کو حل کرنے کا ایک طریقہ ہے، جو اصل مسئلے کو آسان ذیلی مسائل کی ایک ترتیب میں تقسیم کرنے پر مبنی ہے۔ یہ طریقہ کثیر مرحلہ فیصلہ سازی کے عمل پر لاگو ہوتا ہے، جہاں پورے مسئلے کا بہترین حل اس کے ذیلی مسائل کے بہترین حلوں سے تعمیر کیا جا سکتا ہے۔

یہ اصطلاح امریکی ریاضی دان رچرڈ بیل مین نے 1950ء کی دہائی میں متعارف کرائی تھی۔ اس سیاق و سباق میں لفظ «پروگرامنگ» «منصوبہ بندی» یا «عمل کا بہترین منصوبہ تیار کرنے» کے معنوں میں استعمال ہوتا ہے، نہ کہ کمپیوٹر کوڈ لکھنے کے معنوں میں۔

کلیدی خصوصیات اور نظریات

کسی مسئلے پر متحرک پروگرامنگ کے اطلاق کا تعین اس میں دو بنیادی خصوصیات کی موجودگی سے ہوتا ہے۔

بیل مین کا اصولِ اصلاح

اس طریقے کا مرکزی تصور بیل مین کا اصولِ اصلاح (انگ. Bellman's principle of optimality) ہے۔ اس کا کہنا ہے: ابتدائی حالت اور ابتدائی فیصلہ جو بھی ہو، بعد کے فیصلے پہلے فیصلے کے نتیجے میں حاصل ہونے والی حالت کے حوالے سے بہترین حکمت عملی تشکیل دینے چاہئیں۔

دوسرے لفظوں میں، بہترین راستے کا ہر حصہ خود بھی بہترین ہوتا ہے۔ یہ خاصیت مجموعی مسئلے کو آسان ذیلی مسائل کی ترتیب میں تقسیم کرنے اور انہیں تکراری طریقے سے حل کرنے کی اجازت دیتی ہے۔

Overlapping Subproblems - باہم تداخل کرنے والے ذیلی مسائل

کسی مسئلے میں باہم تداخل کرنے والے ذیلی مسائل (انگ. overlapping subproblems) کی خاصیت ہوتی ہے، اگر اس کے تکراری حل کے دوران یکساں ذیلی مسائل بار بار سامنے آتے ہیں۔ DP بار بار کی جانے والی حسابات سے بچنے کی اجازت دیتا ہے، پہلے سے حل شدہ ذیلی مسائل کے جوابات محفوظ کرکے (اس تکنیک کو memoization یا tabulation کہا جاتا ہے)، جو سادہ تکراری تلاش کے مقابلے میں کارکردگی کو نمایاں طور پر بڑھاتا ہے۔

بیل مین کی مساوات

aصولِ اصلاح سے طریقے کا بنیادی تکراری تعلق نکلتا ہے — بیل مین کی مساوات۔ یہ موجودہ حالت کی «قدر» (بہترین فائدہ یا لاگت) کو بعد کی حالتوں کی قدروں سے جوڑتی ہے۔ اضافی ہدفی فنکشن کے ساتھ تعیّن پذیر کثیر مرحلہ عمل کے لیے عام شکل میں یہ اس طرح ہے:

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

جہاں:

• $k$ — مرحلے کا نمبر ($m$ سے 1 تک)؛
• $x$ — مرحلے $k-1$ پر نظام کی حالت؛
• $y$ — مرحلے $k$ پر لیا جانے والا قابلِ کنٹرول فیصلہ؛
• ${\phi }_k(x,y)$ — k-ویں مرحلے پر فائدہ (یا لاگت)؛
• $f_k(x,y)$ — نظام کی نئی حالت متعین کرنے والا فنکشن؛
• $V_k(s)$ — مرحلے $k$ پر حالت $s$ سے شروع ہونے والے ذیلی مسئلے کے لیے ہدفی فنکشن کی بہترین قدر۔

مساوات کو یکے بعد دیگرے حل کیا جاتا ہے، عام طور پر «آخر سے»، یعنی آخری مرحلے سے پہلے مرحلے کی طرف بڑھتے ہوئے۔

استعمال کی مثالیں

• گراف میں مختصر ترین راستے کا مسئلہ: اس مسئلے میں بہترین ذیلی ساخت کی خاصیت ہے، کیونکہ مختصر ترین راستے کا ہر حصہ خود بھی مختصر ترین ہوتا ہے۔ بیل مین-فورڈ اور فلائیڈ-وارشل الگورتھم اس مسئلے کو حل کرنے کے لیے DP کے اطلاق کی کلاسیکی مثالیں ہیں۔
• بیگ کا مسئلہ: مختلف قدر اور وزن والی اشیاء سے محدود گنجائش کے بیگ کو بہترین طریقے سے بھرنے کا مسئلہ۔ DP اس مسئلے کو حل کرنے کی اجازت دیتا ہے، اشیاء کو یکے بعد دیگرے ملاحظہ کرتے ہوئے اور ہر مرحلے پر باقی گنجائش کی تمام ممکنہ قدروں کے لیے زیادہ سے زیادہ قدر کا حساب لگاتے ہوئے۔
• وسائل کی تقسیم کا مسئلہ: مجموعی اثر کو زیادہ سے زیادہ کرنے کے لیے محدود وسائل (مثلاً سرمایہ کاری) کو متعدد منصوبوں کے درمیان تقسیم کرنا۔

حدود

طریقے کی سب سے بڑی حد جہت کا لعنت (انگ. curse of dimensionality) ہے — یہ اصطلاح بیل مین نے حالتوں کی تعداد میں اضافے اور اس کے نتیجے میں حسابی پیچیدگی میں اس وقت تیز رفتار اضافے کو ظاہر کرنے کے لیے متعارف کرائی تھی جب نظام کی حالت بیان کرنے والے متغیرات کی تعداد بڑھتی ہے۔ یہ بہت بڑے پیمانے کے مسائل کے لیے عین DP کے عملی اطلاق کو محدود کرتا ہے۔

متعلقہ تصورات

• آپریشنز ریسرچ
• بہترین کنٹرول کا نظریہ
• مارکوف فیصلہ سازی کا عمل (اسٹاکیسٹک تعمیم)
• ہیملٹن — جیکوبی — بیل مین مساوات (مسلسل وقت کا ہم پلہ)

حواشی

</references>