মূল বিষয়বস্তু
কম্পিউটার বিজ্ঞান
ব্রেথ-ফার্স্ট সার্চ অ্যালগোরিদম
ব্রেডথ-ফার্স্ট সার্চ প্রতিটি শীর্ষবিন্দুর জন্য দুইটি মান নিযুক্ত করে থাকে v:
- একটি দূরত্ব, যেটা যে কোন পথের শীর্ষবিন্দু থেকে শীর্ষবিন্দুর সর্বনিম্ন প্রান্তবিন্দুর সংখ্যা দিবে v।
- predecessor শীর্ষবিন্দু v টি হল মূল অবস্থান থেকে সবচেয়ে সংক্ষিপ্ত পথের শীর্ষবিন্দু। শীর্ষবিন্দুর predecessor টির মূল অবস্থানের বিশেষ কিছু মান রয়েছে, যেমন
null, যেটা নির্দেশ করবে যে এর কোন predecessor নেই।
যদি মূল শীর্ষবিন্দু থেকে শীর্ষবিন্দু v পর্যন্ত কোন পথ না থাকে, তাহলে v এর দূরত্ব অসীম হবে এবং এর predecessor টির, মূল predecessor টির মত একই রকম একটি বিশেষ মান থাকবে।
উদাহরণস্বরূপ, এখানে আটটি শীর্ষবিন্দুসহ একটি অদিকনির্দেশক লেখচিত্র আছে, 0 থেকে 7 পর্যন্ত এটি নম্বর দেওয়া আছে, শীর্ষবিন্দুর সংখ্যাগুলো, শীর্ষবিন্দুর উপরে বা নিচে আসবে। প্রতিটি শীর্ষবিন্দুর ভিতরে দুইটি করে সংখ্যা দেওয়া আছে: মূল অবস্থান থেকে এর দূরত্ব, যেটা হল শীর্ষবিন্দু 3, আর শীর্ষবিন্দু 3 থেকে সবচেয়ে সংক্ষিপ্ত পথে predecessor এটাকে অনুসরণ করবে। একটি ড্যাশ ব্যবহার করে
null বুঝানো হয়:বিএফএসে (ব্রেডথ-ফার্স্ট সার্চ), প্রাথমিকভাবে আমরা প্রতিটি শীর্ষবিন্দুর দূরত্ব এবং predecessor এ বিশেষ মান ব্যবহার করব (
null)। আমরা মূল অবস্থান থেকে খোঁজার কাজটি শুরু করব এবং যখন এর অবস্থান 0 হবে তখন এটাকে আমরা নিযুক্ত করব। তারপরে আমরা মূল অবস্থানের চারপাশে দিয়ে ঘুরে আসব এবং মূল অবস্থানের আশপাশে থাকা প্রতিটি অবস্থানকে একটি দূরত্ব 1 দিব এবং এর predecessor এর মান হিসেবে মূল অবস্থানকে নির্ধারণ করে দিব। তারপরে আমরা সেই অবস্থানগুলোতে যাব যার শীর্ষবিন্দুর দূরত্ব হল 1 এবং যে অবস্থানগুলোতে আগে যাওয়া হয়নি এবং আমরা এর প্রতিটি শীর্ষবিন্দুতে একটি দূরত্ব হিসেবে 2 দিব এবং এর predecessor হিসেবে শীর্ষবিন্দু নির্ধারণ করে দিব আমরা যে অবস্থানগুলোতে গিয়েছিলাম। আমরা ততক্ষন পর্যন্ত যেতে থাকব যতক্ষণ পর্যন্ত না মূল শীর্ষবিন্দুর অবস্থান থেকে অন্যান্য শীর্ষবিন্দুগুলোতে যাওয়া হয়, সেই শীর্ষবিন্দুগুলোতে যাওয়া হবে এবং বিন্দুগুলোতে যাওয়ার আগে মূল শীর্ষবিন্দু থেকে যে শীর্ষবিন্দুগুলোর দূরত্ব হবে k আর বিন্দুগুলোতে যাওয়ার আগে শীর্ষবিন্দুগুলোর দূরত্ব ছিল k, plus, 1।উপরে দেওয়া উদাহরণটির উপরে ভিত্তি করে, এখানে ধাপগুলো এবং প্রতিটি ধাপ কীভাবে সম্পন্ন করতে হবে এখানে তার একটি ভিজুয়ালাইজেশন দেওয়া হল:
- শীর্ষবিন্দু 3, অর্থাৎ মূলঅবস্থানটি অনুসরণ করার মাধ্যমে এই কাজটি করা যাক, যেটা এর দূরত্ব নির্ধারণ করবে 0।
- তারপরে শীর্ষবিন্দু 2 এবং 6 এ যেতে হবে, এদের দূরত্ব 1 এবং তাদের predecessor এর মান শীর্ষবিন্দু 3 নির্ধারণ করার মাধ্যমে।
- মূল অবস্থান থেকে শীর্ষবিন্দুর দূরত্ব যখন 1 সেখান থেকে এর কাজ করার শুরু করা যাক, আর এটা কাজ করবে শীর্ষবিন্দু 2 থেকে। তারপরে শীর্ষবিন্দু 2 থেকে শীর্ষবিন্দু 4 এবং 5 এ যেতে হবে, এদের দূরত্ব 2 এবং তাদের predecessor এর মান শীর্ষবিন্দু 2 নির্ধারণ করার মাধ্যমে। শীর্ষবিন্দু 3 এ যাওয়ার কোন প্রয়োজন নেই, কারণ সেখানে ইতোমধ্যেই যাওয়া হয়েছে।
- শীর্ষবিন্দু 6 থেকে, শীর্ষবিন্দু 5 এ যাওয়ার প্রয়োজন নেই, কারণ শীর্ষবিন্দু 2 থেকে এখনে যাওয়া হয়েছে এবং শীর্ষবিন্দু 3 এও যাওয়ার কোন প্রয়োজন নেই।
- এখন মূল অবস্থান থেকে শীর্ষবিন্দুর অবস্থান যখন 2 সেখান থেকে কাজ করা শুরু কর। শীর্ষবিন্দু 4 থেকে কাজ করা শুরু করা যাক। শীর্ষবিন্দু 2 এ ইতোমধ্যেই যাওয়া হয়েছে। শীর্ষবিন্দু 1 এ যাওয়া যাক, এর দূরত্ব 3 এবং এর predecessor এর মান শীর্ষবিন্দু 4 এ নির্ধারণ করার মাধ্যমে।
- শীর্ষবিন্দু 5 এ যাবার পরে, এর আশেপাশে আর কোথাও যাবার প্রয়োজন নেই, কারণ ওগুলোতে ইতোমধ্যেই যাওয়া হয়ে গিয়েছে।
- এখন মূল অবস্থান থেকে শীর্ষবিন্দুর অবস্থান যখন 3 সেখান থেকে কাজ করা শুরু কর। শুধুমাত্র যে শীর্ষবিন্দুটি এরকম হয় সেটা হল শীর্ষবিন্দু 1। এর আশপাশের বিন্দুগুলো, শীর্ষবিন্দু 4 এবং 5 এ ইতোমধ্যেই যাওয়া হয়েছে। কিন্তু শীর্ষবিন্দু 0 নয়। শীর্ষবিন্দু 0 তে যাওয়া যাক, এর দূরত্ব 4 এবং এর predecessor এর মান শীর্ষবিন্দু 1 এ নির্ধারণ করে দেবার মাধ্যমে।
- এখন সেই শীর্ষবিন্দুগুলোতে যাওয়া যাক কে শীর্ষবিন্দুগুলোর দূরত্ব, মূল শীর্ষবিন্দু থেকে 4 ছিল। এটি শুধুমাত্র শীর্ষবিন্দু 0 হবে এবং এর আশপাশের বিন্দুগুলো, শীর্ষবিন্দু 1 এ ইতোমধ্যেই যাওয়া হয়েছে। আমাদের কাজ শেষ!
এখানে লক্ষ্য করলে দেখা যাচ্ছে যে শীর্ষবিন্দু 3 থেকে শীর্ষবিন্দু 7 পর্যন্ত কোন পথ নেই, তাই এটা কখনই শীর্ষবিন্দু 7 এ যাবে না। এর দূরত্ব এবং predecessor এর প্রাথমিক মান থেকে পরিবর্তন হবে না যেটা হল
null।বেশ কিছু প্রশ্ন এখানে এসেছে। একটি হল একটি শীর্ষবিন্দুতে যে ইতোমধ্যেই যাওয়া হয়েছে কিনা তা কীভাবে আমরা বুঝতে পারব। এটা সহজ: একটি শীর্ষবিন্দুর দূরত্ব
null থাকবে যতক্ষণ পর্যন্ত না এখানে যাওয়া হবে, আর এখানে যাওয়া হলে এটা দূরত্বের জন্য একটি সাংখ্যিক মান পাবে। সুতরাং, যখন আমরা একটি শীর্ষবিন্দুর আশপাশে থাকা বিন্দুগুলো পরীক্ষা করব, আমরা তখন শুধুমাত্র সেই বিন্দুগুলোতে যাব যাদের দূরত্ব বর্তমানে null।অন্য যে প্রশ্নটি এখানে রয়েছে সেটি হল কোন শীর্ষবিন্দুগুলোতে ইতোমধ্যেই যাওয়া হয়েছে কিন্তু সেই শীর্ষবিন্দুগুলো থেকে অন্য কোথাও যাওয়া হয়নি সেগুলো কীভাবে বোঝা যাবে। আমরা এখানে একটি সারি ব্যবহার করব, যেটা হল একটি ডাটা কাঠামো যেটা আমাদের কোন একটি জিনিস সংযুক্ত করতে এবং একই সাথে কোন একটি জিনিস সরিয়ে দিতে আমাদের অনুমতি দিবে, যেখান সরিয়ে ফেলা জিনিস সেটিই হলে যে জিনিসটি সারিতে সবচেয়ে বেশি সময় ধরে আছে। এই ব্যবহারটিকে আমরা বলে থাকি ফার্স্ট ইন, ফার্স্ট আউট। একটি সারির তিনটি অপারেশন আছে:
enqueue(obj)সারিতে একটি অবজেক্ট প্রবেশ করে।dequeue()সারিতে যে অবজেক্টটি সবচেয়ে বেশি সময় ধরে অবস্থান করছে সেই অবজেক্টটিকে এটি সরিয়ে দেয়, অবজেক্টটি ফিরিয়ে দেবার মাধ্যমে।isEmpty()trueরিটার্ন করবে যদি সারিটির ভিতরে কোন অবজেক্ট না থাকে এবংfalseরিটার্ন করবে যদি সারিটিতে কমপক্ষে একটি অবজেক্ট থাকে।
যখনই আমরা কোন একটি শীর্ষবিন্দুতে যাব, তখন এটা সারিতে অন্তর্ভুক্ত হয়ে যাবে। একদম শুরুতে, আমরা মূল শীর্ষবিন্দুটি একটি সারিতে অন্তর্ভুক্ত করব কারণ এই শীর্ষবিন্দুটিই হল প্রথম শীর্ষবিন্দু যেটিতে আমরা প্রথম যাব। পরবর্তীতে কোন শীর্ষবিন্দুগুলোতে যাওয়া হবে তার সিদ্ধান্ত নেবার জন্য, আমরা সেই শীর্ষবিন্দুগুলো নির্বাচন করব যে শীর্ষবিন্দুগুলো সারিতে সবচেয়ে বেশি সময় ধরে আছে এবং সারি থেকে সরিয়ে দেওয়া হয়েছে—অন্য কথায় বলতে গেলে,
dequeue() থেকে যে শীর্ষবিন্দুগুলো সরিয়ে দেওয়া হয়েছে সেই শীর্ষবিন্দুগুলো আমরা এখানে ব্যবহার করব। আমাদের লেখচিত্রের উদাহরণে দেওয়া আছে, প্রতিটি ধাপে সারিটি দেখতে এরকম হবে, একই সাথে আগের ভিজুয়ালাইজেশনও এখানে দেখান হয়েছে, সারির বর্তমান অবস্থাসহ:- Initially, the queue contains just vertex 3 with distance 0.
- Dequeue vertex 3, and enqueue vertices 2 and 6, both with distance 1. The queue now contains vertex 2 with distance 1 and vertex 6 with distance 1.
- Dequeue vertex 2, and enqueue vertices 4 and 5, both with distance 2. The queue now contains vertex 6 with distance 1, vertex 4 with distance 2, and vertex 5 with distance 2.
- Dequeue vertex 6, and don't enqueue any vertices. The queue now contains vertex 4 with distance 2 and vertex 5 with distance 2.
- Dequeue vertex 4, and enqueue vertex 1 with distance 3. The queue now contains vertex 5 with distance 2 and vertex 1 with distance 3.
- Dequeue vertex 5, and don't enqueue any vertices. The queue now contains just vertex 1 with distance 3.
- Dequeue vertex 1, and enqueue vertex 0 with distance 4. The queue now contains just vertex 0 with distance 4.
- Dequeue vertex 0, and don't enqueue any vertices. The queue is now empty. Because the queue is empty, breadth-first search terminates.
এখানে লক্ষ্য করলে দেখা যাবে কিছু মুহূর্তে, সারিটি সমান দূরত্বের শীর্ষবিন্দু রাখছে অথবা সেই শীর্ষবিন্দুগুলো অন্তর্ভুক্ত করছে যেগুলোর দূরত্ব হল k এবং একই সাথে সেই সেই শীর্ষবিন্দুগুলো যেগুলোর দূরত্ব হল k, plus, 1। এভাবেই আমরা নিশ্চিত করি যে আমরা দূরত্ব k তে থাকা সবগুলো শীর্ষবিন্দুতে আমরা গিয়েছি এবং এটি নিশ্চিত করতে হবে দূরত্ব k, plus, 1 এ থাকা শীর্ষবিন্দুগুলোতে যাবার আগেই।
এই বিষয়বস্তুটি Dartmouth Computer Science এর প্রফেসর Thomas Cormen এবং Devin Balkcom এর সহযোগিতায় এবং একই সাথে খান একাডেমির কম্পিউটিং শিক্ষাক্রম দলের একসাথে কাজ করার মাধ্যমে তৈরি করা হয়েছে। এই বিষয়বস্তু CC-BY-NC-SA দিয়ে লাইসেন্সকৃত।
আলোচনায় অংশ নিতে চাও?
কোন আলাপচারিতা নেই।