ডাইনামিক প্রোগ্রামিং

টেমপ্লেট:Distinguishডাইনামিক প্রোগ্রামিং হল কম্পিউটারে প্রোগ্রাম লিখার এবং গাণিতিক নিখুঁতীকরণের একটি পদ্ধতি। রিচার্ড বেলম্যান ১৯৬০ এর দশকে এই পদ্ধতিটি উদ্ভাবন করেন এবং বর্তমানে অনেকসংখ্যক কর্মক্ষেত্র, অ্যারোস্পেস প্রকৌশল হতে অর্থনীতিতে এটি ব্যবহৃত হচ্ছে। উভয় প্রসঙ্গে একটি জটিল সমস্যাকে সহজতর এবং ক্ষুদ্রতর সমস্যায় ভাগ করে পুনরাবৃত্তিয় (রিকার্সিভ) ভাবে সমাধান করাকে এটি নির্দেশ করে। যদিও কিছু বাছাইকরণ (ডিসিশন) সমস্যা এ পদ্ধতিতে বিভাজন সম্ভব নয়, যে বাছাইগুলো সময়ের একাধিক বিন্দুতে অবস্থান করে সেগুলিকে পুনরাবৃত্তভাবে ভাগ করা সম্ভব। অনুরূপভাবে কম্পিউটার বিজ্ঞানে, যদি একটি বড় সমস্যাকে ছোট ছোট সমস্যায় বিভক্ত করে সবগুলোকে পুনরাবৃত্তভাবে সমাধানের মাধ্যমে পুরো সমস্যাটির সন্তোষজনকভাবে সমাধান করা সম্ভব, তাহলে এটির অপ্টিমাল সাবস্ট্রাকচার বৈশিষ্ট রয়েছে বলে ধরে নেয়া যায়।

যদি উপ-সমস্যাগুলিকে পুনরাবৃত্তিয়ভাবে বৃহৎ সমস্যার মধ্যে আবদ্ধ করা যায় যাতে করে ডাইনামিক প্রোগ্রামিং এর পদ্ধতিগুলি এর ওপর প্রয়োগযোগ্য হয়, তাহলে বৃহত্তর সমস্যার মান ও ক্ষুদ্রতর সমস্যাগুলির মানের মাঝে একটি সম্পর্ক রয়েছে বলে ধরে নেয়া যেতে পারে। গাণিতিক অপ্টিমাইযেশন বিদ্যায় এই সম্পর্ককে বলা হয় বেলম্যান সমীকরণ।

সারাংশ

গাণিতিক অপ্টিমাইজেশান

গাণিতিক অপ্টিমাইজেশানের পরিভাষায়, ডাইনামিক প্রোগ্রামিং এর সাহায্যে সাধারণত বোঝানো হয়, কোন একটি বৃহৎ বিষয়ে সিদ্ধান্ত গ্রহণকে সময়ের সাথে সাথে ভেঙে একাধিক ছোট ছোট সিদ্ধান্ত গ্রহণের পদক্ষেপে বিভক্ত করার প্রক্রিয়া। মনে করি, মূল্যমান ফাংশনের একটি অনুক্রম V₁, V₂, ..., V_n এবং সময় i=1 হতে n পর্যন্ত সিস্টেমের অবস্থা নির্দেশকারী y কে উক্ত অনুক্রম আর্গুমেন্ট হিসেবে গ্রহণ করে। n সময়ে y অবস্থার প্রাপ্ত মানের দ্বারা V_n(y) কে সংজ্ঞায়িত করা হয়।

নিয়ন্ত্রণ তত্ত্ব

