عرب سايكلوجي

خوارزمية البحث بالاتساع: استكشاف منهجي لكل الاحتمالات

المحتويات:

المجالات التخصصية الرئيسية: علوم الحاسوب، نظرية المخططات، الذكاء الاصطناعي

1. التعريف الجوهري والمبادئ الأساسية

خوارزمية البحث أولاً بالاتساع (BFS) هي طريقة منهجية لاجتياز أو البحث في عقد (رؤوس) هيكل بيانات شجري أو مخطط (Graph). تُعد هذه الخوارزمية واحدة من أبسط وأهم خوارزميات البحث في نظرية المخططات، حيث تضمن استكشاف جميع الرؤوس المتاحة في المخطط بطريقة منظمة للغاية. يتميز منهج BFS بأنه يبدأ عند عقدة مصدر محددة (أو جذر) ثم يستكشف جميع العقد المجاورة لها مباشرة (المستوى الأول)، قبل الانتقال لاستكشاف العقد المجاورة لتلك العقد (المستوى الثاني)، وهكذا دواليك. بمعنى آخر، تنتشر عملية البحث “عرضياً” أو “اتساعياً” بعيدًا عن العقدة المصدر تدريجيًا، مما يضمن زيارة جميع الرؤوس على مسافة أقصر مسافة متساوية قبل الانتقال إلى الرؤوس الأبعد.

يتمثل المبدأ الأساسي الذي يحكم عمل BFS في استخدام بنية بيانات مساعدة تُعرف باسم الطابور (Queue)، والتي تعمل وفق مبدأ “الداخل أولاً يخرج أولاً” (FIFO). هذه البنية هي ما يفرض الترتيب الاتساعي للاستكشاف؛ فكلما تمت زيارة عقدة، تُضاف جميع جيرانها غير المزارين إلى نهاية الطابور. وعندما يحين دورها، تُزال العقدة من مقدمة الطابور ليتم استكشاف جيرانها بدورهم. هذه الآلية تضمن أن الرؤوس التي تقع على مسافة أقصر من المصدر يتم معالجتها دائمًا قبل الرؤوس التي تقع على مسافة أطول، مما يجعل BFS خيارًا مثاليًا لإيجاد أقصر مسار (Shortest Path) في المخططات غير الموزونة (Unweighted Graphs)، حيث تُعتبر تكلفة الانتقال بين أي عقدتين متجاورتين متساوية (وحدة واحدة).

إن الطريقة التي تنظم بها BFS بحثها تضمن أن الخوارزمية كاملة (Complete)، أي أنها ستجد حلاً إذا كان موجودًا في المخطط. علاوة على ذلك، في سياق المخططات غير الموزونة، فإنها مثالية (Optimal)، مما يعني أنها تضمن العثور على المسار الأقصر من حيث عدد الحواف. هذا الترتيب المنهجي للاستكشاف يميزها جوهريًا عن خوارزميات البحث الأخرى، مثل البحث أولاً بالعمق (DFS)، التي تستخدم بنية المكدس (Stack) وتميل إلى التعمق في فرع واحد قبل استكشاف الأفرع الأخرى. تعود أهمية BFS إلى بساطتها الرياضية وكفاءتها العالية في حل مجموعة واسعة من المشكلات المتعلقة بالاتصال والمسافات في الشبكات.

2. التطور التاريخي والسياق الرياضي

على الرغم من أن المفاهيم الأساسية وراء البحث أولاً بالاتساع قد تكون ضمنية في العديد من الأساليب الرياضية والمنطقية القديمة، إلا أن أول وصف رسمي وموثق للخوارزمية جاء في سياق حل مشكلات المتاهة والرسم البياني في منتصف القرن العشرين. غالبًا ما يُنسب الفضل إلى عالم الحاسوب كوروش إيزو (Kourosh Ezhu) في عام 1945 لاستخدام خوارزمية مماثلة في سياق البحث في المتاهات، لكن الأوصاف الرياضية التي وضعت الأساس الحديث للخوارزمية طُورت لاحقًا.

