ডাইনামিক প্রোগ্রামিং - পর্বঃ১
আমরা এই পর্বে, ডায়নামিক প্রোগ্রামিং এর শুধু থিওরেটিকেল বিষয়ের খুব প্রাথমিক ব্যাপারটা সম্পর্কে জানব। পরের পর্বে উদাহরণ সহ কোড দেয়া হবে। তাহলে সব পানির মতো সোজা হয়ে যাবে।
১.১) ডাইনামিক প্রোগ্রামিং কী এবং কেন?
ডিভাইড এন্ড কনকোয়ার মেথড এ আমরা প্রবলেম গুলোকে কতগুলো সাব-প্রবলেম এ ভাগ করি, তারপর সেগুলো রিকার্শন বা ইটারেশনের মাধ্যমে সলভ করে মার্জ(একত্রিত) করি। ডাইনামিক প্রোগ্রামিং আলাদা কোন প্রোগ্রামিং স্টাইল নয়, এটি নির্দিষ্ট কোন অ্যালগোরিদম ও নয়। তাহলে কি? এটি এক ধরনের অ্যালগোরিদমিক ডিজাইন টেকনিক। এই টেকনিকের মাধ্যমে অনেক প্রবলেম সল্ভ করা যায়। এর মধ্যে কিছু ক্লাসিক প্রবলেম এবং অ্যালগোরিদম এর লিস্ট দেয়া হলঃ
০-১ ন্যাপস্যাক প্রবলেম, কয়েন চেঞ্জিং প্রবলেম, রড কাটিং, ম্যাট্রিক্স চেইন মাল্টিপ্লিকেশন, লংগেস্ট কমন সাবসিকুয়েন্স, অপটিমাল বাইনারি সার্চ ট্রি, রেকট্যাঙ্গুলার ব্লকস, ইত্যাদি।
কোন কোন কেস এ/প্রবলেম এ ডিভাইড এন্ড কনকোয়ার অথবা ব্রূটফোর্স মেথড ব্যবহার করলে, প্রোগ্রামের টাইম কমপ্লেক্সিটি অনেক বেশি হয়ে যায়, অনেক সময় এক্সপোনেনশিয়াল (O(2n)) হয়ে যায়। সেক্ষেত্রে, n এর মান অনেক বড় হলে, প্রোগ্রামটি রান হতে হতে, মাথার চুল পেকে যেতে পারে। কিন্তু ডাইনামিক প্রোগ্রামিং ব্যবহার করে, সেই একই কেস/প্রবলেম গুলো সমাধান করা সম্ভব, টাইম কমপ্লেক্সিটি পলিনমিয়ালে কমিয়ে এনে। কিন্তু একটা ব্যাপার আছে এতে, আমরা টাইম কমপ্লেক্সিটি এত পরিমাণে কমিয়ে আনব, কিন্তু বিনিময়ে কিছু দিব না, তা কি করে হয়? হ্যা দিব। টাইম এর বিনিময়ে স্পেস/মেমরি দিব। কিন্তু মেমরি কেন? কারণ, আমরা সমাধান করার সময় Extra Space/Memory ব্যবহার করব। আমরা তৈরি করব একটা Lookup Table, যার মধ্যে প্রতিটি সম্ভাব্য ভ্যালু থাকবে সমাধানের। কিন্তু আমরা অপটিমাল সমাধানটি বেছে নিব। এভাবে টেবিল থেকে ভ্যালু চেক করব। তাই, সাধারণ ডিভাইড এন্ড কনকোয়ার এর মতো একই কাজ অনেকবার করবে না। অর্থাৎ; ওভার ল্যাপিং সাব-প্রবলেম থাকবে না। ওভার ল্যাপিং সাবপ্রবলেম কি… তা নিয়ে সামনের পর্বে বিস্তারিত আলোচনা করব। এভাবেই চলে এল ডাইনামিক প্রোগ্রামিং এর কনসেপ্ট। কিন্তু এখন আমাদের মনে প্রশ্ন জাগতে পারে, কোন কোন কেস এ এক্সপোনেনশিয়াল টাইম কমপ্লেক্সিটি পাওয়া যায়? কিভাবে বুঝব, যে প্রবলেমটি ডাইনামিক প্রোগ্রামিং দিয়ে সল্ভ করা যাবে? গেলেও শর্তগুলো কি কি? উদাহরণ দেখালে ভাল হত। হ্যা, সব কিছুই পরিষ্কার হয়ে যাবে। জানব সব। কিন্তু এই প্রশ্নের উত্তর গুলো সামনের পর্বে দিব। কথা দিলাম।
এই পর্বে শুধু প্রয়োজন ছিল একটু চোখ বুলানো। শুধু একটু দেখে রাখা।
আমি রাফিদ মুহাম্মদ। বিশ্বের সর্ববৃহৎ বিজ্ঞান ও প্রযুক্তির সৌশল নেটওয়ার্ক - টেকটিউনস এ আমি 7 বছর 2 মাস যাবৎ যুক্ত আছি। টেকটিউনস আমি এ পর্যন্ত 2 টি টিউন ও 0 টি টিউমেন্ট করেছি। টেকটিউনসে আমার 2 ফলোয়ার আছে এবং আমি টেকটিউনসে 0 টিউনারকে ফলো করি।
