গ্রাফ থিওরি !
ময়মনসিংহ টাঙ্গাইল গাজীপুর ঢাকা
স্কুল কলেগজে আমার দেখা সবচেয়ে বিরক্তিকর জিনিস হইলো গ্রাফ :P
না, এই গ্রাফ ঠিক সেই গ্রাফ না ! তআহলে এটা কি? কেন দরকার?
আচ্ছা ধরুন আপনি প্রথম রাস্তায় বাস ছেড়েছেন, ধরুন আপনি ময়মনসিংহ থেকে বাগেরহাট এ বাসটি চালাবেন,
এর মাঝে প্রায় ২০-৩০ টি জেলা আছে, আমরা ধরে নিলাম এর মাঝে ২০টি জেলা আছে, এখন সব জেলা থেকে সব জেলার রাস্তা ও নেই। এখন আপনি চাইবেন যে সব জেলায় যাওয়া যাবে তার মধ্যে যেখানে যাত্রী বেশি পাওয়া যাবে সেই জেলাগুলোতে যাবেন, পাশাপাশি এটাও মাথায় রাখবেন যেন বেশি ঘুরে না যেতে হয় ।
এখন আপনি এই ২০টি জেলার সবগুলো দিয়ে কি করে যাওয়া যায় তা চেক করে দেখবেন, এদের মধ্যে আবে খেয়াল রাখবেন কোথায় কোথায় যাওয়ার রাস্তা নেই , এবং যাত্রী কোথায় বেশি পাওয়া যাবে, এবং সব শেষে অবশ্যই যেন যতটা সম্ভব কম ঘুরে যেন যেতে হয়, যাতে আপনার তেল খরচ বেশি না হয় !
চিন্তায় পরে গেলেন?
আচ্ছা, আপনাকে সাহায্য করতে আছে অসাধারণ ১টি অ্যালগরিদম ! আপনি শুধু গ্রাফ থিওরি ভালভাবে জানবেন, এর পর শুধু ১টা কোড করতে হবে, ব্যাস !
আজ আমরা কথা বলবো সেই গ্রাফ থিওরি নিয়ে ।
ছোট বেলায় অনেকেই আলিফ লায়লা দেখেছেন, ধরূন গুপ্তধন লুকিয়ে আছে কোন গোলক ধাঁধার মাঝে, আপনি আর জলদস্যু তার পিছনে চলেছেন, কে আগে পৌঁছাবে? অবশ্যই আপনি, কারণ আপনি জানেন গ্রাফ থিওরি !
আসুন দেখি উপরের ২টি সমস্যা কি করে গ্রাফ থিওরি দিয়ে সমাধান করা যায় !
প্রথমেই লক্ষ্য করি গ্রাফ কি ? কি কি দিয়ে ১টি গ্রাফ গঠিত হয় ?
বাসের রুট দিয়েই ব্যাখ্যা করি, এখন ১টি গ্রাফে থাকে কিছু নোড, আর বিভিন্ন নোড এর মধ্যে কিছু পথ !
আমাদের প্রথম সমস্যায় যে ২০টি জেলা আছে তা হল নোড, আর রাস্তাগুলো হলো সেই পথ !
দেখানোর সুবিধার জন্য ৪টি জেলা দিয়ে দেখাচ্ছি । আপনি ময়মনসিংহ থেকে ঢাকা আসতে চান, তো দেখতেই পাচ্ছেন সরাসরি কোন রাস্তা নেই, কাজেই আপনাকে হয় টাঙ্গাইল নতুবা গাজীপুর ঘুরে আসতে হবে ।
এখন আপনি কি করবেন ধরুন আপনাকে শুধু দূরত্বের ব্যাপারটা মাথায় রাখতে হবে, মানে সবচেয়ে কম দূরত্ব অতিক্রম করে কি করে ঢাকা আসা যাবে, এর জন্য আমরা কিছু দূরত্ব ধরে নিতে পারি !
ছবিতে আমরা কিছু দূরত্ব ধরে নিয়েছি !
ময়মনসিংহ থেকে যাত্রা শুরু !
এডিট ভালো করতে পারি নি বলে দুঃখিত । যাই হোক , এখন আমরা এখান থেকে টাঙ্গাইল ও গাজিপুর যেতে পারি।
টাঙ্গাইল যেতে ৫০ কি মি, আর গাজীপুর যেতে ৩০ কি মি, তাই আপাতত গাজীপুর যাওয়াই ভালো !
এখন গাজীপুর থেকে ঢাকা যাওয়ার সরাসরি পথ আছে, একই ভাবে টাঙ্গাইল থেকেও আছে।
- ময়মনসিংহ - গাজীপুর - ঢাকা = (৩০ + ২৭ ) = ৫৭ কি মি।
- ময়মনসিংহ - টাঙ্গাইল - ঢাকা = (৫০ + ১৫) = ৬৫ কি মি
তো আপাতত দেখতেই পাচ্ছি ২য় মাধ্যমেই যাওয়া ভালো ! কিন্তু আমার হাতে আরো কিছু পথ আছে যেগুলো আমরা দেখি নি ! সেটি হল টাঙ্গাইল ও গাজীপুরের মাঝে ১০ কি মি ১টি পথ আছে,
3. ময়মনসিংহ - গাজীপুর-টাঙ্গাইল - ঢাকা = (৩০ + ১০ + ১৫ ) = ৫৫ কি মি ।
4. ময়মনসিংহ -- টাঙ্গাইল -গাজীপুর-- ঢাকা = (৫০ + ১০ + ২৭) = ৮৭ কি মি ।
4. ময়মনসিংহ -- টাঙ্গাইল -গাজীপুর-- ঢাকা = (৫০ + ১০ + ২৭) = ৮৭ কি মি ।
এখন আমরা সবগুলো সম্ভাব্য পথ দেখে ফেলেছি ! এদের মধ্যে এখন খুব সহজেই আমরা সবচেয়ে কম দূরত্বের পথ বের করতে পারি । উপরে দেখতেই পাচ্ছি ৩য় উপায়ে অর্থাৎ ময়মনসিংহ - গাজীপুর- টাঙ্গাইল - ঢাকা এই পথে গেলে আমরা সবচেয়ে সহজে এবং কম দূরত্ব অতিক্রম করে ঢাকা যেতে পারব ।
এই পথ বের করতে আমাকে সবগুলো জেলা এবং সবগুলো পথ ঘুরে দেখতে হয়েছে, ৪টি জেলা বলে আমাদের কাছে অনেক সহজ মনে হয়েছে, কিন্তু যদি শহর ৪০ টি হত, বা ৪০০ টি হত, অথবা ৪০০০টি হত, তখন? তখন এই কাজটি ই করে দিবে গ্রাফ এর কিছু অ্যালগরিদম, গ্রাফ পরিভ্রমন করতে সবচেয়ে জনপ্রিয় ও ব্যবহৃত এলগরিদম হল ডি এফ এস (ডেপ্ত ফার্স্ট সার্চ) ও বি এফ এস ( ব্রেডথ ফার্স্ট সার্চ ) ।
আর এদের মাঝে সরটেস্ট পথ বের করতে আছে অয়ারসাল ও ডায়াস্ট্রা অ্যালগরিদম !
আর এদের মাঝে সরটেস্ট পথ বের করতে আছে অয়ারসাল ও ডায়াস্ট্রা অ্যালগরিদম !
এগুলো নিয়ে পরে আলোচনা করবো। প্রথমে দেখব কি করে এই গ্রাফকে কম্পিউটার মেমরীতে ইনপুট দেয়া যায় !
এর জন্য সবচেয়ে সহজ পদ্ধতি হল অ্যাডজাসেন্সি ম্যাট্রিক্স !
ময়মনসিংহ টাঙ্গাইল গাজীপুর ঢাকা
ময়মনসিংহ ০ ১ ১ ০
টাঙ্গাইল ১ ০ ১ ১
গাজীপুর ১ ১ ০ ১
ঢাকা ০ ১ ১ ০
উপরে যা দেখছি তা হল ১টি পাথ ম্যাট্রিক্স , সংশ্লিষ্ট নোড (জেলা) এর মধ্যে কোন পথ থাকলে ১ না থাকলে ০ বসানো হয়েছে ! যেমন দেখতেই পাচ্ছেন যে ময়মনসিংহ থেকে টাঙ্গাইল ও গাজীপুর এ পথ আছে বলে তাতে ১ বসানো হয়েছে, কিন্তু ঢাকার সাথে নেই বলে ০ বসানো হয়েছে , এক ই ভাবে বাকীগুলো বসানো হয়েছে। যেহেতু এটি ১টি আনডাইরেক্টেড গ্রাফ, তাই ১টি জায়গা থেকে আরেক জায়গায় গেলে অই পথে ফেরত ও আসা যাবে, কিন্তু রাস্তা গুলো ওয়ান ওয়ে হলে অন্যরকম ঘটনা হত, ডাইরেক্টেড গ্রাফ নিয়ে পরবর্তী সংখ্যায় লিখব ।
এবার দেখব অয়েটেড ম্যাট্রিক্স, যাতে পথ থাকলে পথের দূরত্ব সহ দেখাবে !!
Simply Nice Dosto.
ReplyDeleteলিখে আপনার বোঝানোর ক্ষমতা অনেক ভাল । বাকীটাও লিখে ফেলেন। আপনার ব্লগের ফিড নিলাম।
ReplyDelete