Art + Math + Science + English
  1. গণিত
  2. ক্লাস ১১
  3. প্রজেক্ট ২১
উদ্ভাবন ও সমস্যা সমাধানের মাধ্যমে গণিত

২১স্কুলে যাওয়ার দ্রুততম পথ: সংক্ষিপ্ততম পথ আর ডাইকস্ট্রার অ্যালগরিদম

দলগুলো তাদের বাড়ি আর স্কুলের মধ্যের রাস্তা, গলি আর বাস বা রিকশার স্টপের একটি মানচিত্র নেটওয়ার্ক (গ্রাফ) হিসেবে আঁকে: বিন্দুগুলো মোড় আর রেখাগুলো যাত্রার মিনিট লেখা রাস্তার অংশ। তারা ডাইকস্ট্রার অ্যালগরিদম শেখে, যে ধাপে ধাপে পদ্ধতির ওপর ম্যাপ অ্যাপ তৈরি, হাতে হাতে তা দিয়ে দ্রুততম পথ বের করে, আর তারপর তাদের স্কুলের জন্য একটি ভালো রুট পরিকল্পনা বা হাঁটার দলের পরিকল্পনা বানায়।

ক্লাস ও বয়স
ক্লাস ১১ · ১৬–১৭
কাজের ধরন
দলগত
সময় লাগবে
৬০ মিনিটের ২–৩টি সেশন
কাঠিন্য
চ্যালেঞ্জিং
আনুমানিক খরচ
৳০–৳৫০

গাণিতিক ধারণা

  • গ্রাফ: শীর্ষ, প্রান্ত আর ওজন
  • সংক্ষিপ্ততম পথের সমস্যা
  • ডাইকস্ট্রার অ্যালগরিদম
  • অ্যালগরিদমের দক্ষতা
  • আসল যাত্রার সময়ের মডেলিং

শেখার উদ্দেশ্য

  • একটি আসল রাস্তার নেটওয়ার্ককে ওজনযুক্ত গ্রাফ হিসেবে উপস্থাপন করা।
  • হাতে হাতে ডাইকস্ট্রার অ্যালগরিদম চালানো।
  • উত্তর যাচাই করা আর পদ্ধতিটি কেন কাজ করে ব্যাখ্যা করা।
  • ফলাফল ব্যবহার করে একটি বাস্তব উন্নতির প্রস্তাব দেওয়া।

বাস্তব জীবনের সাথে সম্পর্ক

ম্যাপ আর রাইড শেয়ারিং অ্যাপ, ডেলিভারি কোম্পানি আর অ্যাম্বুলেন্স সেবা সবাই প্রতি সেকেন্ডে বহুবার সংক্ষিপ্ততম পথের সমস্যা সমাধান করে। নেটওয়ার্ক প্রকৌশলীরা ইন্টারনেট জুড়ে তথ্য পাঠাতে একই ধারণা ব্যবহার করেন।

প্রয়োজনীয় উপকরণ

  • চার্ট পেপার, রঙিন কলম, স্টিকি নোট
  • একটি স্থানীয় মানচিত্র (ছাপা বা হাতে আঁকা)
  • এক সপ্তাহ ধরে সহপাঠীদের কাছ থেকে সংগ্রহ করা যাত্রার সময়ের আন্দাজ
  • ঐচ্ছিক: একটি স্প্রেডশিট বা একটি সহজ প্রোগ্রাম