تم تقديم وصف واضح ودقيق لخوارزمية BFS من قبل عالم الرياضيات وعلوم الحاسوب إدوارد فورست (Edward Forrest) في ستينيات القرن الماضي، حيث تم توظيفها بشكل خاص في تحليل وتصنيف هياكل المخططات. مع التطور السريع لعلوم الحاسوب وبنيات البيانات، أصبحت BFS أداة أساسية في دراسة نظرية المخططات (Graph Theory)، التي توفر الإطار الرياضي اللازم لتمثيل العلاقات المعقدة بين الكيانات. إن السياق الرياضي لـ BFS يرتكز على مفاهيم الاتصال (Connectivity) وقابلية الوصول (Reachability)، حيث تحدد الخوارزمية بفعالية مجموعة الرؤوس التي يمكن الوصول إليها من نقطة البداية.

في سياق الذكاء الاصطناعي المبكر، كانت BFS تُستخدم كإحدى استراتيجيات البحث غير المطلعة (Uninformed Search)، حيث لا تستخدم معلومات إرشادية (Heuristics) لتوجيه البحث، بل تعتمد فقط على ترتيب منظم. هذا الاستخدام التاريخي يوضح كيف أصبحت BFS أساسًا لبناء خوارزميات بحث أكثر تعقيدًا وتوجيهًا لاحقًا، مثل خوارزمية A*، التي تجمع بين منهجية BFS (لضمان المسار الأقصر) والمعلومات الإرشادية (لتحسين الكفاءة). وبالتالي، فإن BFS ليست مجرد خوارزمية للرسم البياني، بل هي حجر الزاوية في فهم كيفية استكشاف فضاءات الحالة بشكل فعال ومنهجي.

3. منهجية عمل الخوارزمية

تبدأ عملية تنفيذ خوارزمية البحث أولاً بالاتساع بتحديد عقدة البداية (Start Node) وتعيينها كـ مُزارة (Visited) لمنع الوقوع في حلقات لا نهائية (Cycles) داخل المخطط. يتم بعد ذلك إضافة عقدة البداية إلى الطابور (Queue). يظل البحث مستمرًا طالما أن الطابور ليس فارغًا. في كل خطوة تكرارية، تقوم الخوارزمية بسحب (Dequeue) العقدة الموجودة في مقدمة الطابور، والمعروفة بالعقدة الحالية.

بمجرد استخراج العقدة الحالية، تبدأ الخوارزمية في فحص جميع الجيران (Neighbors) لهذه العقدة. لكل جار يتم فحصه، هناك شرطان يجب التحقق منهما: أولاً، هل هذا الجار هو العقدة الهدف (إذا كان البحث يسعى لهدف معين)؟ وثانيًا، هل تم زيارة هذا الجار بالفعل؟ إذا لم يتم زيارة الجار، فإنه يُضاف إلى قائمة “المزارة” ويُدرج في نهاية الطابور. هذا الإجراء يضمن أن جميع الرؤوس الواقعة على نفس المستوى من المصدر ستتم إضافتها إلى الطابور ومعالجتها بالترتيب قبل أن تبدأ الخوارزمية في معالجة الرؤوس في المستوى الأعمق التالي.

يُمكن تلخيص الخطوات المنهجية لـ BFS باستخدام القائمة المرتبة التالية، التي تضمن التنفيذ الصحيح والفعال:

  1. التهيئة: إنشاء طابور فارغ وقائمة (أو مجموعة) لتتبع الرؤوس المُزارة.
  2. البدء: إضافة العقدة المصدر إلى الطابور وتحديدها كمُزارة.
  3. التكرار: طالما أن الطابور غير فارغ، استخرج العقدة الأولى منه (V).
  4. التوسع: فحص جميع الجيران (W) للعقدة المستخرجة (V).
  5. الزيارة والإضافة: إذا لم تتم زيارة الجار (W) من قبل، قم بتحديده كمُزار وإضافته إلى نهاية الطابور.
  6. الإنهاء: تتوقف الخوارزمية عندما يصبح الطابور فارغًا (مما يعني زيارة جميع الرؤوس التي يمكن الوصول إليها) أو عندما يتم العثور على العقدة الهدف.

