البحث بالعرض أولاً

📅 آخر تحديث: ٢٦ يوليو ٢٠٢٦
✍️ نُشر في: ٢٦ يوليو ٢٠٢٦
📷 يحتوي على 33 صور
الموسوعة الحرة
خوارزمية حل المتاهة باستخدام البحث في العرض أولاً
الجزء العلوي من شجرة لعبة إكس أو

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

على سبيل المثال، في نهاية لعبة الشطرنج ، قد يقوم محرك الشطرنج ببناء شجرة اللعبة انطلاقًا من الوضع الحالي بتطبيق جميع النقلات الممكنة، ثم يستخدم خوارزمية البحث بالعرض أولًا لإيجاد وضعية فوز للأبيض. قد تكون الأشجار الضمنية (مثل أشجار اللعبة أو أشجار حل المشكلات الأخرى) ذات حجم لانهائي؛ ويضمن البحث بالعرض أولًا إيجاد عقدة حل [ 1 ] إن وُجدت.

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

يمكن تعميم البحث بالعرض أولاً ليشمل كلاً من الرسوم البيانية غير الموجهة والرسوم البيانية الموجهة ذات عقدة بداية معينة (يشار إليها أحيانًا باسم "مفتاح البحث"). [ 4 ] في البحث في فضاء الحالة في الذكاء الاصطناعي ، يُسمح غالبًا بعمليات البحث المتكررة عن الرؤوس، بينما في التحليل النظري للخوارزميات القائمة على البحث بالعرض أولاً، تُتخذ الاحتياطات عادةً لمنع التكرارات.

ابتكر كونراد تسوزه خوارزمية البحث في العرض أولاً (BFS) وتطبيقها في إيجاد المكونات المتصلة للرسوم البيانية عام 1945 ، وذلك في أطروحته للدكتوراه (المرفوضة) حول لغة البرمجة Plankalkül ، ولكن لم تُنشر هذه الأطروحة حتى عام 1972. [ 5 ] أُعيد ابتكارها عام 1959 على يد إدوارد ف. مور ، الذي استخدمها لإيجاد أقصر مسار للخروج من متاهة، [ 6 ] [ 7 ] ثم طوّرها سي واي لي لاحقًا إلى خوارزمية لتوجيه الأسلاك (نُشرت عام 1961). [ 8 ]

الشفرة الزائفة

تجد الشفرة الزائفة أدناه أقصر مسار من رأس الجذر المعطى إلى جميع الرؤوس الأخرى في الرسم البياني باستخدام BFS.

المدخلات : رسم بياني G وجذر رأس ابتدائي لـ G

الناتج : حالة الهدف. تتتبع الروابط الأصلية أقصر مسار للعودة إلى الجذر [ 9 ]

الإجراء 1 BFS( G , root ) هو 2 ليكن Q طابورًاتم استكشاف جذر التسمية 3 4 Q .enqueue( root ) 5 طالما أن Q ليست فارغة ، 6 v := Q .dequeue() 7 إذا كانت v هي الهدف، 8 فأرجع v. 9 لكل الحواف من v إلى w في G.adjacentEdges ( v ) ، 10 إذا لم يتم تصنيف w على أنها مستكشفة ، 11 صنّف w على أنها مستكشفة. 12 w .parent := v 13 Q .enqueue( w )

مزيد من التفاصيل

خريطة نموذجية لجنوب ألمانيا مع بعض الروابط بين المدن
الشجرة التي تم الحصول عليها من خلال البحث في العرض أولاً عند تشغيل خوارزمية البحث في العرض أولاً على الخريطة المعطاة والبدء من فرانكفورت

يشبه هذا التنفيذ غير التكراري التنفيذ غير التكراري للبحث العميق أولاً ، ولكنه يختلف عنه في جانبين:

  1. يستخدم هذا النظام طابورًا ( الأول في الأول خارجًا ) بدلاً من مكدس (الأخير في الأول خارجًا)
  2. يتحقق مما إذا كان قد تم استكشاف رأس معين قبل إضافته إلى قائمة الانتظار بدلاً من تأخير هذا الفحص حتى يتم إخراج الرأس من قائمة الانتظار.

إذا كانت G شجرة ، فإن استبدال طابور خوارزمية البحث بالعرض أولاً بمكدس سيؤدي إلى خوارزمية بحث بالعمق أولاً. بالنسبة للرسوم البيانية العامة، فإن استبدال مكدس تطبيق البحث بالعمق أولاً التكراري بطابور سيؤدي أيضاً إلى خوارزمية بحث بالعرض أولاً، وإن كانت غير قياسية إلى حد ما. [ 10 ]

تحتوي قائمة الانتظار Q على الحدود التي يبحث فيها الخوارزمية حاليًا.

يمكن تصنيف العقد على أنها مستكشفة عن طريق تخزينها في مجموعة، أو عن طريق سمة على كل عقدة، وذلك حسب طريقة التنفيذ.

تُعد السمة الأصلية لكل عقدة مفيدة للوصول إلى العقد في أقصر مسار، على سبيل المثال عن طريق التراجع من عقدة الوجهة إلى عقدة البداية، بمجرد تشغيل BFS، وتعيين العقد السابقة.

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

