মূল বিষয়বস্তু
ব্রেথ-ফার্স্ট সার্চ এবং এর ব্যবহার
প্রারম্ভিক এই টিউটোরিয়ালে, একটি চরিত্র নিয়ে তুমি খেলছ, যেখানে এই চরিত্রটিকে একটি লক্ষ্যে নিয়ে যাবার জন্য গোলকধাঁধার মধ্য দিয়ে তুমি নিয়ে যাচ্ছ। তুমি কাজটি শুরু করেছ এটা বলার মাধ্যমে যে লক্ষ্যটি তার নিজের অবস্থান থেকে শূন্য ধাপ দূরে। তারপর তুমি সেই বর্গগুলো খুঁজে পেলে যেগুলো লক্ষ্য থেকে এক ধাপ দূরে। তারপর সব বর্গগুলো যেগুলো লক্ষ্য থেকে দুই ধাপ দূরে। তারপর তিন ধাপ এবং এভাবেই যতক্ষণ পর্যন্ত না তুমি সেই বর্গটিতে পৌছাচ্ছ যেখান থেকে তোমার চরিত্রটি চলা শুরু করেছিল। এখন যদি তুমি সেই বর্গটি খুঁজে বের করতে চাও যে বর্গটি
প্রারম্ভিক টিউটোরিয়ালে আমরা এই ছবিটি দেখেছি:
এখন এটিকে তুমি একটি অদিকনির্দেশক লেখচিত্র হিসেবে চিহ্নিত করতে পার। বর্গের সংলগ্ন থাকা প্রতিটি বর্গ দেয়ালের অংশ নয় এবং প্রতিটি প্রান্তবিন্দু তার সংলগ্ন বর্গগুলোর সাথে ছোট ঘটনা হিসেবে অবস্থান করছে।
উপরের কার্যপ্রণালী অনুসরণ করে খুঁজে পাওয়া পথটির গুরুত্বপূর্ণ একটি বৈশিষ্ট্য রয়েছে: এই পথটি বাদে চরিত্র থেকে এর লক্ষ্য পর্যন্ত যাওয়া অন্য কোন পথ এর চেয়ে কম সংখ্যক বর্গের ভিতর দিয়ে যায় না। এর কারণ হল এটি খুঁজে বের করার জন্য যে অ্যালগোরিদমটি আমরা এখানে ব্যবহার করেছি সেটি ব্রেডথ-ফার্স্ট সার্চ নামে আমরা চিনি। ব্রেডথ-ফার্স্ট সার্চ, যেটাকে আমরা বিএফএস নামেও চিনে থাকি, মূল শীর্ষবিন্দু থেকে অন্য শীর্ষবিন্দুগুলোতে যাওয়ার জন্য, পথগুলোতে থাকা প্রান্তবন্দুর সংখ্যার উপরে ভিত্তি করে সংক্ষিপ্ত পথটি খুঁজে বের করে।
ব্রেডথ-ফার্স্ট সার্চের আরও একটি উদাহরণ এখানে দেওয়া হল: "সিক্স ডিগ্রীস অফ কেভিন বেকন" গেম। এখানে, খেলোয়াড়েরা সিনেমায় অভিনয় করা অভিনেতা এবং অভিনেত্রীদের কে কোন সিনেমায় অভিনয় করেছে তার উপরে ভিত্তি করে কেভিন বেকনের সাথে সংযোগ প্রদান করা চেষ্টা করে থাকে। চেইনটি যত ছোট হবে তত ভালো এবং এর ফলাফলটি স্তম্ভিত করে দেবার মত যে কতজন অভিনেতা এবং অভিনেত্রী কেভিন বেকনের কাছে পৌছাতে পারে আর চেইনের মধ্যে থাকা অভিনেতা ও অভিনেত্রীর সংখ্যাটি হবে ছয়জন বা তার কম। একজন অস্ট্রেলিয়ান অভিনেত্রী কেটি বেলের উদাহরণ দেখা যাক। তিনি ন্যাশ এডগারটনের সাথে 2006 সালে ম্যাকবেথে অভিনয় করেছেন; এডগারটন, লাউরেন্স ফিসবার্নের সাথে 2003 সালে দ্যা ম্যাট্রিক্স রিলোডেডে অভিনয় করেছেন; এবং ফিসবার্ন, কেভিন বেকনের সাথে 2003 সালে মিসটিক রিভার নামের সিনেমাতে অভিনয় করেছেন। সুতরাং, কেটি বেলের "কেভিন বেকন সংখ্যাটি" হল 3। প্রকৃতপক্ষে, কেটি বেলের, কেভিন বেকন সংখ্যা যে 3 তা খুঁজে বের করার জন্য বেশ কয়েকটি পদ্ধতি আছে। তুমি যে কোন অভিনেতা অথবা অভিনেত্রীর কেভিন বেকন সংখ্যা দেখতে পার দ্যা ওরাকল অফ কেভিন বেকন ওয়েবসাইট থেকে।
হয়তো তুমি এখানে অনুমান করতে পার যে, দ্যা ওরাকল বেকন ওয়েবসাইটটি একটি অদিকনির্দেশক লেখচিত্র রক্ষা করে থাকে যেখানে প্রতিটি শীর্ষবিন্দু একজন অভিনেত্রী অথবা অভিনেত্রীকে প্রকাশ করছে এবং যদি দুইজন অভিনেতা একই সিনেমাতে অভিনয় করে থাকে তাহলে তাদের শীর্ষবিন্দুতে, প্রান্তবিন্দুর একটি ঘটনা রয়েছে। কেভিন বেকনের শীর্ষবিন্দু থেকে একটি ব্রেডথ-ফার্স্ট সার্চ, চেইনের ভিতরে থাকা অভিনেতা এবং অভিনেত্রীদের কাছে যাবার জন্য সবচেয়ে সংক্ষিপ্ত পথটি খুঁজে বের করতে হবে।
এই বিষয়বস্তুটি Dartmouth Computer Science এর প্রফেসর Thomas Cormen এবং Devin Balkcom এর সহযোগিতায় এবং একই সাথে খান একাডেমির কম্পিউটিং শিক্ষাক্রম দলের একসাথে কাজ করার মাধ্যমে তৈরি করা হয়েছে। এই বিষয়বস্তু CC-BY-NC-SA দিয়ে লাইসেন্সকৃত।
আলোচনায় অংশ নিতে চাও?
কোন আলাপচারিতা নেই।