إن الاستخدام الدقيق للطابور هو العنصر الحاسم في الحفاظ على خاصية البحث أولاً بالاتساع. إذا تم استبدال الطابور بالمكدس، ستتحول الخوارزمية إلى بحث أولاً بالعمق (DFS). هذه المنهجية تضمن أن أي مسار يتم اكتشافه لأول مرة إلى عقدة معينة هو بالضرورة المسار الأقصر في المخططات غير الموزونة، لأن BFS تصل إلى العقد بالترتيب التصاعدي لمسافاتها عن المصدر.

4. تعقيد الوقت والمساحة

يُعد تحليل تعقيد خوارزمية BFS أمرًا حيويًا لفهم كفاءتها في التعامل مع المخططات الكبيرة. يتم قياس التعقيد عادةً بدلالة عدد الرؤوس (V) وعدد الحواف (E) في المخطط.

تعقيد الوقت (Time Complexity): يعتمد تعقيد الوقت لـ BFS على كيفية تمثيل المخطط. إذا تم استخدام قائمة الجوار (Adjacency List)، فإن كل رأس يتم إضافته إلى الطابور مرة واحدة فقط ويتم إخراجه مرة واحدة فقط، مما يستغرق وقتًا قدره O(|V|). وعندما تتم معالجة رأس معين، فإننا نتفحص جميع حوافه المجاورة. وبما أن كل حافة يتم فحصها مرتين على الأكثر (مرة من كل طرف)، فإن فحص جميع الحواف يستغرق وقتًا قدره O(|E|). وبالتالي، فإن تعقيد الوقت الكلي لـ BFS باستخدام قائمة الجوار هو O(|V| + |E|). هذا التعقيد خطي، مما يجعل BFS فعالة للغاية وتُعتبر الأفضل من الناحية النظرية لمعظم تطبيقات اجتياز المخططات.

أما إذا تم تمثيل المخطط باستخدام مصفوفة الجوار (Adjacency Matrix)، فإن عملية تحديد جيران رأس معين تتطلب فحص جميع الرؤوس الأخرى، مما يجعل تكلفة فحص الجيران O(|V|) لكل رأس. وبما أن هناك |V| من الرؤوس، يصبح التعقيد الكلي في هذه الحالة O(|V|²)، وهو أقل كفاءة بكثير من التمثيل بقائمة الجوار عندما تكون المخططات متفرقة (Sparse). لذلك، يُفضل دائمًا استخدام قائمة الجوار عند تطبيق BFS لضمان الأداء الأمثل.

تعقيد المساحة (Space Complexity): يُقاس تعقيد المساحة لـ BFS بشكل أساسي بحجم بنية البيانات اللازمة لتخزين الطابور وتتبع الرؤوس المُزارة. في أسوأ السيناريوهات، قد يحتاج الطابور إلى تخزين جميع الرؤوس الموجودة في المخطط، خاصة عندما تكون جميع الرؤوس على نفس المستوى من المصدر أو عندما يكون المخطط كثيفًا. بالتالي، فإن تعقيد المساحة هو O(|V|)، وهو ما يعكس الحاجة إلى مساحة لتخزين الطابور وقائمة الرؤوس المُزارة. يُعتبر هذا التعقيد مقبولاً في معظم الحالات، ولكنه قد يصبح مشكلة في المخططات ذات الأعداد الهائلة من الرؤوس (مثل مساحات البحث اللانهائية)، حيث يمكن أن يستهلك الطابور ذاكرة كبيرة جدًا.

