মূল বিষয়বস্তু
কম্পিউটার বিজ্ঞান
কোর্স: কম্পিউটার বিজ্ঞান > অধ্যায় 1
পাঠ 1: অ্যালগোরিদম পরিচিতিরাস্তা-খুঁজে বের করা
কখনো কখনো কোন সমস্যা আলাদা মনে হলেও তাদের সমাধান করতে গেলে দেখা যায় যে তারা একই রকম। প্যাক-ম্যান, ব্রিটেনের রাজপরিবার এবং অরল্যান্ডো যাত্রা এগুলোর মধ্যে কি মিল খুঁজে পাওয়া যায়? তাদের সবগুলোই রাস্তা বের করা বা পথ খোঁজা সম্পর্কিত সমস্যা:
- কীভাবে বর্তমান রাজপুত্র উইলিয়াম, রাজা উইলিয়াম lll যে 1963 সালে কলেজ অফ উইলিয়াম অ্যান্ড মেরিতে অনুদান করেছিলেন তার সাথে সম্পর্কিত?
- ভূত কোন পথ বেছে নিলে যত তাড়াতাড়ি সম্ভব প্যাক-ম্যানের কাছে পৌঁছে যাবে?
- ডালাস, টেক্সাস থেকে অরল্যান্ডো, ফ্লোরিডা যাবার সবচেয়ে ভালো রাস্তা কোনটি?
এই প্রশ্নগুলোর উত্তর পেতে আমাদের কিছু তথ্য দিতে হবে।
উদাহরণস্বরূপ, ব্রিটেনের রাজপরিবারের বংশধারাতে আমরা দেখতে পারব সবার মধ্যে সম্পর্কগুলো। প্রিন্স উইলিয়াম হল চার্লস ফিলিপ আর্থার উইন্ডসর এর ছেলে। চার্লস হল রাণী এলিজাবেথ ll এর ছেলে। আমাদের সমস্যাটি হচ্ছে বংশধারার এই সম্পর্কগুলো ব্যবহার করে প্রিন্স উইলিয়াম এবং উইলিয়াম lll এর মধ্যে সবচেয়ে ছোট সম্পর্ক শিকলটি বের করা। তুমি নিচের সারনি দেখে বুঝতে পারছ যে, এর জন্য কয়েকটি সম্পর্কের প্রয়োজন।
প্যাক-ম্যানের জন্য, আমাদের একটি ধাঁধাঁর মানচিত্র লাগবে। এই ম্যাপটি এই মেজ বা ধাঁধাঁর মধ্যে সংলগ্ন থাকা উন্মুক্ত বর্গগুলো প্রদর্শন করছে—অথবা যে বর্গগুলোর মধ্যে কোন সংযোগ নেই অর্থাৎ দুইটি বর্গের মধ্যে একটি দেয়াল আছে সেটিও এখানে প্রদর্শন করছে—and the problem is to find a path along black squares that leads the ghost to Pac-Man.
ডালাস থেকে অরল্যান্ডো যাবার পথ খুঁজে বের করার জন্য, আমাদের লাগবে মার্কিন যুক্তরাষ্ট্রের মানচিত্র, যেখানে নিকটবর্তী শহরগুলোর মধ্যে সম্পর্ক ও রাস্তাগুলো দেখা যাবে। এমন কোন রাস্তা নেই যা সরাসরি ডালাস আর অরল্যান্ডো কে সংযুক্ত করে, কিন্তু বিভিন্ন ধাপে রাস্তা আছে।
একটি ধাঁধাঁ অনুসন্ধান
Maze games are fun, so let's delve deeper into one. In our game, the main character can navigate to destinations in a maze.
As the human player, you control the main character by clicking on the next destination in the maze, and the computer figures out how to move the character there. The destination is marked with a red rectangle labeled "GOAL", and the character starts off on their first destination, the start square. Try playing it below:
খেয়াল করেছ কীভাবে বস্তুটি লক্ষ্যের দিকে সরে যায়? এটা করার জন্য, প্রোগ্রামকে নির্ণয় করতে হবে ব্যবহারকারী যেখানে ক্লিক করেছে সেখানে বস্তুটি যাবার সঠিক রাস্তাগুলো কি কি এবং তারপর সেই সরে যাওয়া অ্যানিমেশন করতে হবে। এখানে বস্তুটি যাবার একাধিক রাস্তা থাকতে পারে এবং প্রোগ্রামকে সেগুলো থেকে সর্বোত্তম পথটি বাছাই করতে হবে।
কোন অ্যালগোরিদম বাছাই করার আগে, সরে যাওয়ার নিয়মগুলো নির্ধারণ করতে হবে: দেয়াল হবে ধূসর বর্গ এবং সরে যাওয়ার সঠিক রাস্তা হবে ফাঁকা বর্গ। প্রতিটি ধাপে, বস্তুটি একটি বর্গ থেকে তার সংলগ্ন বর্গগুলোতে যেতে পারবে। এই বস্তুটি দাবার নৌকার মত আড়াআড়ি যেতে পারবে না।
যে অ্যালগোরিদমটি, এই প্রোগ্রামটি কাজ করার পিছনে কাজ করে তাহল: লক্ষ্যের কাছাকাছি 1 বর্গ সরিয়ে নিয়ে নিয়ে যেতে হবে—ব্যবহারকারী যেখানে ক্লিক করেছে সেদিকে—in each step. কিন্তু "লক্ষ্যের দিকে" বলতে কি বুঝাচ্ছে? একটি সোজা রেখায় লক্ষ্যের দিকে আগালে প্রায়ই বস্তুটি দেয়ালে বাঁধা পাবে। অ্যালগোরিদমকে নির্ণয় করতে হবে আশেপাশের কোন বর্গটি আসলেই "লক্ষ্যের দিকে" নিয়ে যাবে, আর আমরা সেটা করতে পারি প্রত্যেকটি বর্গকে একটি মান দিয়ে যেটা উপস্থাপন করবে সর্বনিম্ন ধাপের সংখ্যা যেটা বস্তুটি নিলে সেখান থেকে লক্ষ্যে পৌছাতে পারবে। এই অ্যালগোরিদম ব্যবহার করে প্রত্যেকটি বর্গে একটি মান দেওয়া যায়:
- লক্ষ্য বর্গটিতে শুরু করব। লক্ষ্য, লক্ষ্য থেকে কত দূরে? শূন্য ধাপ, লক্ষ্যকে 0 দিয়ে চিহ্নিত কর।
- ধাঁধাঁয় সেই বর্গগুলো খুঁজে বের কর যেগুলো লক্ষ্য থেকে ঠিক এক ধাপ দূরে। তাদেরকে 1 দিয়ে চিহ্নিত কর। এইক্ষেত্রে, যদি লক্ষ্য বেরিয়ে যাবার বর্গ হয়, তাহলে সেখানে এমন শুধুমাত্র একটি বর্গ থাকবে যা এক ধাপ দূরে আছে।
- এখন এমন সব বর্গগুলো খুঁজে বের কর যা লক্ষ্য থেকে 2 ধাপ দূরে। এই বর্গগুলো 1 দিয়ে চিহ্নিত বর্গগুলো থেকে 1 ধাপ দূরে হবে যেগুলো এখনও চিহ্নিত হয়নি। সেগুলোকে 2 দিয়ে চিহ্নিত কর।
- এখন এমন সব বর্গগুলো চিহ্নিত কর যা লক্ষ্য থেকে 3 ধাপ দূরে। এই বর্গগুলো 2 দিয়ে চিহ্নিত বর্গগুলো থেকে 1 ধাপ দূরে হবে যেগুলো এখনও চিহ্নিত হয়নি। সেগুলোকে 3 দিয়ে চিহ্নিত কর।
- ধাঁধাঁয় বর্গগুলো দূরত্ব অনুযায়ী চিহ্নিত করতে থাক।
অবশেষে, অ্যালগোরিদম সেই বর্গটি চিহ্নিত করে যেখানে বস্তুটি আছে। তারপর প্রোগ্রামটি লক্ষ্যের দিকে একটি পথ বাছাই করবে কয়েকটি বর্গের একটি ক্রম দিয়ে যেখানে বর্গের সংখ্যাগুলো ধীরে ধীরে কমতে থাকবে। যদি তুমি সংখ্যাগুলোকে বর্গের উচ্চতা হিসেবে চিন্তা কর, তাহলে এটা অনেকটা হবে পাহাড় থেকে নামার মত।
তুমি নিচে এখানে মান-চিহ্নিতকরণ অ্যালগোরিদম খেলে দেখতে পার। "রিস্টার্ট অ্যালগোরিদম" ক্লিক করে বার বার দেখে নিতে পার।
কি হবে যদি ব্যবহারকারী শুরুর বর্গ থেকে লক্ষ্যের বর্গে যেতে চায়? এই বর্গ-চিহ্নিতকরন অ্যালগোরিদম ব্যবহার করে, শুরুর বর্গ লক্ষ্য থেকে 13 ধাপ দূরে আছে। এখানে একটি চিত্রে দেখানো হয়েছে বস্তুটির সম্ভাব্য অবস্থানের মধ্যে সম্পর্কগুলো, শুরু, লক্ষ্য এবং লক্ষ্য থেকে প্রত্যেকটি অবস্থানের সর্বনিম্ন দূরত্ব:
There's a square immediately to the south of the start that is only 12 steps from the goal. So the first move is "south". South of that square is an 11. South again. South again to a 10. Then east to a 9. East twice more to a 7, then north five times to a 2. Finish up by going west once, to a 1, and finally north once, to the goal.
We won't discuss exactly how to implement this maze search algorithm right now, but you might find it fun to think about how you might represent the maze and the character using JavaScript and how you might implement the algorithm.
এই বিষয়বস্তুটি Dartmouth Computer Science এর প্রফেসর Thomas Cormen এবং Devin Balkcom এর সহযোগিতায় এবং একই সাথে খান একাডেমির কম্পিউটিং শিক্ষাক্রম দলের একসাথে কাজ করার মাধ্যমে তৈরি করা হয়েছে। এই বিষয়বস্তু CC-BY-NC-SA দিয়ে লাইসেন্সকৃত।
আলোচনায় অংশ নিতে চাও?
গেমটির ধাপ গুলো বুঝি নাই(1 টি ভোট)