নিয়ন্ত্রণ তত্ত্বে একটি চিরাচরিত সমস্যা হচ্ছে, কোন একটি সিস্টেম $\dot{𝐱}(t)=𝐠(𝐱(t),𝐮(t),t)$কে অবিচ্ছিন্ন সময় অন্তর $t_0\le t\le t_1$এর মাঝে গ্রহণযোগ্য আবক্র পথ ${𝐱}^{\ast }$অনুসরণ করে এবং একটি কস্ট ফাংশন মিনিমাইজে বাধ্য করতে গেলে যে গ্রহণযোগ্য নিয়ন্ত্রণ ${𝐮}^{\ast }$দরকার সেটি বের করা।

$J=b(𝐱(t_1),t_1)+\underset{t_0}{\overset{t_1}{\int }}f(𝐱(t),𝐮(t),t)\mathrm{d}t$

এই সমস্যার সমাধান হল, একটি সন্তোষজনক নিয়ন্ত্রণ বিধি অথবা বিধান ${𝐮}^{\ast }=h(𝐱(t),t)$এর ব্যবস্থা করা, যা একটি সন্তোষজনক আবক্রপথ ${𝐱}^{\ast }$এবং উন্নততর ক্ষতি-ফাংশন $J^{\ast }$এর সৃষ্টি করে। শেষোক্ত ফাংশন ডাইনামিক প্রোগ্রামিং এর মৌলিক সমীকরণ মেনে চলে:

$-J_t^{\ast }=\underset{𝐮}{\min }\{f(𝐱(t),𝐮(t),t)+J_x^{\ast 𝖳}𝐠(𝐱(t),𝐮(t),t)\}$

একটি আংশিক ব্যবকলনীয় সমীকরণ যেটি হ্যামিল্টন – জ্যাকোবি – বেলম্যান সমীকরণ হিসেবে পরিচিত যেখানে $J_x^{\ast }=\frac{\partial J^{\ast }}{\partial 𝐱}={[\frac{\partial J^{\ast }}{\partial x_1}\frac{\partial J^{\ast }}{\partial x_2}\dots \frac{\partial J^{\ast }}{\partial x_n}]}^{𝖳}$ এবং $J_t^{\ast }=\frac{\partial J^{\ast }}{\partial t}$. $t$, $𝐱$, এবং অজ্ঞাতনামা ফাংশন $J_x^{\ast }$এর সাপেক্ষে $𝐮$এর লঘুকরণ করে প্রাপ্ত ফলাফল হ্যামিল্টন – জ্যাকোবি – বেলম্যান সমীকরণে প্রতিস্থাপন করে আংশিক ব্যবকলনীয় সমীকরণটির সমাধান সীমানা শর্ত $J\left(t_1\right)=b(𝐱(t_1),t_1)$ হতে পাওয়া যেতে পারে। কার্যক্ষেত্রে, এর জন্য সাধারণত সংখ্যাগত কৌশলের প্রয়োজন পড়ে যাতে করে নিখুঁত অপ্টিমাইজেশন সম্পর্কের বিযুক্ত (ডিসক্রিট) আসন্নায়ন (অপ্টিমাইজেশন) সম্ভবপর হয়। বিকল্পভাবে, এই চলমান প্রক্রিয়াটিকে একটি বিযুক্ত ব্যবস্থার মাধ্যমে অনুমান করা সম্ভব, যা হ্যামিল্টন – জ্যাকোবি – বেলম্যান সমীকরণে প্রাপ্ত অবস্থার সাথে সামঞ্জস্যপূর্ণ একটি পুনরাবৃত্তিয় সম্পর্কের সৃষ্টি করে:

$J_k^{\ast }\left({𝐱}_{n-k}\right)=\underset{{𝐮}_{n-k}}{\min }\{\hat{f}({𝐱}_{n-k},{𝐮}_{n-k})+J_{k-1}^{\ast }\left(\hat{g}({𝐱}_{n-k},{𝐮}_{n-k})\right)\}$

যেখানে

$k$

-তম ধাপে

$n$

টি সমভাবে বিস্তৃত বিযুক্ত সময় অন্তরে,

$\hat{f}$

এবং

$\hat{g}$

যথাক্রমে

$f$

and

$𝐠$