5. تطبيقات رئيسية في علوم الحاسوب

نظرًا لخصائصها الفريدة في إيجاد أقصر مسار وضمان اكتمال البحث، تتمتع خوارزمية BFS بمجموعة واسعة من التطبيقات الحاسوبية التي تتجاوز مجرد اجتياز المخططات.

  • إيجاد أقصر مسار في المخططات غير الموزونة: هذا هو التطبيق الأكثر شهرة لـ BFS. تُستخدم الخوارزمية للعثور على المسار الذي يحتوي على أقل عدد من الحواف بين عقدتين. يُستخدم هذا في تطبيقات مثل تحليل الشبكات الاجتماعية (إيجاد “درجة الانفصال” بين شخصين) أو في ألعاب الفيديو لتخطيط حركة الوحدة على خريطة شبكية.
  • اختبار الاتصال: يمكن لـ BFS تحديد ما إذا كان مخطط معين متصلاً (Connected) أم لا. إذا تمكنت BFS من زيارة جميع رؤوس المخطط بدءًا من أي نقطة عشوائية، فهذا يعني أن المخطط متصل. وإذا لم تتمكن من زيارة سوى جزء من الرؤوس، فإن هذا الجزء يمثل أحد المكونات المتصلة للمخطط.
  • الزحف على الويب (Web Crawling): تستخدم محركات البحث BFS لتنظيم كيفية زيارة صفحات الويب. يبدأ الزاحف بصفحة معينة، ثم يزور جميع الروابط الموجودة فيها (المستوى الأول)، ثم يزور الروابط الموجودة في هذه الصفحات (المستوى الثاني)، وهكذا. هذا يضمن أن يتم فهرسة الصفحات الأقرب إلى نقطة البداية أولاً.
  • خوارزمية مارك وعلامة (Mark and Sweep) لجمع القمامة: في إدارة الذاكرة، تُستخدم تقنية شبيهة بـ BFS لتحديد الكائنات التي لا يمكن الوصول إليها (Garbage). تبدأ الخوارزمية من مجموعة من الجذور (المتغيرات النشطة) وتستخدم BFS لوضع علامات على جميع الكائنات التي يمكن الوصول إليها؛ أي كائن لم يتم وضع علامة عليه بعد اكتمال BFS يعتبر “قمامة” ويتم إزالته.

إضافة إلى ما سبق، يتم استخدام BFS في بناء شجرة الامتداد الدنيا (Minimum Spanning Tree) في سياق خوارزميات مثل خوارزمية بريم (Prim’s Algorithm)، وكذلك في تحليل الدوائر الكهربائية والشبكات الحاسوبية. إن قدرتها على معالجة المستويات بشكل متساوٍ تجعلها مفيدة في أي سياق يتطلب ضمان استكشاف متساوٍ أو إيجاد حلول تعتمد على المسافة الأدنى.

6. الخصائص والميزات الهامة

تتميز خوارزمية البحث أولاً بالاتساع بعدد من الخصائص النظرية التي تمنحها ميزة على غيرها من خوارزميات البحث في سياقات معينة:

  • الكمال (Completeness): إذا كان هناك حل (أي مسار إلى العقدة الهدف) موجودًا في المخطط، فإن BFS تضمن العثور عليه، شريطة أن يكون المخطط محدودًا. وهذا يعني أن BFS لن تفشل في العثور على المسار إذا كان موجودًا في نطاق البحث.
  • المثالية (Optimality) للمخططات غير الموزونة: في المخططات التي لا تحتوي على أوزان للحواف (أو حيث تكون جميع الأوزان متساوية)، فإن أول مسار تكتشفه BFS إلى أي عقدة هدف هو بالضرورة المسار الأقصر من حيث عدد الحواف. وهذه خاصية قوية تجعلها مفضلة على DFS في سياق إيجاد أقصر مسافة.
  • إنتاج شجرة البحث أولاً بالاتساع: أثناء عملية الاجتياز، تقوم BFS ضمنيًا بإنشاء شجرة فرعية (Subtree) للمخطط تُعرف باسم شجرة البحث أولاً بالاتساع (BFS Tree). تمثل هذه الشجرة أقصر مسار من المصدر إلى كل عقدة يمكن الوصول إليها.
  • استخدام الذاكرة (Memory Usage): على الرغم من كفاءتها الزمنية، فإن BFS تتطلب استخدام ذاكرة أكبر مقارنة بـ DFS. وذلك لأنها تحتاج إلى تخزين جميع العقد في المستوى الحالي، وأحيانًا جميع العقد في المستويات السابقة، في الطابور قبل معالجتها. هذا الاستهلاك العالي للذاكرة يمكن أن يكون قيدًا في المخططات الكبيرة جدًا أو اللانهائية.

