لطالما فتنتني طرق Graph Traversal تمامًا. بدءًا من إجراء اتصالات فعالة من نظير إلى نظير إلى العثور على أقرب المطاعم والمقاهي باستخدام نظام تحديد المواقع العالمي (GPS) ، فإن طرق المسح لها مجموعة متنوعة من التطبيقات في سيناريو العالم الحقيقي. في هذه المدونة الخاصة بخوارزمية Breadth-First Search ، سنناقش المنطق الكامن وراء طرق اجتياز الرسم البياني ونستخدم أمثلة لفهم عمل خوارزمية Breadth-First Search.
للحصول على معرفة عميقة بالذكاء الاصطناعي والتعلم الآلي ، يمكنك التسجيل في البث المباشر بواسطة Edureka مع دعم على مدار الساعة طوال أيام الأسبوع وإمكانية الوصول مدى الحياة.
إليك قائمة بالموضوعات التي سيتم طرحها مغطى في هذه المدونة:
- مقدمة لمسح الرسم البياني
- ما هو اتساع البحث؟
- فهم خوارزمية Breadth-First Search مع مثال
- الشفرة الكاذبة لخوارزمية بحث النطاق الأول
- تطبيقات اتساع البحث الأول
مقدمة لمسح الرسم البياني
تسمى عملية زيارة الرسم البياني واستكشافه للمعالجة اجتياز الرسم البياني. لكي نكون أكثر تحديدًا ، يتعلق الأمر بزيارة واستكشاف كل رأس وحافة في رسم بياني بحيث يتم استكشاف جميع القمم مرة واحدة بالضبط.
هذا يبدو بسيطا! لكن هناك مشكلة.
هناك العديد من تقنيات اجتياز الرسم البياني مثل بحث Breadth-First Search و Depth First Search وما إلى ذلك. التحدي هو استخدام الرسم البياني تقنية المسح الأكثر ملاءمة لحل مشكلة معينة. هذا يقودنا إلى تقنية Breadth-First Search.
ما هي خوارزمية 'اتساع أول بحث'؟
تعد خوارزمية Breadth-First Search تقنية اجتياز الرسم البياني ، حيث تحدد عقدة أولية عشوائية (المصدر أو العقدة الجذرية) وتبدأ في اجتياز طبقة الرسم البياني بطريقة يمكن من خلالها زيارة واستكشاف جميع العقد والعقد الفرعية التابعة لها.
قبل أن ننتقل إلى أبعد من ذلك ونفهم 'عرض النطاق أولاً' بمثال ، دعنا نتعرف على مصطلحين مهمين يتعلقان بمسيرة الرسم البياني:
- زيارة العقدة: تمامًا كما يوحي الاسم ، تعني زيارة العقدة زيارة العقدة أو تحديدها.
- استكشاف عقدة: استكشاف العقد المجاورة (العقد الفرعية) للعقدة المحددة.
راجع الشكل أعلاه لفهم هذا بشكل أفضل.
فهم خوارزمية 'اتساع البحث أولاً' مع مثال
بيانات تدفق التحكم في جافا
تتبع خوارزمية Breadth-First Search نهجًا بسيطًا يستند إلى المستوى لحل مشكلة ما. ضع في اعتبارك الشجرة الثنائية أدناه (وهي رسم بياني). هدفنا هو اجتياز الرسم البياني باستخدام خوارزمية Breadth-First Search.
قبل أن نبدأ ، يجب أن تكون على دراية بهيكل البيانات الرئيسي المتضمن في خوارزمية Breadth-First Search.
قائمة الانتظار هي بنية بيانات مجردة تتبع منهجية First-In-First-Out (سيتم الوصول إلى البيانات المدرجة أولاً أولاً). إنه مفتوح من كلا الطرفين ، حيث يتم استخدام أحد الطرفين دائمًا لإدخال البيانات (قائمة الانتظار) والآخر يستخدم لإزالة البيانات (dequeue).
دعنا الآن نلقي نظرة على الخطوات المتبعة في اجتياز رسم بياني باستخدام بحث Breadth-First:
الخطوة 1: خذ قائمة انتظار فارغة.
الخطوة 2: حدد عقدة البداية (زيارة عقدة) وأدخلها في قائمة الانتظار.
الخطوه 3: بشرط ألا تكون قائمة الانتظار فارغة ، قم باستخراج العقدة من قائمة الانتظار وأدخل العقد التابعة لها (استكشاف عقدة) في قائمة الانتظار.
الخطوة الرابعة: اطبع العقدة المستخرجة.
لا تقلق إذا كنت مرتبكًا ، فسنفهم ذلك بمثال.
ألق نظرة على الرسم البياني أدناه ، وسوف نستخدم خوارزمية Breadth-First Search لاجتياز الرسم البياني.
في حالتنا ، سنقوم بتعيين العقدة 'a' كعقدة جذر ونبدأ في الانتقال لأسفل واتباع الخطوات المذكورة أعلاه.
توضح الصورة أعلاه العملية الشاملة لخوارزمية Breadth-First Search. اسمحوا لي أن أشرح هذا بمزيد من العمق.
- قم بتعيين 'a' كعقدة جذر وأدخلها في قائمة الانتظار.
- استخرج العقدة 'أ' من قائمة الانتظار وأدخل العقد الفرعية لـ 'أ' ، أي 'ب' و 'ج'.
- طباعة العقدة 'أ'.
- قائمة الانتظار ليست فارغة وتحتوي على العقدة 'b' و 'c'. نظرًا لأن 'b' هي العقدة الأولى في قائمة الانتظار ، فلنستخرجها وأدخل العقد الفرعية لـ 'b' ، أي العقدة 'd' و 'e'.
- كرر هذه الخطوات حتى تصبح قائمة الانتظار فارغة. لاحظ أنه لا ينبغي إضافة العقد التي تمت زيارتها بالفعل إلى قائمة الانتظار مرة أخرى.
دعونا الآن نلقي نظرة على الشفرة الزائفة لخوارزمية Breadth-First Search.
الشفرة الكاذبة لخوارزمية بحث النطاق الأول
إليك الشفرة الزائفة لتنفيذ خوارزمية 'عرض النطاق الأول':
المدخلات: كعقدة المصدر BFS (G ، s) دع Q يكون في قائمة الانتظار. Q.enqueue (s) علامات كما تمت زيارتها بينما (Q ليست فارغة) v = Q.dequeue () لجميع الجيران w of v في الرسم البياني G إذا لم تتم زيارة Q.enqueue (w) علامة w أثناء الزيارة
في الكود أعلاه ، يتم تنفيذ الخطوات التالية:
- (G ، s) مدخلات ، هنا G هو الرسم البياني و s هي عقدة الجذر
- يتم إنشاء قائمة انتظار 'Q' وتهيئتها باستخدام عقدة المصدر 's'
- تم وضع علامة على جميع العقد الفرعية لـ 's'
- استخراج 's' من قائمة الانتظار وزيارة العقد الفرعية
- معالجة جميع العقد الفرعية لـ v
- يخزن w (العقد الفرعية) في Q لمزيد من زيارة العقد الفرعية
- استمر حتى 'Q' فارغة
قبل أن ننهي المدونة ، دعونا نلقي نظرة على بعض تطبيقات خوارزمية Breadth-First Search.
تطبيقات لوغاريتم اتساع البحث
البحث ذو النطاق الأول هو طريقة مسح بسيطة للرسم البياني تحتوي على مجموعة مذهلة من التطبيقات. فيما يلي بعض الطرق الشيقة التي يتم من خلالها استخدام بحث Bread-First:
الزواحف في محركات البحث: Breadth-First Search هو أحد الخوارزميات الرئيسية المستخدمة لفهرسة صفحات الويب. تبدأ الخوارزمية في الانتقال من الصفحة المصدر وتتبع جميع الروابط المرتبطة بالصفحة. هنا سيتم اعتبار كل صفحة ويب كعقدة في الرسم البياني.
أنظمة الملاحة GPS: يعد Breadth-First Search أحد أفضل الخوارزميات المستخدمة للعثور على المواقع المجاورة باستخدام نظام GPS.
ابحث عن أقصر مسار وأدنى شجرة امتداد لرسم بياني غير مرجح: عندما يتعلق الأمر برسم بياني غير مرجح ، فإن حساب أقصر مسار يكون أمرًا بسيطًا نظرًا لأن الفكرة وراء أقصر مسار هي اختيار مسار بأقل عدد من الحواف. يمكن أن يسمح Breadth-First Search بهذا عن طريق اجتياز الحد الأدنى من عدد العقد بدءًا من العقدة المصدر. وبالمثل ، بالنسبة للشجرة الممتدة ، يمكننا استخدام أي من طريقتين ، البحث الأول أو طريقة اجتياز العمق أولاً للعثور على شجرة ممتدة.
البث: تستفيد الشبكات مما نسميه حزم للاتصال. تتبع هذه الحزم طريقة اجتياز للوصول إلى عقد الشبكات المختلفة. من أكثر طرق الاجتياز شيوعًا البحث 'Breadth-First Search'. يتم استخدامه كخوارزمية تُستخدم لتوصيل حزم البث عبر جميع العقد في الشبكة.
شبكات نظير إلى نظير: يمكن استخدام بحث Breadth-First كطريقة اجتياز للعثور على جميع العقد المجاورة في شبكة نظير إلى نظير. على سبيل المثال ، يستخدم BitTorrent بحث Breadth-First للتواصل من نظير إلى نظير.
لذلك كان هذا كل شيء عن عمل خوارزمية Breadth-First Search. الآن بعد أن عرفت كيفية اجتياز الرسوم البيانية ، أنا متأكد من أنك مهتم بمعرفة المزيد. إليك بعض المدونات ذات الصلة لإبقائك مهتمًا:
بهذا نصل إلى نهاية هذه المدونة. إذا كانت لديك أي استفسارات بخصوص هذا الموضوع ، فيرجى ترك تعليق أدناه وسنعاود الاتصال بك.
إذا كنت ترغب في التسجيل في دورة كاملة حول الذكاء الاصطناعي والتعلم الآلي ، فإن Edureka لديها برنامج منسق خصيصًا هذا سيجعلك بارعًا في تقنيات مثل التعلم الخاضع للإشراف والتعلم غير الخاضع للإشراف ومعالجة اللغة الطبيعية. ويشمل التدريب على أحدث التطورات والأساليب التقنية في الذكاء الاصطناعي والتعلم الآلي مثل التعلم العميق والنماذج الرسومية والتعلم المعزز.