البحث بالعرض أولاً (BFS)
ألقِ حجرًا في بركة فتنتشر التموجات بالتساوي في حلقات. والبحث بالعرض أولاً يستكشف الرسم البياني بالطريقة نفسها: أولاً كل ما يبعد خطوة واحدة عن البداية، ثم كل ما يبعد خطوتين، وهكذا. وهذا الترتيب البسيط هو ما يجعله يجد أقصر المسارات.
الفكرة
الرسم البياني مجموعة من العقد تربطها حواف: أماكن وطرق، وأشخاص وصداقات، ومربعات متاهة والفتحات بينها. ويجيب البحث بالعرض أولاً عن السؤال: إذا بدأت من هنا، فإلى أين أصل، وبكم خطوة على الأقل؟ وهو يحتفظ بطابور من العقد التي لم تُزر بعد. وأخذ العقد من المقدمة وإضافة الجديدة إلى الآخر يعني أن العقد تُعالج بالترتيب الذي اكتُشفت به.
خطوة بخطوة
ضع البداية في الطابور على مسافة 0. خذ العقدة التي في المقدمة. لكل جار لم يُرَ بعد، سجّل مسافته على أنها مسافة العقدة الحالية زائد واحد، وتذكّر العقدة الحالية على أنها الطريق الذي بُلغ منه، وأضفه إلى آخر الطابور. وتخطَّ الجيران الذين رُئوا من قبل. كرّر حتى يفرغ الطابور، أو حتى تبلغ الهدف.
مثال
خذ رسمًا بيانيًا حوافه A–B وA–C وB–D وC–D وC–E وD–F، وابدأ من A. أخذ A من الطابور يجد B وC على المسافة 1. وأخذ B يجد D على المسافة 2. وأخذ C يجد أن D رُئيت من قبل، ويجد E على المسافة 2. وأخذ D يجد F على المسافة 3. ولا تجد E وF شيئًا جديدًا، ويفرغ الطابور. وتتبُّع العقد المحفوظة رجوعًا من F يعطي F ← D ← B ← A، فأقصر مسار من A إلى F هو A → B → D → F، وطوله ثلاث حواف.
لماذا المسافات صحيحة
كل عقدة على المسافة 1 تدخل الطابور قبل أي عقدة على المسافة 2، وكل عقدة على المسافة 2 قبل أي عقدة على المسافة 3، وهكذا، لأن جيران العقدة لا يدخلون الطابور إلا عندما تخرج هي نفسها منه. لذلك فإن أول مسار يبلغ عقدة ما هو مسار فيه أقل عدد من الحواف، ولا يحتاج BFS أبدًا إلى تصحيح مسافة. وتُؤخذ كل عقدة مرة واحدة ويُنظر إلى كل حافة من طرفيها، فيزداد العمل مع عدد العقد مضافًا إليه عدد الحواف.
التاريخ والاستخدامات
وصف Konrad Zuse البحث بالعرض أولاً عام 1945، في عمله على لغته Plankalkül الذي لم يُنشر حتى عام 1972. وأعاد Edward F. Moore اختراعه عام 1959 لإيجاد أقصر طريق للخروج من متاهة، واستخدمه C. Y. Lee عام 1961 لتوجيه الأسلاك على لوحات الدوائر. واليوم يجد أقل عدد من الحركات في الألغاز، ودرجات الانفصال في الشبكات الاجتماعية، والصفحات التي يبلغها زاحف الويب أولاً، وأقرب خانة فارغة في الألعاب. وعندما تكون للحواف أطوال، تعمّمه خوارزمية ديكسترا.
استكشفه بنفسك
افتح التطبيق واضغط «خطوة». تُبرز العقدة التي تجري زيارتها، وتكون العقد المنتظرة في الطابور زرقاء، والعقد التي تمت زيارتها خضراء، ولكلٍّ منها مسافتها. ويظهر الطابور أسفل الرسم البياني، المقدمة أولاً. حوّل النقر إلى «الهدف» واختر عقدة ليتوقف البحث عندها وترى أقصر مسار، أو أنشئ رسمًا بيانيًا جديدًا بعقد وحواف أكثر.
الأسئلة المتداولة
ما التعقيد الزمني لـ BFS؟
O(V + E) لعدد V من العقد (الرؤوس) وعدد E من الحواف: كل عقدة تدخل الطابور وتخرج منه مرة واحدة، وكل حافة تُفحص من طرفيها. ويحتاج إلى ذاكرة إضافية O(V) للطابور والمسافات.
لماذا يستخدم BFS طابورًا؟
لأن مبدأ ما يدخل أولاً يخرج أولاً يُبقي العقد بالترتيب الذي اكتُشفت به، وهو ترتيب مسافاتها. ولو استُخدم مكدس بدلاً منه، لغاص البحث في العمق أولاً: وهذا هو البحث بالعمق أولاً.
هل يجد BFS أقصر المسارات في الرسوم البيانية الموزونة؟
ليس عمومًا: فهو يعدّ الحواف لا أطوالها. للرسوم البيانية الموزونة التي ليس فيها حواف سالبة، استخدم خوارزمية ديكسترا. وإذا كان كل وزن 0 أو 1، فهناك نوع يُسمى 0-1 BFS يؤدي الغرض.
أين يُستخدم BFS؟
في حل الألغاز والمتاهات بأقل عدد من الحركات، وإيجاد أصدقاء الأصدقاء في الشبكات الاجتماعية، وزحف الويب مستوى بعد مستوى، والبث في الشبكات، وكجزء أساسي من خوارزميات أخرى مثل إيجاد التدفق الأعظمي.
هل أنت مستعد لتجربتها؟
افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.
جرّب البحث بالعرض أولاً