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

    এই সিরিজে আমরা ডাইনামিক প্রোগ্রামিং দ্বারা সমাধান করা যায় এমন কিছু চমৎকার সমস্যার সমাধান দেখবো। সমস্যা গুলো সমাধান করার জন্য বেসিক ডিপি এবং রিকারসন / ব্যাকট্রাকিং কনসেপ্ট থাকতে হবে। 

    প্রথমেই আসা যাক রিকারশন নিয়ে। রিকারশন হচ্ছে একটি ফাংশনকে যখন আমরা ঔ ফাংশন দ্বারাই কল করি তখন তাকে রিকারশন বলে থাকি। একটি উদাহরণ দেয়া যাক, ধরা যাক একটি রোবটের জন্য একটি নির্ধারিত কাজ প্রোগ্রাম করে দেয়া হল। তাকে বলা হল প্রতিদিন তাকে দুটি ঠিকানা দেয়া হবে, সেখান থেকে তাকে তাকে একটি ঠিকানা নিজে হতে বাছাই করতে হবে এবং সেখানে যেতে হবে। এখানে রোবটের কাজটাই হল একটা ফাংশন। এবং প্রতিদিন তার বাছাই করা নতুন ঠিকানা হল ফাংশনের প্যারামিটার। এক ঠিকানায় যাবার পর তাকে সেখান থেকে আবার নতুন দুটি ঠিকানা দেয়া হয় এবং সে আবার তার ফাংশন মত কাজ করে। প্রতিদিন নতুন নতুন ঠিকানায় যাবার পর পুনরায় একি প্রক্রিয়া চলতেই থাকে।  এটাই হচ্ছে রিকারশন। প্রশ্ন হচ্ছে এর শেষপ্রান্ত কোথায়? উদ্দেশ্যহীন ভাবে নিশ্চয় আজীবন এই রিকারশন চলতে পারে না। এই উদ্দেশ্যকেই আমরা বলি বেইস কেস বা টারমিনেশন পয়েন্ট। ধরা যাক, রোবটটির চার্জ শেষ হয়ে গেলে সে আর নতুন কোন ঠিকানায় যেতে পারবে  না। এটাই তার বেইস কেস। প্রতিটি নতুন ঠিকানায়  যাবার জন্য তার কিছু চার্জ খরচ হয়। যখনই এই চার্জ শেষ হয়ে যাবে সে আর নতুন প্যারামিটার নিয়ে তার নির্ধারিত ফাংশন  চালাতে পারবে না।

    এবার প্রশ্নে আশা যাক আমরা রোবটটির মাধ্যমে আসলে কি করাতে চাচ্ছিলাম? আমরা জানতে চাই রোবটটি তার নির্ধারিত ফাংশন এর মাধ্যমে সবচেয়ে বেশি কতগুলো ঠিকানায় ঘুরতে পারবে। এবার ধরা যাক, রোবটটি যখন ই তার বেইস কেস এ পৌছায় সে তখন সে তার আগের দিন যেখানে ছিল (মনে করি X) সেখানে ফিরে যায়। এক্ষেত্রে তার চার্জও ফিরে আসে (নতুন ঠিকানায় যাবার জন্য যতটুকু খরচ হয়েছিল)। মনে আছে তাকে প্রত্যেকবার দুটো ঠিকানা দেয়া হচ্ছিল? এবার সে এই আগের বার বাছাই না করা ঠিকানায় যায়। সেখান থেকেও চার্জ শেষ না হওয়া পর্যন্ত ফাংশন মত চলতে থাকে। চার্জ শেষ হলে একই ভাবে আগের শহরে ফিরে এসে চার্জ পুনঃরুদ্ধার করে এবং আগের বার বাছাই না করা পথে ফাংশন মত কাজ করে। এই বার বার পেছনে ফিরে আসাই হল ব্যাকট্রাকিং। এবার প্রশ্ন হল রোবটটির তো X ঠিকানা থেকে সম্ভাব্য দুটি পথেই ফাংশন চালানো শেষ এখন সে কি করবে? উত্তর হল যেহেতু কিছুই করার নেই, সে X এর ঠিক আগের ঠিকানায় ব্যাকট্রাক করবে। তবে ব্যাকট্রাক করার সময় X থেকে সম্ভাব্য দুটি ঠিকানার যেটিতে গিয়ে সে সবচেয়ে বেশি নতুন ঠিকানায় যেতে পেরেছে, সেটির তথ্য রেকর্ড করে রাখবে । সেখান থেকেও একি প্রক্রিয়ায় বাছাই না করা পথে ফাংশন চালিয়ে দেখতে চাইবে কতটি নতুন ঠিকানায় যাওয়া যায় এবং আগের তথ্য আর নতুন তথ্যের তুলনা করে যেটা থেকে বেশি ঠিকানায় যাওয়া যায় সেটা রেকর্ড করে তারও পুর্বের ঠিকানায় ব্যাকট্রাক করবে। একি প্রক্রিয়া চলতে থাকবে যতক্ষন না পর্যন্ত সে তার শুরুর ঠিকানায় পৌছে যায়। এবং রেকর্ড তথ্য থেকে  আমাদের ফলাফল জানাতে পারে।

    এবার রোবটের ভ্রমন কাহিনি থেকে কিছু অবজারভেশন এ আসা যাক-