تحليل

تعقيد الزمان والمكان

يمكن التعبير عن التعقيد الزمني على النحو التالي:يا(|V|+|هـ|){\displaystyle O(|V|+|E|)}، حيث سيتم استكشاف كل رأس وكل حافة في أسوأ الحالات.|V|{\displaystyle |V|}يمثل عدد الرؤوس و|هـ|{\displaystyle |E|}يمثل عدد الحواف في الرسم البياني. لاحظ أنيا(|هـ|){\displaystyle O(|E|)}قد يختلف بينيا(1){\displaystyle O(1)}ويا(|V|2){\displaystyle O(|V|^{2})}، وذلك بحسب مدى تباعد الرسم البياني المدخل. [ 11 ]

عندما يكون عدد رؤوس الرسم البياني معروفًا مسبقًا، وتُستخدم هياكل بيانات إضافية لتحديد الرؤوس التي أُضيفت بالفعل إلى قائمة الانتظار، يمكن التعبير عن تعقيد المساحة على النحو التالي:يا(|V|){\displaystyle O(|V|)}، أين|V|{\displaystyle |V|}يمثل عدد الرؤوس. هذا بالإضافة إلى المساحة المطلوبة للرسم البياني نفسه، والتي قد تختلف باختلاف تمثيل الرسم البياني المستخدم في تطبيق الخوارزمية.

عند التعامل مع الرسوم البيانية الكبيرة جدًا بحيث لا يمكن تخزينها بشكل صريح (أو غير المحدودة)، يكون من الأنسب وصف تعقيد البحث بالعرض أولًا بمصطلحات مختلفة: لإيجاد العقد التي تبعد مسافة d عن عقدة البداية (مقاسة بعدد عمليات اجتياز الحواف)، يستغرق البحث بالعرض أولًا وقتًا وذاكرة من رتبة O ( bd + 1 ) ، حيث b هو " عامل التفرع " للرسم البياني (متوسط ​​درجة الخروج). [ 12 ] : 81

اكتمال

في تحليل الخوارزميات، يُفترض أن يكون مُدخل البحث بالعرض أولاً عبارة عن رسم بياني محدود، ممثل بقائمة تجاور أو مصفوفة تجاور أو تمثيل مشابه. مع ذلك، عند تطبيق أساليب اجتياز الرسوم البيانية في الذكاء الاصطناعي ، قد يكون المُدخل تمثيلاً ضمنياً لرسم بياني غير محدود. في هذا السياق، تُوصف طريقة البحث بأنها كاملة إذا كانت تضمن إيجاد حالة الهدف إن وُجدت. البحث بالعرض أولاً كامل، بينما البحث بالعمق أولاً ليس كذلك. عند تطبيقه على رسوم بيانية غير محدودة ممثلة ضمنياً، سيجد البحث بالعرض أولاً حالة الهدف في النهاية، بينما قد يضل البحث بالعمق أولاً في أجزاء من الرسم البياني لا تحتوي على حالة هدف، ولن يعود أبداً. [ 13 ]

طلب BFS

يُقال إن تعداد رؤوس الرسم البياني هو ترتيب BFS إذا كان ناتجًا محتملاً لتطبيق BFS على هذا الرسم البياني.

يتركجي=(V،هـ){\displaystyle G=(V,E)}ليكن رسمًا بيانيًا معن{\displaystyle n}الرؤوس. تذكر ذلكشمال(v){\displaystyle N(v)}هي مجموعة جيرانv{\displaystyle v}. يتركσ=(v1،...،vم){\displaystyle \sigma =(v_{1},\dots ,v_{m})}أن تكون قائمة بعناصر مميزة منV{\displaystyle V}، لv∈V∖{v1،...،vم}{\displaystyle v\in V\setminus \{v_{1},\dots ,v_{m}\}}، يتركνσ(v){\displaystyle \nu _{\sigma }(v)}كن الأقلأنا{\displaystyle i}بحيثvأنا{\displaystyle v_{i}}هو جار لـv{\displaystyle v}، إذا كان هذاأنا{\displaystyle i}موجود، ويكون∞{\displaystyle \infty }خلاف ذلك.

يتركσ=(v1،...،vن){\displaystyle \sigma =(v_{1},\dots ,v_{n})}ليكن تعدادًا لرؤوسV{\displaystyle V}التعدادσ{\displaystyle \sigma }ويُقال إنه ترتيب BFS (مع المصدر)v1{\displaystyle v_{1}}) إذا، لكل1<أنا≤ن{\displaystyle 1<i\leq n}،vأنا{\displaystyle v_{i}}هو الرأسw∈V∖{v1،...،vأنا-1}{\displaystyle w\in V\setminus \{v_{1},\dots ,v_{i-1}\}}بحيثν(v1،...،vأنا-1)(w){\displaystyle \nu _{(v_{1},\dots ,v_{i-1})}(w)}هو الحد الأدنى. وبالمثل،σ{\displaystyle \sigma }هو ترتيب BFS إذا، بالنسبة للجميع1≤أنا<ج<ك≤ن{\displaystyle 1\leq i<j<k\leq n}معvأنا∈شمال(vك)∖شمال(vج){\displaystyle v_{i}\in N(v_{k})\setminus N(v_{j})}يوجد جار vم{\displaystyle v_{m}}لvج{\displaystyle v_{j}}بحيثم<أنا{\displaystyle m<i}.

