কখনো কখনো কোন সমস্যা আলাদা মনে হলেও তাদের সমাধান করতে গেলে দেখা যায় যে তারা একই রকম। প্যাক-ম্যান, ব্রিটেনের রাজপরিবার, এবং অরল্যান্ডো যাত্রা এগুলোর মধ্যে কি মিল খুঁজে পাওয়া যায়? তাদের সবগুলোই রাস্তা বের করা বা পথ খোঁজা সম্পর্কিত সমস্যা:
  • কিভাবে বর্তমান রাজপুত্র উইলিয়াম, রাজা উইলিয়াম lll যে ১৯৬৩ সালে কলেজ অফ উইলিয়াম অ্যান্ড মেরিতে অনুদান করেছিলেন তার সাথে সম্পর্কিত?
  • ভূত কোন পথ বেছে নিলে যত তাড়াতাড়ি সম্ভব প্যাক-ম্যানের কাছে পৌঁছে যাবে?
  • ডালাস, টেক্সাস থেকে অরল্যান্ডো, ফ্লোরিডা যাবার সবচেয়ে ভালো রাস্তা কোনটি?
এই প্রশ্নগুলোর উত্তর পেতে আমাদের কিছু তথ্য দিতে হবে।
উদাহরণস্বরূপ, ব্রিটেনের রাজপরিবারের বংশধারাতে আমরা দেখতে পারব সবার মধ্যে সম্পর্কগুলো। প্রিন্স উইলিয়াম হল চার্লস ফিলিপ আর্থার উইন্ডসর এর ছেলে। চার্লস হল রাণী এলিজাবেথ ll এর ছেলে। আমাদের সমস্যাটি হচ্ছে বংশধারার এই সম্পর্কগুলো ব্যবহার করে প্রিন্স উইলিয়াম এবং উইলিয়াম lll এর মধ্যে সবচেয়ে ছোট সম্পর্ক শিকলটি বের করা। তুমি নিচের সারনি দেখে বুঝতে পারছ যে, এর জন্য কয়েকটি সম্পর্কের প্রয়োজন।
রাজপরিবারের বংশধারায় এলিজাবেথ II ও উইলিয়াম III কে চিহ্নিত করা হয়েছে
প্যাক-ম্যানের জন্য, আমাদের একটি ধাঁধাঁর মানচিত্র লাগবে। এই ম্যাপটি এই মেজ বা ধাঁধাঁর মধ্যে সংলগ্ন থাকা উন্মুক্ত বর্গগুলো প্রদর্শন করছে—অথবা যে বর্গগুলোর মধ্যে কোন সংযোগ নেই অর্থাৎ দুইটি বর্গের মধ্যে একটি দেয়াল আছে সেটিও এখানে প্রদর্শন করছে—and the problem is to find a path along black squares that leads the ghost to Pac-Man.
প্যাক-ম্যান ধাঁধাঁয় প্যাক-ম্যান ও ভুতকে চিহ্নিত করা হয়েছে
ডালাস থেকে অরল্যান্ডো যাবার পথ খুঁজে বের করার জন্য, আমাদের লাগবে মার্কিন যুক্তরাষ্ট্রের মানচিত্র, যেখানে নিকটবর্তী শহরগুলোর মধ্যে সম্পর্ক ও রাস্তাগুলো দেখা যাবে। এমন কোন রাস্তা নেই যা সরাসরি ডালাস আর অরল্যান্ডো কে সংযুক্ত করে, কিন্তু বিভিন্ন ধাপে রাস্তা আছে।
মার্কিন যুক্তরাষ্ট্রের রাস্তাচিত্রে ডালাস ও অরল্যান্ডো চিহ্নিত করা হয়েছে

একটি ধাঁধাঁ অনুসন্ধান

