আপনার প্রথম প্রসারিত অনুসন্ধান অ্যালগরিদম সম্পর্কে জানতে হবে



ব্রেডথ-ফার্স্ট সার্চ অ্যালগরিদমের এই ব্লগে আমরা গ্রাফ ট্র্যাভারসাল পদ্ধতিগুলির পিছনে যুক্তিটি আলোচনা করব এবং এর কার্যকারিতা বুঝতে পারি।

গ্রাফ ট্র্যাভারসাল পদ্ধতিগুলি আমাকে সর্বদা বেশ মুগ্ধ করে। জিপিএস ব্যবহার করে নিকটতম রেস্তোঁরা ও ক্যাফেগুলি সন্ধানের কার্যকর সমকক্ষ থেকে পিয়ার যোগাযোগের কাজ করা থেকে শুরু করে ট্র্যাভার্সাল পদ্ধতিতে বাস্তব-বিশ্বের দৃশ্যে বিভিন্ন ধরণের অ্যাপ্লিকেশন রয়েছে। ব্রাথ-ফার্স্ট অনুসন্ধান অ্যালগরিদমের এই ব্লগে আমরা গ্রাফ ট্র্যাভারসাল পদ্ধতিগুলির পিছনে যুক্তিটি আলোচনা করব এবং ব্রেথ-ফার্স্ট অনুসন্ধান অ্যালগরিদমের কাজ বোঝার জন্য উদাহরণগুলি ব্যবহার করব।

কৃত্রিম বুদ্ধিমত্তা এবং মেশিন লার্নিংয়ের গভীর-জ্ঞান পেতে, আপনি লাইভের জন্য তালিকাভুক্ত করতে পারেন 24/7 সমর্থন এবং আজীবন অ্যাক্সেস সহ এডুরেকা দ্বারা।





এখানে বিষয়গুলির তালিকার তালিকা রয়েছে এই ব্লগে আচ্ছাদিত:

  1. গ্রাফ ট্র্যাভারসাল পরিচিতি
  2. প্রস্থ-প্রথম অনুসন্ধান কী?
  3. একটি উদাহরণ সহ চূড়ান্ত-প্রথম অনুসন্ধানের অ্যালগরিদম বোঝা
  4. প্রস্থ-প্রথম অনুসন্ধান অ্যালগরিদম সিউডোকোড
  5. প্রস্থ-প্রথম অনুসন্ধানের অ্যাপ্লিকেশন

গ্রাফ ট্র্যাভারসাল পরিচিতি

প্রসেসিংয়ের জন্য কোনও গ্রাফ পরিদর্শন ও অন্বেষণের প্রক্রিয়াটিকে গ্রাফ ট্র্যাভারসাল বলে। আরও সুনির্দিষ্ট হওয়ার জন্য এটি প্রতিটি গ্রাফিক্স এবং প্রান্তটি একটি গ্রাফের মধ্যে ঘুরে দেখার এবং অন্বেষণ করার মতো যা সমস্ত শীর্ষকোষ একবারে অনুসন্ধান করা হয়।



এটাই সহজ! কিন্তু একটি ধরা আছে।

বেশ কয়েকটি গ্রাফ ট্র্যাভারসাল কৌশল রয়েছে যেমন ব্রেথথ ফার্স্ট অনুসন্ধান, গভীরতা প্রথম অনুসন্ধান এবং আরও অনেক কিছু। চ্যালেঞ্জ হ'ল গ্রাফ ব্যবহার করা ট্র্যাভার্সাল কৌশল যা কোনও নির্দিষ্ট সমস্যা সমাধানের জন্য সবচেয়ে উপযুক্ত। এটি আমাদের প্রশস্ত-প্রথম অনুসন্ধান কৌশল এনেছে।

প্রস্থ-প্রথম অনুসন্ধান অ্যালগরিদম কী?

প্রস্থ-প্রথম অনুসন্ধান অ্যালগরিদম হল একটি গ্রাফ ট্র্যাভার্সিং কৌশল, যেখানে আপনি একটি এলোমেলো প্রাথমিক নোড (উত্স বা মূল নোড) নির্বাচন করেন এবং গ্রাফ স্তর অনুসারে এমনভাবে ট্র্যাভার করা শুরু করুন যাতে সমস্ত নোড এবং তাদের সম্পর্কিত শিশু নোডগুলি পরিদর্শন ও অন্বেষণ করা হয়।



ম্যাথ.এবস জবাতে কি করে?