১. আমরা ঘুরে ফিরে আমাদের সম্ভাব্য সকল ঠিকানায় সম্ভাব্য সকল ভাবেই যাওয়ার চেস্টা করেছি। তার X ঠিকানায় যদি A থেকে যাওয়া যায় সেটাও চেস্টা করেছি আবার B থেকে যাওয়া গেলে সেটাও চেস্টা করে দেখেছি।

২. বেইস কেস বুঝতে যদি ভুল করি তাহলে আজিবন ফাংশনের ভেতর ফাংশন ইনফিনিটলি কল হতেই থাকবে এবং আমাদের রিকারশন কখনোই শেষ হবে না।

৩. কোন একটা ঠিকানা/স্টেট থেকে ফাংশন কলিং এর সময় আমাদের প্রত্যেকবার করা প্যারামিটার চয়েস এর উপর ই আসলে আমরা কি তথ্য পাব সেটা নির্ভর করছে। ব্যাকট্রাক করার সময় আমরা আগের স্টেটে তথ্য নিয়ে ফিরছি। সম্পুর্ন প্রক্রিয়ায় এটাই সবচেয়ে গুরত্বপুর্ন,  যেহেতু এর উপর আমাদের ফলাফল নির্ভর করছে।

৪. আমাদের কাছে মুল হচ্ছে তথ্য, কোন একটা ঠিকানা থেকে যদি আমরা ইতিমধ্যে জানি যে, এখান থেকে সবচেয়ে বেশি কতটি শহরে আমাদের রোবট যেতে পারবে তাহলে কিন্তু আর সেখানে ফাংশন চালিয়ে যাওয়ার মানে হয় না। তথ্য তো আমরা জানি ই!

    এই অবজারভেশন গুলোই আসলে ডিপির প্রকৃত ফাউন্ডেশন। অনলাইন এ অনেক রিসোর্স পাওয়া যাবে ডিপি শেখার জন্য, নানা রকম ডিপি টেকনিক আয়ত্ত করার জন্য। আমার কাছে বেসিক ডিপি নিয়ে সবচেয়ে ভালো মনে হওয়া রিসোর্স গুলো হচ্ছে -   

Topcoder Dynamic Programming Tutorial : এখানে মুলত state কি, কিভাবে বের করতে হয়, Bidirectional Approach করতে হয়, Matrix এ কিভাবে ডিপি কাজ করে সেসব নিয়ে আলোচনা করা হয়েছে।
Codechef Dynamic programming Tutorial : এখানে Bottom Up Approach, Top Down Approach, Memoization নিয়ে স্বল্প আলোচনার পাশাপাশি অনেক গুলো রিসোর্স শেয়ার করা আছে
FreeCodeCamp - Demystifying Dynamic Programming : সাবপ্রবলেম এর কন্সেপ্ট নিয়ে আলোচনা করা হয়েছে এখানে।

Next Page