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

উইকিপিডিয়া, মুক্ত বিশ্বকোষ থেকে
পরিভ্রমণে ঝাঁপ দিন অনুসন্ধানে ঝাঁপ দিন

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

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

সারাংশ[সম্পাদনা]

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

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

নিয়ন্ত্রণ তত্ত্ব[সম্পাদনা]

নিয়ন্ত্রণ তত্ত্বে একটি চিরাচরিত সমস্যা হচ্ছে, কোন একটি সিস্টেম কে অবিচ্ছিন্ন সময় অন্তর এর মাঝে গ্রহণযোগ্য আবক্র পথ অনুসরণ করে এবং একটি কস্ট ফাংশন মিনিমাইজে বাধ্য করতে গেলে যে গ্রহণযোগ্য নিয়ন্ত্রণ দরকার সেটি বের করা।

এই সমস্যার সমাধান হল, একটি সন্তোষজনক নিয়ন্ত্রণ বিধি অথবা বিধান এর ব্যবস্থা করা, যা একটি সন্তোষজনক আবক্রপথ এবং উন্নততর ক্ষতি-ফাংশন এর সৃষ্টি করে। শেষোক্ত ফাংশন ডাইনামিক প্রোগ্রামিং এর মৌলিক সমীকরণ মেনে চলে:

একটি আংশিক ব্যবকলনীয় সমীকরণ যেটি হ্যামিল্টন – জ্যাকোবি – বেলম্যান সমীকরণ হিসেবে পরিচিত যেখানে এবং . , , এবং অজ্ঞাতনামা ফাংশন এর সাপেক্ষে এর লঘুকরণ করে প্রাপ্ত ফলাফল হ্যামিল্টন – জ্যাকোবি – বেলম্যান সমীকরণে প্রতিস্থাপন করে আংশিক ব্যবকলনীয় সমীকরণটির সমাধান সীমানা শর্ত হতে পাওয়া যেতে পারে।[২] কার্যক্ষেত্রে, এর জন্য সাধারণত সংখ্যাগত কৌশলের প্রয়োজন পড়ে যাতে করে নিখুঁত অপ্টিমাইজেশন সম্পর্কের বিযুক্ত (ডিসক্রিট) আসন্নায়ন (অপ্টিমাইজেশন) সম্ভবপর হয়। বিকল্পভাবে, এই চলমান প্রক্রিয়াটিকে একটি বিযুক্ত ব্যবস্থার মাধ্যমে অনুমান করা সম্ভব, যা হ্যামিল্টন – জ্যাকোবি – বেলম্যান সমীকরণে প্রাপ্ত অবস্থার সাথে সামঞ্জস্যপূর্ণ একটি পুনরাবৃত্তিয় সম্পর্কের সৃষ্টি করে:

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

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

তথ্যসূত্র[সম্পাদনা]

  1. Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C. (2001), Introduction to Algorithms (2nd ed.), MIT Press & McGraw–Hill, আইএসবিএন ০-২৬২-০৩২৯৩-৭ . pp. 344.
  2. Kamien, M. I.; Schwartz, N. L. (১৯৯১)। Dynamic Optimization: The Calculus of Variations and Optimal Control in Economics and Management (Second সংস্করণ)। New York: Elsevier। পৃষ্ঠা 261। আইএসবিএন 978-0-444-01609-6 
  3. Kirk, Donald E. (১৯৭০)। Optimal Control Theory: An Introduction। Englewood Cliffs, NJ: Prentice-Hall। পৃষ্ঠা 94–95। আইএসবিএন 978-0-13-638098-6