تسمح هذه الخصائص النظرية بوضع BFS كأداة موثوقة في النظم التي تتطلب ضمانات حول العثور على الحل الأمثل أو الأقصر. ومع ذلك، يجب دائمًا موازنة خاصية المثالية مع متطلبات الذاكرة؛ فكلما اتسع نطاق البحث، زادت الحاجة إلى مساحة تخزين ضخمة للطابور.

7. المقارنة مع البحث أولاً بالعمق (Depth-First Search – DFS)

تُعد خوارزمية البحث أولاً بالعمق (DFS) النظير الرئيسي لـ BFS، والاثنتان تشتركان في الهدف العام لاجتياز المخططات، لكنهما تختلفان جوهريًا في المنهجية والأداء، مما يجعلهما مناسبتين لأنواع مختلفة من المشكلات.

يكمن الاختلاف الأساسي في بنية البيانات المستخدمة: تعتمد BFS على الطابور (Queue)، مما يجبر البحث على التوسع عرضيًا ومستوى تلو الآخر. في المقابل، تعتمد DFS على المكدس (Stack) (أو الاستدعاءات التكرارية التي تستخدم مكدس النظام)، مما يدفع البحث إلى التعمق قدر الإمكان في فرع واحد قبل التراجع واستكشاف فرع آخر. هذا يعني أن BFS مناسبة لإيجاد أقصر مسار، بينما DFS مناسبة بشكل أفضل للمشكلات التي تتطلب استكشافًا كاملاً للمسار، مثل البحث عن المكونات المتصلة أو إجراء فرز طوبولوجي (Topological Sorting).

من حيث الأداء، يتساوى تعقيد الوقت لكلا الخوارزميتين، حيث يبلغ O(|V| + |E|). ومع ذلك، يختلف تعقيد المساحة بشكل كبير. تتطلب BFS مساحة O(|V|) لتخزين الطابور، وقد تكون هذه المساحة ضخمة إذا كان المخطط يحتوي على العديد من الرؤوس في نفس المستوى. بينما تتطلب DFS مساحة O(h)، حيث h هو عمق المخطط. إذا كان المخطط ضحلًا (Shallow)، فإن DFS تكون أفضل في استخدام الذاكرة؛ ولكن إذا كان المخطط عميقًا جدًا أو يحتوي على عمق بحث لا نهائي، قد تواجه DFS مشكلات في الذاكرة المتعلقة بتجاوز سعة المكدس (Stack Overflow)، بينما قد تفشل BFS في حالة المخططات اللانهائية إذا لم يتم العثور على الحل قريبًا.

باختصار، يتم اختيار BFS عندما تكون الأولوية لـ أقصر مسار أو عندما تكون عقدة الهدف متوقعة بالقرب من نقطة البداية (ضحلة). بينما يتم اختيار DFS عندما تكون الأولوية هي استكشاف المسارات الطويلة أو عندما يكون استخدام الذاكرة قيدًا صارمًا، أو في تطبيقات مثل فحص الدورات (Cycle Detection) أو الفرز الطوبولوجي.

8. مصادر إضافية للقراءة