চল প্যাক-ম্যানের মত আরেকটা নিয়ে আরেকটু গভীরভাবে চিন্তা করি, এটা একটা কম্পিউটার গেম যার প্রধান চরিত্রকে নিয়ন্ত্রন করা হয় ধাঁধাঁয় কোথায় ক্লিক করে। গেমটি নিচে আছে। কয়েকটি অবস্থানে ক্লিক করে বস্তুটিকে সরানোর চেষ্টা কর, যেটা হল হলুদ বৃত্তটি, আর লক্ষ্য হল লাল আয়তক্ষেত্র।
খেয়াল করেছ কিভাবে বস্তুটি লক্ষ্যের দিকে সরে যায়? এটা করার জন্য, প্রোগ্রামকে নির্ণয় করতে হবে ব্যবহারকারী যেখানে ক্লিক করেছে সেখানে বস্তুটি যাবার সঠিক রাস্তাগুলো কি কি এবং তারপর সেই সরে যাওয়া অ্যানিমেশন করতে হবে। এখানে বস্তুটি যাবার একাধিক রাস্তা থাকতে পারে, এবং প্রোগ্রামকে সেগুলো থেকে সর্বোত্তম পথটি বাছাই করতে হবে।
কোন অ্যালগোরিদম বাছাই করার আগে, সরে যাওয়ার নিয়মগুলো নির্ধারণ করতে হবে: দেয়াল হবে ধূসর বর্গ এবং সরে যাওয়ার সঠিক রাস্তা হবে ফাঁকা বর্গ। প্রতিটি ধাপে, বস্তুটি একটি বর্গ থেকে তার সংলগ্ন বর্গগুলোতে যেতে পারবে। এই বস্তুটি দাবার নৌকার মত আড়াআড়ি যেতে পারবে না।
যে অ্যালগোরিদমটি, এই প্রোগ্রামটি কাজ করার পিছনে কাজ করে তাহল: লক্ষ্যের কাছাকাছি 1 বর্গ সরিয়ে নিয়ে নিয়ে যেতে হবে—ব্যবহারকারী যেখানে ক্লিক করেছে সেদিকে—in each step. কিন্তু "লক্ষ্যের দিকে" বলতে কি বুঝাচ্ছে? একটি সোজা রেখায় লক্ষ্যের দিকে আগালে প্রায়ই বস্তুটি দেয়ালে বাঁধা পাবে। অ্যালগোরিদমকে নির্ণয় করতে হবে আশেপাশের কোন বর্গটি আসলেই "লক্ষ্যের দিকে" নিয়ে যাবে, আর আমরা সেটা করতে পারি প্রত্যেকটি বর্গকে একটি মান দিয়ে যেটা উপস্থাপন করবে সর্বনিম্ন ধাপের সংখ্যা যেটা বস্তুটি নিলে সেখান থেকে লক্ষ্যে পৌছাতে পারবে। এই অ্যালগোরিদম ব্যবহার করে প্রত্যেকটি বর্গে একটি মান দেওয়া যায়:
  1. লক্ষ্য বর্গটিতে শুরু করব। লক্ষ্য, লক্ষ্য থেকে কত দূরে? শূন্য ধাপ, লক্ষ্যকে ০ দ্বারা চিহ্নিত কর।
  2. ধাঁধাঁয় সেই বর্গগুলো খুঁজে বের কর যেগুলো লক্ষ্য থেকে ঠিক এক ধাপ দূরে। তাদেরকে ১ দ্বারা চিহ্নিত কর। এইক্ষেত্রে, যদি লক্ষ্য বেরিয়ে যাবার বর্গ হয়, তাহলে সেখানে এমন শুধুমাত্র একটি বর্গ থাকবে যা এক ধাপ দূরে আছে।
  3. এখন এমন সব বর্গগুলো খুঁজে বের কর যা লক্ষ্য থেকে ২ ধাপ দূরে। এই বর্গগুলো ১ দ্বারা চিহ্নিত বর্গগুলো থেকে ১ ধাপ দূরে হবে যেগুলো এখনও চিহ্নিত হয়নি। সেগুলোকে ২ দিয়ে চিহ্নিত কর।
  4. এখন এমন সব বর্গগুলো চিহ্নিত কর যা লক্ষ্য থেকে ৩ ধাপ দূরে। এই বর্গগুলো ২ দ্বারা চিহ্নিত বর্গগুলো থেকে ১ ধাপ দূরে হবে যেগুলো এখনও চিহ্নিত হয়নি। সেগুলোকে ৩ দিয়ে চিহ্নিত কর।
  5. ধাঁধাঁয় বর্গগুলো দূরত্ব অনুযায়ী চিহ্নিত করতে থাক। k সংখ্যা দ্বারা বর্গ চিহ্নিত হয়ে যাবার পর, k চিহ্নিত বর্গের এক ধাপ পরের সব বর্গকে k, plus, 1 সংখ্যা দ্বারা চিহ্নিত করতে হবে যেগুলো এখনও চিহ্নিত হয়নি।