আমরা আরও সরানোর আগে এবং উদাহরণের সাথে ব্রেডথ-ফার্স্ট অনুসন্ধান বোঝার আগে, গ্রাফ ট্র্যাভারসাল সম্পর্কিত দুটি গুরুত্বপূর্ণ শর্তের সাথে পরিচিত হই:

গ্রাফ ট্র্যাভারসাল - প্রস্থের প্রথম অনুসন্ধানের অ্যালগরিদম - এডুরেকা

  1. একটি নোড পরিদর্শন: নামটি যেমন প্রস্তাব দেয় ঠিক তেমন কোনও নোডের পরিদর্শন করার অর্থ একটি নোডে দেখা বা নির্বাচন করা।
  2. একটি নোড অন্বেষণ: অন্বেষণ নির্বাচিত নোডের সংলগ্ন নোড (শিশু নোড)।

এটি আরও ভালভাবে বুঝতে উপরের চিত্রটি দেখুন।

একটি উদাহরণ সহ চূড়ান্ত-প্রথম অনুসন্ধান অ্যালগরিদম বোঝা

প্রস্থ-প্রথম অনুসন্ধান অ্যালগরিদম কোনও সমস্যা সমাধানের জন্য একটি সহজ, স্তর-ভিত্তিক পদ্ধতির অনুসরণ করে। নীচের বাইনারি গাছ বিবেচনা করুন (যা একটি গ্রাফ)। আমাদের লক্ষ্য ব্রেডথ-ফার্স্ট অনুসন্ধান অ্যালগরিদম ব্যবহার করে গ্রাফটি অতিক্রম করা।

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

একটি সারি হ'ল একটি বিমূর্ত তথ্য কাঠামো যা ফার্স্ট-ইন-ফার্স্ট-আউট পদ্ধতি অনুসরণ করে (প্রথমে প্রবেশ করা ডেটা প্রথমে অ্যাক্সেস করা হবে)। এটি উভয় প্রান্তে খোলা রয়েছে, যেখানে এক প্রান্তটি সর্বদা ডেটা সন্নিবেশ করানোর জন্য ব্যবহৃত হয় (এনকুই) এবং অন্যটি ডেটা অপসারণ করতে (ডিকুই) ব্যবহার করা হয়।

এবার আসুন ব্রাডথ-ফার্স্ট অনুসন্ধান ব্যবহার করে কোনও গ্রাফ ট্র্যাভারে জড়িত পদক্ষেপগুলি একবার দেখে নেওয়া যাক:

ধাপ 1: একটি খালি সারি নিন।

ধাপ ২: একটি প্রারম্ভিক নোড (কোনও নোড পরিদর্শন করা) নির্বাচন করুন এবং এটি কাতারে প্রবেশ করান।

ধাপ 3: প্রদত্ত শর্ত যে সারিটি খালি নয়, কুই থেকে নোডটি বের করুন এবং তার চাইল্ড নোডগুলি (একটি নোড অন্বেষণ করে) কাতারে প্রবেশ করুন।

পদক্ষেপ 4: নিষ্ক্রিয় নোড মুদ্রণ করুন।

আপনি যদি বিভ্রান্ত হন তবে চিন্তা করবেন না, আমরা এটি উদাহরণ দিয়ে বুঝতে পারি।

নতুনদের জন্য ইনফরম্যাটিকা টিউটোরিয়াল পিডিএফ

নীচের গ্রাফটি একবার দেখুন, আমরা গ্রাফটি পেরিয়ে যাওয়ার জন্য প্রস্থ-প্রথম অনুসন্ধান অ্যালগরিদম ব্যবহার করব।

আমাদের ক্ষেত্রে, আমরা নোডকে ‘এ’ রুট নোড হিসাবে অর্পণ করব এবং নীচের দিকে যাত্রা শুরু করব এবং উপরে বর্ণিত পদক্ষেপগুলি অনুসরণ করব।