ধাপে ধাপে নির্দেশনা

  1. একটি অনুশীলনের নেটওয়ার্ক দিয়ে শুরু করো: বাড়ি H, মোড় A, B, C আর স্কুল S। রাস্তা: H-A ৪ মিনিট, H-B ২, B-A ১, A-C ৫, B-C ৮, C-S ৩, A-S ১০।
  2. ডাইকস্ট্রার নিয়ম শেখো: H-কে লেবেল ০ দাও। বারবার সবচেয়ে ছোট লেবেলের অসমাপ্ত বিন্দু বেছে তাকে স্থায়ী করো, আর লেবেল + রাস্তার সময় ছোট হলে তার প্রতিবেশীদের আপডেট করো।
  3. একটি সারণিতে অনুশীলনের নেটওয়ার্কটি করো। প্রতিটি লেবেল আর তা কোথা থেকে এসেছে লেখো।
  4. S থেকে পেছনে গিয়ে দ্রুততম পথ আর তার সময় পড়ো। অন্য পথগুলোর তালিকা করে যাচাই করো।
  5. এখন তোমার আসল নেটওয়ার্ক বানাও: মোড় আর স্টপ চিহ্নিত করো, আর জরিপ থেকে প্রতিটি রাস্তায় সাধারণ মিনিট লেখো।
  6. তিনটি আলাদা বাড়ির জন্য অ্যালগরিদম চালাও। কোন রাস্তাগুলো অনেক দ্রুততম পথে আসে?
  7. একটি ওজন বদলাও (যেমন বর্ষায় পানি ওঠে এমন রাস্তা) আর আবার চালাও। কী বদলায়?
  8. এক পাতার একটি প্রস্তাব লেখো: একটি নিরাপদ বা দ্রুত রুট পরিকল্পনা, একটি হাঁটার দল বা একটি ভালো মিলনস্থান।

গাণিতিক ব্যাখ্যা

অনুশীলনের নেটওয়ার্কে লেবেলগুলো এই ক্রমে স্থায়ী হয়: H = ০, B = ২, A = ৩ (B হয়ে, সরাসরি ৪-এর চেয়ে ভালো), C = ৮, আর শেষে S = ১১। দ্রুততম পথ H, B, A, C, S, যাতে ১১ মিনিট লাগে; H, A, C, S-এ লাগে ১২ আর H, B, A, S-এ ১৩। ডাইকস্ট্রার পদ্ধতি কাজ করে কারণ যখন একটি বিন্দুর লেবেল অসমাপ্ত বিন্দুগুলোর মধ্যে সবচেয়ে ছোট, তখন অন্য কোনো পথ তাতে দ্রুত পৌঁছাতে পারে না, কারণ অন্য প্রতিটি পথকে আগে এমন একটি বিন্দু দিয়ে যেতে হবে যা অন্তত ততটা দূরে, আর রাস্তার সময় কখনো ঋণাত্মক নয়। আসল নেটওয়ার্ক বড়, তাই কম্পিউটার অ্যালগরিদমটি চালায়, কিন্তু যুক্তি ঠিক সেটাই যা শিক্ষার্থীরা হাতে করে।

প্রত্যাশিত ফলাফল

স্কুল এলাকার একটি লেবেলযুক্ত নেটওয়ার্ক মানচিত্র, কয়েকটি বাড়ির জন্য ডাইকস্ট্রা সারণি, একটি বর্ষাকালের তুলনা আর এক পাতার একটি রুট প্রস্তাব।

যে দক্ষতা গড়ে ওঠে

  • গ্রাফ মডেলিং
  • একটি অ্যালগরিদম অনুসরণ আর ব্যাখ্যা করা
  • জরিপ থেকে তথ্য সংগ্রহ
  • একটি বাস্তব প্রস্তাব লেখা

মূল্যায়নের মানদণ্ড

  • অনুশীলনের নেটওয়ার্ক সঠিকভাবে সমাধান করা (১১ মিনিট)।
  • আসল নেটওয়ার্ক যুক্তিসঙ্গত ওজনসহ পরিষ্কারভাবে আঁকা।
  • অ্যালগরিদমের সারণি সম্পূর্ণ আর সঠিকভাবে পেছনে ট্রেস করা।
  • প্রস্তাবে ফলাফল ব্যবহার করা আর নিরাপত্তা বিবেচনা করা।

এক্সটেনশন চ্যালেঞ্জ

তোমার নেটওয়ার্কে ডাইকস্ট্রার অ্যালগরিদম চালায় এমন একটি ছোট প্রোগ্রাম (পাইথন বা স্প্রেডশিট) লেখো। তারপর খুঁজে বের করো ন্যূনতম বিস্তৃত বৃক্ষ (minimum spanning tree) কী আর একটি শহরের কখন তার দরকার হবে।

নিরাপত্তা ও অন্তর্ভুক্তি

শুধু নিজেদের স্বাভাবিক যাত্রা থেকে সময় সংগ্রহ করবে। মাপার জন্য একা অচেনা রাস্তায় হাঁটবে না, আর সহপাঠীদের বাড়ির অবস্থান ক্লাসের বাইরে শেয়ার করবে না।