Dynamic programming — গতিশীল প্রোগ্রামিং

গতিশীল প্রোগ্রামিং (ডিপি; ইং. dynamic programming, DP) — এটি জটিল অপ্টিমাইজেশন সমস্যা সমাধানের একটি পদ্ধতি, যা মূল সমস্যাটিকে একটি ক্রমানুসারে সহজতর উপসমস্যায় বিভক্ত করার উপর ভিত্তি করে গড়ে উঠেছে। পদ্ধতিটি বহু-ধাপবিশিষ্ট সিদ্ধান্ত গ্রহণের প্রক্রিয়ায় প্রয়োগ করা হয়, যেখানে সম্পূর্ণ সমস্যার সর্বোত্তম সমাধান তার উপসমস্যাগুলির সর্বোত্তম সমাধান থেকে নির্মাণ করা সম্ভব।

পরিভাষাটি আমেরিকান গণিতবিদ রিচার্ড বেলম্যান ১৯৫০-এর দশকে প্রবর্তন করেছিলেন। এই প্রসঙ্গে «প্রোগ্রামিং» শব্দটি «পরিকল্পনা» বা «সর্বোত্তম কর্মপরিকল্পনা প্রণয়ন» অর্থে ব্যবহৃত হয়, কম্পিউটার কোড লেখার অর্থে নয়।

মূল বৈশিষ্ট্য ও উপপাদ্যসমূহ

কোনো সমস্যায় গতিশীল প্রোগ্রামিংয়ের প্রযোজ্যতা নির্ধারিত হয় তার দুটি মৌলিক বৈশিষ্ট্যের উপস্থিতি দ্বারা।

বেলম্যানের অপ্টিমালিটির নীতি

পদ্ধতির কেন্দ্রীয় ধারণাটি হল বেলম্যানের অপ্টিমালিটির নীতি (ইং. Bellman's principle of optimality)। এটি বলে: প্রাথমিক অবস্থা এবং প্রাথমিক সিদ্ধান্ত যা-ই হোক না কেন, পরবর্তী সিদ্ধান্তগুলি অবশ্যই প্রথম সিদ্ধান্তের ফলে প্রাপ্ত অবস্থার সাপেক্ষে একটি সর্বোত্তম কৌশল গঠন করতে হবে।

অন্যভাবে বলতে গেলে, সর্বোত্তম পথের যেকোনো অংশ নিজেই সর্বোত্তম। এই বৈশিষ্ট্যটি সামগ্রিক সমস্যাটিকে একটি ক্রমানুসারে সহজতর উপসমস্যায় বিভক্ত করতে এবং সেগুলিকে পুনরাবৃত্তিমূলকভাবে সমাধান করতে সহায়তা করে।

অধিব্যাপী উপসমস্যা

কোনো সমস্যায় অধিব্যাপী উপসমস্যার (ইং. overlapping subproblems) বৈশিষ্ট্য থাকে, যদি তার পুনরাবৃত্তিমূলক সমাধানের সময় একই উপসমস্যাগুলি বারবার আবির্ভূত হয়। ডিপি ইতোমধ্যে সম্মুখীন উপসমস্যাগুলির সমাধান সংরক্ষণ করে (এই কৌশলটিকে মেমোইজেশন বা ট্যাবুলেশন বলা হয়) পুনরাবৃত্তিমূলক গণনা এড়িয়ে চলতে পারে, যা সরল পুনরাবৃত্তিমূলক অনুসন্ধানের তুলনায় কার্যকারিতা উল্লেখযোগ্যভাবে বৃদ্ধি করে।

বেলম্যান সমীকরণ

অপ্টিমালিটির নীতি থেকে পদ্ধতির মূল পুনরাবৃত্তিমূলক সম্পর্কটি উদ্ভূত হয় — বেলম্যান সমীকরণ। এটি বর্তমান অবস্থার «মূল্য» (সর্বোত্তম লাভ বা ব্যয়) পরবর্তী অবস্থাগুলির মূল্যের সাথে সংযুক্ত করে। যোজক লক্ষ্যমান ফাংশন সহ নির্ধারণবাদী বহু-ধাপ প্রক্রিয়ার জন্য এর সাধারণ রূপটি হল:

$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$ অবস্থায় শুরু হওয়া উপসমস্যার জন্য লক্ষ্যমান ফাংশনের সর্বোত্তম মান।

সমীকরণটি ক্রমানুসারে সমাধান করা হয়, সাধারণত «শেষ থেকে», শেষ ধাপ থেকে প্রথম ধাপের দিকে এগিয়ে।

প্রয়োগের উদাহরণ

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

সীমাবদ্ধতা

পদ্ধতির প্রধান সীমাবদ্ধতা হল মাত্রার অভিশাপ (ইং. curse of dimensionality) — বেলম্যান কর্তৃক প্রবর্তিত একটি পরিভাষা, যা সিস্টেমের অবস্থা বর্ণনাকারী চলকের সংখ্যা বৃদ্ধির সাথে সাথে অবস্থার সংখ্যা এবং ফলস্বরূপ গণনামূলক জটিলতার ঘাতীয় বৃদ্ধি বোঝাতে ব্যবহৃত হয়। এটি অত্যন্ত উচ্চ মাত্রার সমস্যাগুলির জন্য সুনির্দিষ্ট ডিপির ব্যবহারিক প্রয়োগকে সীমিত করে।

সংশ্লিষ্ট ধারণাসমূহ

• অপারেশনস রিসার্চ
• সর্বোত্তম নিয়ন্ত্রণের তত্ত্ব
• মার্কভ সিদ্ধান্ত প্রক্রিয়া (স্টোকাস্টিক সাধারণীকরণ)
• হ্যামিলটন — জ্যাকোবি — বেলম্যান সমীকরণ (অবিচ্ছিন্ন সময়ের জন্য অ্যানালগ)

টীকাসমূহ

</references>