অবশেষে, অ্যালগোরিদম সেই বর্গটি চিহ্নিত করে যেখানে বস্তুটি আছে। তারপর প্রোগ্রামটি লক্ষ্যের দিকে একটি পথ বাছাই করবে কয়েকটি বর্গের একটি ক্রম দিয়ে যেখানে বর্গের সংখ্যাগুলো ধীরে ধীরে কমতে থাকবে। যদি তুমি সংখ্যাগুলোকে বর্গের উচ্চতা হিসেবে চিন্তা কর, তাহলে এটা অনেকটা হবে পাহাড় থেকে নামার মত।
তুমি নিচে এখানে মান-চিহ্নিতকরণ অ্যালগোরিদম খেলে দেখতে পার। "রিস্টার্ট অ্যালগোরিদম" ক্লিক করে বার বার দেখে নিতে পার।
কি হবে যদি ব্যবহারকারী শুরুর বর্গ থেকে লক্ষ্যের বর্গে যেতে চায়? এই বর্গ-চিহ্নিতকরন অ্যালগোরিদম ব্যবহার করে, শুরুর বর্গ লক্ষ্য থেকে ১৩ ধাপ দূরে আছে। এখানে একটি চিত্রে দেখানো হয়েছে বস্তুটির সম্ভাব্য অবস্থানের মধ্যে সম্পর্কগুলো, শুরু, লক্ষ্য, এবং লক্ষ্য থেকে প্রত্যেকটি অবস্থানের সর্বনিম্ন দূরত্ব:
গোলকধাঁধার সাথে সঙ্গতিপূর্ণ লেখচিত্র
শুরুর দক্ষিণ পাশেই একটি বর্গ আছে ( ৪র্থ সারি, ৩য় কলাম) যেটা লক্ষ্য থেকে মাত্র ১২ ধাপ দূরে। তাহলে প্রথমবার সরবে "দক্ষিন" দিকে সেই বর্গটির দক্ষিণে আছে ১১। আবারো দক্ষিণ দিকে। আবারো দক্ষিণে গিয়ে ১০। তারপর পূর্বদিকে গেলে ৯। আরও দুইবার পূর্বদিকে গেলে ৭, তারপর উত্তর দিকে ৫ গেলে ২। এবং শেষ করবে পশ্চিম দিকে একবার গিয়ে, ১ এ এবং সবশেষে একবার উত্তর দিকে গিয়ে লক্ষ্যে পৌছাব।
আমরা এটা নিয়ে এখনি আলোচনা করব না যে কিভাবে এই ধাঁধাঁ অনুসন্ধান অ্যালগরিদম কাজ করে, কিন্তু তুমি হয়ত জাভাস্ক্রিপ্ট ব্যবহার করে কিভাবে ধাঁধাঁ এবং বস্তুটি উপস্থাপন করা যায় তা চিন্তা করলে বেশ মজা পাবে আর তুমি হয়ত এটা করেও ফেলতে পারবে।

এই বিষয়বস্তুটি Dartmouth Computer Science এর প্রফেসর Thomas Cormen এবং Devin Balkcom এর সহযোগিতায় এবং একই সাথে খান একাডেমির কম্পিউটিং শিক্ষাক্রম দলের একসাথে কাজ করার মাধ্যমে তৈরি করা হয়েছে। এই বিষয়বস্তু CC-BY-NC-SA দ্বারা লাইসেন্সকৃত।