التطبيقات

يمكن استخدام البحث بالعرض أولاً لحل العديد من المشاكل في نظرية الرسم البياني، على سبيل المثال:

انظر أيضاً

مراجع

  1. ↑ أي، عقدة تحقق الخاصية المحددة
  2. ↑ كورمن توماس هـ. وآخرون  (2009). "22.3". مقدمة في الخوارزميات . مطبعة معهد ماساتشوستس للتكنولوجيا.
  3. ↑ كورف، ريتشارد إي. (1985). "التعميق التكراري بالبحث العميق أولاً: بحث مثالي عن الشجرة المقبولة" . الذكاء الاصطناعي (27): 99-100 . doi : 10.7916/D8HQ46X1 .
  4. ↑ "مواصفات معيار Graph500 (تقييم أداء الحواسيب العملاقة)" . Graph500.org، 2010. مؤرشف من الأصل بتاريخ 26-03-2015 . تم الاطلاع عليه بتاريخ 15-03-2015 .
  5. ^ زوزي، كونراد (1972)، Der Plankalkül (في المانيا)، أرشيف الإنترنت كونراد تسوسيانظر الصفحات 96-105 من ملف PDF المرفق (الترقيم الداخلي 2.47-2.56).
  6. ↑ مور، إدوارد ف. (1959). "أقصر مسار عبر متاهة". وقائع الندوة الدولية حول نظرية التبديل . مطبعة جامعة هارفارد. ص 285-292 . كما ورد في مراجع كورمن، ليسرسون، ريفست، وستين.
  7. ↑ سكينا، ستيفن (2008). "الفرز والبحث". دليل تصميم الخوارزميات . سبرينغر. ص 480. Bibcode : 2008adm..book.....S . doi : 10.1007/978-1-84800-070-4_4 . ISBN  978-1-84800-069-8.
  8. ↑ لي، سي واي (1961). "خوارزمية لوصلات المسارات وتطبيقاتها". معاملات معهد مهندسي الراديو في الحواسيب الإلكترونية (3): 346-365 . doi : 10.1109/TEC.1961.5219222 . S2CID 40700386 . 
  9. ↑ كورمن، توماس هـ. (يناير 2010). "22.2 البحث بالعرض أولاً". مقدمة في الخوارزميات . برنتيس هول الهند المحدودة. ISBN 978-81-203-4007-7. OCLC 1006880283 . 
  10. ↑ "اجتياز الرسم البياني القائم على المكدس لا يساوي البحث العميق أولاً" . 11011110.github.io . تم ​​الاسترجاع في 10 يونيو 2020 .
  11. ↑ كورمن، توماس هـ .؛ ليسرسون، تشارلز إي .؛ ريفست، رونالد ل .؛ شتاين، كليفورد (2001) [1990]. "22.2 البحث بالعرض أولاً". مقدمة في الخوارزميات ( الطبعة الثانية). مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل. الصفحات 531-539 . ISBN   0-262-03293-7.
  12. ↑ راسل، ستيوارت ؛ نورفيج، بيتر (2003) [1995]. الذكاء الاصطناعي: منهج حديث ( الطبعة الثانية). برنتيس هول. ISBN  978-0137903955.
  13. ↑ كوبين، ب. (2004). الذكاء الاصطناعي في ضوء. جونز وبارتليت للتعليم. ص 79-80.
  14. ↑ عزيز، عدنان؛ براكاش، أميت (2010). "4. خوارزميات على الرسوم البيانية". خوارزميات للمقابلات . Algorithmsforinterviews.com. ص 144. ISBN  978-1453792995.
  15. ^ كلاينبرج، جون ؛ تاردوس ، إيفا (2006)، تصميم الخوارزمية ، أديسون ويسلي، ص 94 – 97 .
  16. ↑ دوليبالا، لاكسمان؛ بليلوش، جاي إي؛ شون، جوليان (21 أغسطس 2019). خوارزميات الرسوم البيانية المتوازية ذات الكفاءة النظرية يمكن أن تكون سريعة وقابلة للتوسع . ص 17. arXiv : 1805.05208 . doi : 10.1145/3210377.3210414 . ISBN  9781450357999. S2CID 44126609 . 
  • كنوت، دونالد إي. (1997)، فن برمجة الحاسوب، المجلد 1، الطبعة الثالثة، بوسطن: أديسون-ويسلي، رقم ISBN 978-0-201-89683-1تمت أرشفة هذا النص من المصدر الأصلي بتاريخ 4 سبتمبر 2008 ، وتمت معاينته بتاريخ 9 فبراير 2008.
  • هياكل البيانات المفتوحة - القسم 12.3.1 - البحث بالعرض أولاً ، بات مورين