আগের পর্বে আমরা ফিবোনাচ্চি নাম্বার নিয়ে আলোচনা করেছি। আমরা দেখেছি কিভাবে ডাইনামিক প্রোগ্রামিং ব্যবহার করে রিকার্সিভলি এবং ইটারেটিভলি ফিবোনাচ্চি সংখ্যা জেনারেট করা যায়। এই পর্বে আমরা কথা বলবো শর্টেস্ট পাথ প্রবলেম নিয়ে এবং সেটা নিয়ে আলোচনা করার সময় ডিপির কিছু নতুন প্রোপার্টি নিয়ে জানবো।
যদিও শর্টেস্ট পাথ গ্রাফ থিওরির একটা প্রবলেম, এই লেখা বুঝতে গ্রাফ নিয়ে না জানলেও চলবে।
মনে করো আমাদেরকে এক শহর থেকে অন্য শহরে যাবার শর্টেস্ট পাথ খুজে বের করতে হবে। শহর আছে মোট টি। হলো প্রথম শহর, এবং হলো শেষ শহর। কোন শহর থেকে কোন শহরে সরাসরি যাওয়া যায় এবং শহরগুলোর মধ্যে দুরত্ব কত সেটা অ্যারো দিয়ে দেখিয়ে দেয়া আছে। এখন আমাদের প্রবলেমটা হলো থেকে এ যাবার শর্টেস্ট পাথের দৈর্ঘ্য কত?
প্রবলেমের প্যারামিটার বা স্টেট নির্ধারণ
প্রথমেই আমাদের বের করতে হবে প্রবলেমটাকে কি কি প্যারামিটার বা স্টেট দিয়ে প্রকাশ করা যায়। ক্রমান্বয়ে আমাদের স্টেট হবে এক্ষেত্রে তুমি বর্তমানে কোন শহরে আছো সেটা। ধরে নিলাম তুমি বর্তমানে তম শহরে আছো এবং আমাদের প্রবলেমটাকে আমরা ফাংশন দিয়ে প্রকাশ করবো।
স্টেট ট্রানজিশন এবং রিকার্শন
আমরা জানিনা শহর থেকে কোন শহরে গেল দ্রুততম উপায়ে গন্তব্য পৌছাতে পারবো। এই ধাপে এসে আমরা সেটা অনুমান করবো।
আইডিয়াটা হলো প্রতিটা শহর থেকে আমরা অন্য সব শহরে যাবো এবং সেখান থেকে শর্টেস্ট পাথ খুজে বের করার চেষ্টা করবো। সবগুলো অনুমানের মধ্যে যেটা সবথেকে ছোট সেটাই হবে উত্তর। জেনারেলাইজড করে লিখলে: যেখানে থকে তে এজ আছে।
সাবপ্রবলেম/স্টেট অর্ডারিং এবং DAG
এখন একটু চিন্তা করো এই রিকার্শন চালিয়ে দিলে কিভাবে ফাংশন কল হবে। যদি একে অপরের উপর নির্ভরশীল (সাইকেল বা লুপ) থাকে, তাহলে এই সলিউশন ইমপ্লিমেন্ট করলে আমাদের কোড ইনফাইনাইট লুপে আটকে যাবে।
এত কষ্ট করে একটা ভুল সমাধান বের করার উদ্দেশ্য আসলে তোমাদের DAG বা ডিরেক্টেড অ্যাসাইক্লিক গ্রাফ (Directed Acyclic Graph) কনসেপ্টটার সাথে পরিচয় করিয়ে দেয়া। DAG মানে হলো একটা ডিরেক্টেড গ্রাফ যেখানে কোনো সাইকেল নেই। ডাইনামিক প্রোগ্রামিং সলিউশন কাজ করবে শুধুমাত্র তখনই যখন সাবপ্রবলেমগুলো একটা DAG তৈরি করবে। সাইকেল থাকলেই সাবপ্রবলেমগুলা ইনফিনিট লুপে আটকে যাবে।
অ্যাসাইক্লিক গ্রাফের জন্য শর্টেস্ট পাথ প্রবলেম আমাদের ডিপি ফর্মূলা দিয়েই সমাধান করা যাবে।
ইন্টারেস্টিং ব্যপার: সাইক্লিক গ্রাফেও ডিপি দিয়ে শর্টেস্ট পাথ বের করা যায় তবে সেক্ষেত্রে একটা অতিরিক্ত প্যারামিটার যোগ করতে হয় যেটা দিয়ে বুঝায় ‘সর্বোচ্চ টা এজ ব্যবহার করে শর্টেস্ট পাথ কত?’। তখন সেটাই হয়ে যাবে বেলম্যানফোর্ড অ্যালগরিদম!
কমপ্লেক্সিটি
কোডে আমরা দুটো প্যারামিটার পাস করলেও প্রবলেমের স্টেট আসলে শুধু প্রথম প্যারামিটারটাই। এর ভ্যালু হতে পারে থেকে পর্যন্ত। প্রতিটা সাবপ্রবলেমের জন্য আবার সেই শহরের সাথে কোন শহরের কানেকশন আছে সেটা আমাদের চেক করতে হচ্ছে একটা লুপ চালিয়ে, কানেকশন থাকতে পারে সর্বোচ্চ টা। মোট কমপ্লেক্সিটি পেতে আমারা স্টেট সংখ্যা এবং ভিতরের কমপ্লেক্সিটি গুণ করে দিয়ে যাবো ।