উপরের চিত্রটি প্রস্থ-প্রথম অনুসন্ধান অ্যালগরিদমের শেষ থেকে শেষের প্রক্রিয়া চিত্রিত করে। আমাকে আরও গভীরতার সাথে এটি ব্যাখ্যা করুন।

  1. রুট নোড হিসাবে ‘ক’ নির্ধারণ করুন এবং এটিকে কাতারে প্রবেশ করুন।
  2. সারি থেকে নোড ‘এ’ বের করুন এবং ‘ক’, যথা, ‘বি’ এবং ‘সি’ এর চাইল্ড নোড .োকান।
  3. প্রিন্ট নোড ‘এ’।
  4. সারিটি খালি নয় এবং নোডে রয়েছে ‘বি’ এবং ‘সি’। যেহেতু ‘বি’ হ'ল প্রথম সারির নোড তাই আসুন এটি বের করুন এবং ‘বি’, অর্থাত্ নোড ‘ডি’ এবং ‘ই’ এর চাইল্ড নোডগুলি sertোকান।
  5. সারিটি খালি না হওয়া পর্যন্ত এই পদক্ষেপগুলি পুনরাবৃত্তি করুন। মনে রাখবেন যে নোডগুলি ইতিমধ্যে পরিদর্শন করা হয়েছে সেগুলি কাতারে যুক্ত করা উচিত নয় আবার।

এখন আসুন ব্রাডথ-ফার্স্ট সার্চ অ্যালগরিদমের সিডোকোডটি দেখুন।

প্রস্থ-প্রথম অনুসন্ধান অ্যালগরিদম সিউডোকোড

প্রস্থ-প্রথম অনুসন্ধান অ্যালগরিদম বাস্তবায়নের জন্য সিউডোকোডটি এখানে রয়েছে:

ইনপুট: s উত্স নোড হিসাবে বিএফএস (জি, গুলি) কিউ সারি হতে দিন। Q.enqueue (s) চিহ্নটি পরিদর্শনকালে (Q খালি নয়) v = Q.dequeue () গ্রাফ জি-তে সমস্ত প্রতিবেশী W এর জন্য যদি W. দেখা না গিয়ে Q.enqueue (w) চিহ্ন ডাব্লু না দেখায়

উপরের কোডে, নিম্নলিখিত পদক্ষেপগুলি কার্যকর করা হয়েছে:

  1. (জি, গুলি) ইনপুট, এখানে জি গ্রাফ এবং এস হ'ল মূল নোড
  2. সোর্স নোড ‘এস’ দিয়ে একটি সারি ‘কিউ’ তৈরি এবং সূচনা করা হয়েছে
  3. ‘S’ এর সমস্ত শিশু নোড চিহ্নিত রয়েছে
  4. সারি থেকে ‘গুলি’ বের করুন এবং চাইল্ড নোডগুলি দেখুন
  5. ভি এর সমস্ত শিশু নোড প্রক্রিয়া করুন
  6. এর চাইল্ড নোডগুলি আরও দেখার জন্য কিউতে ডাব্লু (শিশু নোড) সঞ্চয় করে Stores
  7. ‘কিউ’ না হওয়া পর্যন্ত চালিয়ে যান খালি

আমরা ব্লগটি গুছিয়ে নেওয়ার আগে, আসুন প্রথম প্রারম্ভিক অনুসন্ধান অ্যালগরিদমের কিছু অ্যাপ্লিকেশন দেখে নেওয়া যাক।

প্রস্থ-প্রথম অনুসন্ধান অ্যালগরিদমের অ্যাপ্লিকেশন

প্রস্থ-প্রথম অনুসন্ধান হ'ল একটি সাধারণ গ্রাফ ট্র্যাভার্সাল পদ্ধতি যা এতে আশ্চর্যের সাথে বিভিন্ন অ্যাপ্লিকেশন রয়েছে। এখানে কয়েকটি আকর্ষণীয় উপায়ে যা রুটি-প্রথম অনুসন্ধান ব্যবহৃত হচ্ছে:

অনুসন্ধান ইঞ্জিনগুলিতে ক্রলারগুলি: ওয়েব পৃষ্ঠাগুলি সূচীকরণের জন্য ব্যবহৃত মূল আলগোরিদিমগুলির মধ্যে একটি: প্রস্থ-প্রথম অনুসন্ধান Search অ্যালগরিদম উত্স পৃষ্ঠা থেকে ট্র্যাভার করতে শুরু করে এবং পৃষ্ঠার সাথে সম্পর্কিত সমস্ত লিঙ্ক অনুসরণ করে। এখানে প্রতিটি ওয়েব পৃষ্ঠা গ্রাফের নোড হিসাবে বিবেচিত হবে।

জিপিএস নেভিগেশন সিস্টেমগুলি: জিপিএস সিস্টেমটি ব্যবহার করে প্রতিবেশী অবস্থানগুলি সন্ধান করতে ব্যবহৃত সেরা অ্যালগরিদমগুলির মধ্যে একটি: প্রস্থ-প্রথম অনুসন্ধান।

