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

ডাইনামিক প্রোগ্রামিং হল কম্পিউটারে প্রোগ্রাম লিখার এবং গাণিতিক নিখুঁতীকরণের একটি পদ্ধতি। রিচার্ড বেলম্যান ১৯৬০ এর দশকে এই পদ্ধতিটি উদ্ভাবন করেন এবং বর্তমানে অনেকসংখ্যক কর্মক্ষেত্র, অ্যারোস্পেস প্রকৌশল হতে অর্থনীতিতে এটি ব্যবহৃত হচ্ছে। উভয় প্রসঙ্গে একটি জটিল সমস্যাকে সহজতর এবং ক্ষুদ্রতর সমস্যায় ভাগ করে পুনরাবৃত্তিয় (রিকার্সিভ) ভাবে সমাধান করাকে এটি নির্দেশ করে। যদিও কিছু বাছাইকরণ (ডিসিশন) সমস্যা এ পদ্ধতিতে বিভাজন সম্ভব নয়, যে বাছাইগুলো সময়ের একাধিক বিন্দুতে অবস্থান করে সেগুলিকে পুনরাবৃত্তভাবে ভাগ করা সম্ভব। অনুরূপভাবে কম্পিউটার বিজ্ঞানে, যদি একটি বড় সমস্যাকে ছোট ছোট সমস্যায় বিভক্ত করে সবগুলোকে পুনরাবৃত্তভাবে সমাধানের মাধ্যমে পুরো সমস্যাটির সন্তোষজনকভাবে সমাধান করা সম্ভব, তাহলে এটির বৈশিষ্ট রয়েছে বলে ধরে নেয়া যায়।
যদি উপ-সমস্যাগুলিকে পুনরাবৃত্তিয়ভাবে বৃহৎ সমস্যার মধ্যে আবদ্ধ করা যায় যাতে করে ডাইনামিক প্রোগ্রামিং এর পদ্ধতিগুলি এর ওপর প্রয়োগযোগ্য হয়, তাহলে বৃহত্তর সমস্যার মান ও ক্ষুদ্রতর সমস্যাগুলির মানের মাঝে একটি সম্পর্ক রয়েছে বলে ধরে নেয়া যেতে পারে। গাণিতিক অপ্টিমাইযেশন বিদ্যায় এই সম্পর্ককে বলা হয় ।
গাণিতিক অপ্টিমাইজেশানের পরিভাষায়, ডাইনামিক প্রোগ্রামিং এর সাহায্যে সাধারণত বোঝানো হয়, কোন একটি বৃহৎ বিষয়ে সিদ্ধান্ত গ্রহণকে সময়ের সাথে সাথে ভেঙে একাধিক ছোট ছোট সিদ্ধান্ত গ্রহণের পদক্ষেপে বিভক্ত করার প্রক্রিয়া। মনে করি, মূল্যমান ফাংশনের একটি অনুক্রম "V", "V", ..., "V" এবং সময় i=1 হতে n পর্যন্ত নির্দেশকারী "y" কে উক্ত অনুক্রম আর্গুমেন্ট হিসেবে গ্রহণ করে। "n" সময়ে "y" অবস্থার প্রাপ্ত মানের দ্বারা "V"("y") কে সংজ্ঞায়িত করা হয়।
নিয়ন্ত্রণ তত্ত্বে একটি চিরাচরিত সমস্যা হচ্ছে, কোন একটি সিস্টেম formula_1কে অবিচ্ছিন্ন সময় অন্তর formula_2এর মাঝে গ্রহণযোগ্য আবক্র পথ formula_3অনুসরণ করে এবং একটি মিনিমাইজে বাধ্য করতে গেলে যে গ্রহণযোগ্য নিয়ন্ত্রণ formula_4দরকার সেটি বের করা।
এই সমস্যার সমাধান হল, একটি সন্তোষজনক নিয়ন্ত্রণ বিধি অথবা বিধান formula_6এর ব্যবস্থা করা, যা একটি সন্তোষজনক আবক্রপথ formula_3এবং উন্নততর ক্ষতি-ফাংশন formula_8এর সৃষ্টি করে। শেষোক্ত ফাংশন ডাইনামিক প্রোগ্রামিং এর মৌলিক সমীকরণ মেনে চলে:
একটি আংশিক ব্যবকলনীয় সমীকরণ যেটি হিসেবে পরিচিত যেখানে formula_10 এবং formula_11. formula_12, formula_13, এবং অজ্ঞাতনামা ফাংশন formula_14এর সাপেক্ষে formula_15এর লঘুকরণ করে প্রাপ্ত ফলাফল হ্যামিল্টন – জ্যাকোবি – বেলম্যান সমীকরণে প্রতিস্থাপন করে আংশিক ব্যবকলনীয় সমীকরণটির সমাধান সীমানা শর্ত formula_16 হতে পাওয়া যেতে পারে। কার্যক্ষেত্রে, এর জন্য সাধারণত প্রয়োজন পড়ে যাতে করে নিখুঁত অপ্টিমাইজেশন সম্পর্কের বিযুক্ত (ডিসক্রিট) আসন্নায়ন (অপ্টিমাইজেশন) সম্ভবপর হয়। বিকল্পভাবে, এই চলমান প্রক্রিয়াটিকে একটি বিযুক্ত ব্যবস্থার মাধ্যমে অনুমান করা সম্ভব, যা হ্যামিল্টন – জ্যাকোবি – বেলম্যান সমীকরণে প্রাপ্ত অবস্থার সাথে সামঞ্জস্যপূর্ণ একটি পুনরাবৃত্তিয় সম্পর্কের সৃষ্টি করে:
যেখানে formula_18-তম ধাপে formula_19টি সমভাবে বিস্তৃত বিযুক্ত সময় অন্তরে, formula_20এবং formula_21যথাক্রমে formula_22 and formula_23এর বিযুক্ত অনুুমানকে নির্দেশ করে। এই ফাংশনাল সমীকরণকে বেলম্যান সমীকরণ বলা হয়ে থাকে, যেটি সমাধান করে অনুকূলকরণ (অপ্টিমাইজেশান) সমীকরণের বিযুক্ত অনুমানের নিখুঁত একটি সমাধান পাওয়া সম্ভব।
অর্থনীতিতে, সাধারণভাবে লক্ষ্য হচ্ছে কোন ডাইনামিক সামাজিক কল্যান ফাংশনের সর্বাধিকরণ (লঘিষ্ঠকরণের পরিবর্তে)। রামজের সমস্যায়, এই ফাংশনটি ব্যয়ের সাথে উপযোগের একটি সম্পর্ক স্থাপন করে। ঢিলেঢালাভাবে বলতে গেলে, পরিকল্পনাকারীকে সমসাময়িক ব্যয় এবং ভবিষ্যত ব্যয়ের মাঝে একটি ভারসাম্য সৃষ্টি করতে হয় (বিনিয়োগের মূলধন যেটি উৎপাদনে ব্যবহৃত হয় তার মাধ্যমে) যেটি নামে পরিচিত। ভবিষ্যত ব্যয় একটি নির্দিষ্ট formula_24হারে ছাড়প্রাপ্ত হয়। মূলধনের রুপান্তরের একটি বিযুক্ত অনুমান নিচের সমীকরণের সাহায্যে দেয়া যায়:
যেখানে formula_26 ব্যয়, formula_18 পুঁজি, এবং formula_22 একটি যেটি পূরণ করে। একটি মূলধন formula_29 ধরে নেয়া হয়।
একটি সমস্যাকে ডায়নামিক প্রোগ্রামিং এর মাধ্যমে সমাধানের জন্য অবশ্যই দুটি মূল বৈশিষ্ট্য থাকতে হবে : এবং । যদি এমন হয় যে, ওভারল্যাপ করে না এমন সাব-প্রবলেমগুলোর সর্বোত্তম সমাধানগুলি একত্রিত করে কোনও সমস্যার সমাধান করা যায়, তবে কৌশলটিকে ডায়নামিক প্রোগ্রামিং এর পরিবর্তে "" (বিভাজন এবং বিজয়ন) বলা হয়। একারণে এবং কুইক সর্ট কে ডাইনামিক প্রোগ্রামিং হিসাবে ধরা হয়না।