এর বিযুক্ত অনুুমানকে নির্দেশ করে। এই ফাংশনাল সমীকরণকে বেলম্যান সমীকরণ বলা হয়ে থাকে, যেটি সমাধান করে অনুকূলকরণ (অপ্টিমাইজেশান) সমীকরণের বিযুক্ত অনুমানের নিখুঁত একটি সমাধান পাওয়া সম্ভব।

চিত্র ১. অপ্টিমাল সাবস্ট্রাকচার বৈশিষ্ট ব্যবহার করে গ্রাফের মধ্যে স্বল্পতম দুরত্ব বের করা;একেকটি সরলরেখা এখানে একটি করে এজ (edge) নির্দেশ করছে;দুটি বিন্দুর মাঝে স্বল্পতম দুরত্ব বক্ররেখার মাধ্যমে প্রদর্শিত হয়েছে (যে কোন দুই প্রান্তবিন্দুর মাঝে অন্য পথ থাকতে পারে যাদের দেখানো হয়নি); গাঢ় রেখার মাধ্যমে শুরু হতে শেষ পর্যন্ত ক্ষুদ্রতম দুরত্ব দেখানো হয়েছে।

অর্থনৈতিক উদাহরণ: রামজের সন্তোষজনক সঞ্চয়ের সমস্যা

টেমপ্লেট:আরও দেখুন অর্থনীতিতে, সাধারণভাবে লক্ষ্য হচ্ছে কোন ডাইনামিক সামাজিক কল্যান ফাংশনের সর্বাধিকরণ (লঘিষ্ঠকরণের পরিবর্তে)। রামজের সমস্যায়, এই ফাংশনটি ব্যয়ের সাথে উপযোগের একটি সম্পর্ক স্থাপন করে। ঢিলেঢালাভাবে বলতে গেলে, পরিকল্পনাকারীকে সমসাময়িক ব্যয় এবং ভবিষ্যত ব্যয়ের মাঝে একটি ভারসাম্য সৃষ্টি করতে হয় (বিনিয়োগের মূলধন যেটি উৎপাদনে ব্যবহৃত হয় তার মাধ্যমে) যেটি অন্তর্বর্তীকালীন বিকল্প নামে পরিচিত। ভবিষ্যত ব্যয় একটি নির্দিষ্ট $\beta \in (0,1)$হারে ছাড়প্রাপ্ত হয়। মূলধনের রুপান্তরের একটি বিযুক্ত অনুমান নিচের সমীকরণের সাহায্যে দেয়া যায়:

$k_{t+1}=\hat{g}(k_t,c_t)=f(k_t)-c_t$

যেখানে $c$ ব্যয়, $k$ পুঁজি, এবং $f$ একটি উৎপাদন ফাংশন যেটি ইনাদার শর্তসমূহকে পূরণ করে। একটি মূলধন $k_0>0$ ধরে নেয়া হয়।

কম্পিউটার প্রোগ্রামিং

টেমপ্লেট:Refimprove sectionএকটি সমস্যাকে ডায়নামিক প্রোগ্রামিং এর মাধ্যমে সমাধানের জন্য অবশ্যই দুটি মূল বৈশিষ্ট্য থাকতে হবে : অপটিমাল সাবস্ট্রাকচার এবং ওভারল্যাপিং সাব-প্রবলেম। যদি এমন হয় যে, ওভারল্যাপ করে না এমন সাব-প্রবলেমগুলোর সর্বোত্তম সমাধানগুলি একত্রিত করে কোনও সমস্যার সমাধান করা যায়, তবে কৌশলটিকে ডায়নামিক প্রোগ্রামিং এর পরিবর্তে "ডিভাইড অ্যান্ড কনকোয়ার" (বিভাজন এবং বিজয়ন) বলা হয়। একারণে মার্জ সর্ট এবং কুইক সর্ট কে ডাইনামিক প্রোগ্রামিং হিসাবে ধরা হয়না।