অপ্রকাশিত গ্রাফের জন্য সবচেয়ে সংক্ষিপ্ত পথ এবং সর্বনিম্ন স্প্যানিং ট্রিটি সন্ধান করুন: যখন এটি একটি অপ্রকাশিত গ্রাফের কথা আসে, সবচেয়ে সংক্ষিপ্ত পাথ গণনা করা বেশ সহজ কারণ সবচেয়ে সংক্ষিপ্ততম পাথের পিছনে ধারণাটি সর্বনিম্ন সংখ্যার কিনার সহ একটি পথ বেছে নেওয়া হয়। প্রশস্ত-প্রথম অনুসন্ধান উত্স নোড থেকে শুরু করে ন্যূনতম সংখ্যক নোডকে অনুসরণ করে এটিকে মঞ্জুরি দিতে পারে। একইভাবে, বিস্তৃত গাছের জন্য, আমরা একটি বিস্তৃত গাছ খুঁজে পেতে দুটি, ব্রেথথ ফার্স্ট অনুসন্ধান বা গভীরতা-প্রথম ট্র্যাভারসাল পদ্ধতি ব্যবহার করতে পারি।

সম্প্রচার: নেটওয়ার্কিং আমরা যোগাযোগের জন্য প্যাকেট হিসাবে যাকে বলি তা ব্যবহার করে। এই প্যাকেটগুলি বিভিন্ন নেটওয়ার্কিং নোডগুলিতে পৌঁছানোর জন্য একটি ট্র্যাভারসাল পদ্ধতি অনুসরণ করে। সর্বাধিক ব্যবহৃত ট্র্যাভারসাল পদ্ধতিগুলির মধ্যে একটি হ'ল প্রশস্ত-প্রথম অনুসন্ধান। এটি একটি অ্যালগরিদম হিসাবে ব্যবহৃত হচ্ছে যা কোনও নেটওয়ার্কের সমস্ত নোড জুড়ে সম্প্রচারিত প্যাকেটগুলি যোগাযোগ করার জন্য ব্যবহৃত হয়।

পিয়ার টু পিয়ার নেটওয়ার্কিং: পিয়ার টু পিয়ার নেটওয়ার্কে প্রতিবেশী সমস্ত নোডগুলি খুঁজে পেতে ট্র্যাভার্সাল পদ্ধতি হিসাবে ব্রেডথ-ফার্স্ট অনুসন্ধান ব্যবহার করা যেতে পারে। উদাহরণস্বরূপ, বিট টরেন্ট পিয়ার থেকে পিয়ার যোগাযোগের জন্য ব্রেডথ-ফার্স্ট অনুসন্ধান ব্যবহার করে।

সুতরাং এটি ছিল প্রশস্ত-প্রথম অনুসন্ধানের অ্যালগরিদমের কাজ সম্পর্কে। গ্রাফগুলি কীভাবে ট্র্যাভার করতে হয় তা আপনি জানেন তবে আমি নিশ্চিত যে আপনি আরও জানতে আগ্রহী। আপনাকে আগ্রহী রাখতে এখানে কয়েকটি প্রাসঙ্গিক ব্লগ রয়েছে:

  1. উদাহরণ সহ মার্কোভ চেইনের পরিচয় - পাইথনের সাথে মার্কভ চেইন

এটির সাথে আমরা এই ব্লগের শেষে এসেছি। এই বিষয়ে আপনার যদি কোনও প্রশ্ন থাকে তবে নীচে একটি মন্তব্য করুন এবং আমরা আপনার কাছে ফিরে যাব।

আপনি যদি কৃত্রিম বুদ্ধিমত্তা এবং মেশিন লার্নিংয়ের একটি সম্পূর্ণ কোর্সের জন্য ভর্তি হতে চান, তবে এডুরেকা একটি বিশেষভাবে সজ্জিত যা আপনাকে তদারকি করা শেখা, আনসার্পাইজড লার্নিং এবং প্রাকৃতিক ভাষা প্রক্রিয়াজাতকরণের মতো কৌশলগুলিতে দক্ষ করে তুলবে। এর মধ্যে কৃত্রিম বুদ্ধিমত্তা এবং মেশিন লার্নিং যেমন ডিপ লার্নিং, গ্রাফিকাল মডেলস এবং রিইনফোর্সমেন্ট লার্নিংয়ের সর্বশেষ অগ্রগতি এবং প্রযুক্তিগত পদ্ধতির উপর প্রশিক্ষণ অন্তর্ভুক্ত রয়েছে।