مرجع
آخر الزيارات

بحث بتفضيل العمق

539 كلمة•0 مشاهدة•🗒️ منذ 10 أيام
باختصار: بحث بتفضيل العمق طريقة للبحث داخل بيان (شجرة، شجرة اثنانية، بيان كثيف، بيان طفيف). تجد هنا «إكتشاف الحلقات»، «زحف الويب» و«تحليل الشبكات» ضمن 13 قسماً.
المحتويات
  1. إكتشاف الحلقات
  2. زحف الويب
  3. تحليل الشبكات
  4. التحقق من الاتصال
  5. إذا كانت "ص" لم تتم زيارتها
  6. شبه الرماز للبحث بتفضيل العمق
  7. ضع علامة بأن "س" تمت زيارتها
  8. استراتيجية البحث
  9. خطوات العمليةː
  10. استخدامات البحث بالعمق اولا
  11. مشاكل المعاكسة
  12. إيجاد اطول مسار
  13. إيجاد المسارات وحل المتاهات
بحث بتفضيل العمق

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

ومن ناحية أخرى، تحققت النسخة الأولى من بحث بتفضيل العمق في القرن ال19 على يد عالم الرياضيات الفرنسي بيير تشارلز تريماو كإستراتيجية لحل المتاهات.

إكتشاف الحلقات

كذلك، تُستعمل خوارزمية البحث بالعمق أولاً للتأكد من وجود أو عدم وجود حلقات في المبيان.

زحف الويب

وعلى صعيد آخر، تُستعمل خوارزمية البحث بالعمق أولاً في محركات البحث وأدوات الزحف على الويب، حيث تتبع الروابط (وَصْلات ترابطية) بشكل منهجي لاكتشاف الصفحات وفهرستها.

تحليل الشبكات

في هذا الإطار، تُساعد خوارزمية البحث بالعمق أولاً في تحليل بنية الشبكات، واكتشاف المكونات المترابطة، وتقييم موثوقية الشبكات.

التحقق من الاتصال

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

إذا كانت "ص" لم تتم زيارتها

نفّذ ب.م.أ(ص)

شبه الرماز للبحث بتفضيل العمق

إجراء ب.م.أ(العقدة س)

ضع علامة بأن "س" تمت زيارتها

لكل عقدة مجاورة "ص" لـ "س"

استراتيجية البحث

من جانب آخر، تتمثل استراتيجية البحث -كما يوحي الاسم- في البحث أعمق متى أمكن ذلك. فالبحث بتفضيل العمق يستكشف كل الحواف الخارجة من اخر رأس تم اكتشافه، والذي ما زالت هناك حواف صادرة منه لم يتم المرور بها بعد. بمعنى آخرː عند تمثيل البحث بالعمق اولا، إذا وصلت الخوارزمية الى رأس جديد، فإنها لا تعود إلى الخلف مباشرة، بل تستمر في التقدم منه عبر أي حافة غير مستكشفة متاحة. وعندما تنفذ جميع الحواف من هذا الرأس، تعود الخوارزمية إلي الرأس الذي سبقه لتبحث عن حواف أخرى غير مستكشفة، وتكرر هذه العملية حتى تتم زيارة جميع الرؤوس. في حال بقاء رؤوس غير مستكشفة فأن الخوارزمية تعتبرها مصدرا وتكرر البحث من ذلك المصدر. الخوارزمية تستمر بالتكرار حتى تتم زيارة جميع الرؤوس

خطوات العمليةː

في هذا الإطار، نفترض أن الرأس س هو رأس المصدر. تم وضح حالتها "صحيح"، للإشارة على ان هذا الرأس تمت زيارته.

علاوةً على ذلك، من ثم، تقوم الخوارزمية بالبحث عن العقدة المصنفة على انها الاصغر بالمقارنة مع س.

من جانب آخر، نقوم بإنقاص قيمة المتغير ع بمقدار 1، والذي يمثل العقد الغير مكتشفة.

في هذا الإطار، في حالة وجود العقدة ذات الرقم الاصغر. يتم إستدعاء الإقتران بشكل متكرر على هذه العقدة، وإنقاص ع بمقدار 1.

وعلى صعيد آخر، 4 .تستمر هذه العملية على نفس المنوال، حيث يتم استدعاء إقتران التكرار على العقد المجاورة غير المزارة حسب ترتيب أرقامها.

  • 5. تتوقف العملية عندما لا توجد أي عقدة مجاورة بحالة خطأ (أي غير مكتشفة).
  • 6. في النهاية، يتم فحص قيمة المتغير عː
  • في حال كانت ع = 0 يكون المبيان متصل.
  • في حال كانت ع > 0 يكون المبيان غير متصل.

استخدامات البحث بالعمق اولا

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

مشاكل المعاكسة

وفي السياق ذاته، تُعتبر خوارزمية البحث بالعمق أولاً الأساس لخوارزميات المعاكسة، المستعملة في مسائل مثل لغز N-Queens، وحل سودوكو، وتوليد التباديل.

إيجاد اطول مسار

في هذا الإطار، بحسب ما ذكره كورمن وآخرون (1992)، العامل الأساسي الذي يميز خوارزمية البحث بالعمق أولاً، هو قدرتها على اكتشاف العقد (أو الرؤوس) التي لم تتم زيارتها بشكل عميق داخل المبيان. وبنائا عليه فإن البحث في العمق اولا هو الحل الامثل لمشكلة إيجاد اطول مسار.

إيجاد المسارات وحل المتاهات

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

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.