البحث المتعمق الأول

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

هذه مقالة غير مراجعة. ينبغي أن يزال هذا القالب بعد أن يراجعها محرر مغاير للذي أنشأها؛ إذا لزم الأمر فيجب أن توسم المقالة بقوالب الصيانة المناسبة. يمكن أيضاً تقديم طلب لمراجعة المقالة في الصفحة المُخصصة لذلك. (ديسمبر 2015)

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

الخصائص

زمان ومساحة التحليل في  DFS تختلف وفقا ل مجال تطبيقه.  فمثلا في علم الحاسوب النظري ، عادة ما تستخدم DFS لاجتياز أحد الرسم البياني بأكمله ، و يستغرق وقتا طويلا Θ ( | V | + | E | ) ، خطي في حجم الرسم البياني. في هذه التطبيقات ويستخدم أيضا O الفضاء ( | V | ) في أسوأ الحالات لتخزين كومة من الرؤوس على مسار البحث الحالي فضلا عن مجموعة من القمم التي تم زيارتها  بالفعل .

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

مثال

في هذة الرسمة 

https://ar.wikipedia.org/w/File:Graph.traversal.example.svg

يبدأ البحث  من النقطة A، على افتراض أن الحواف اليسرى في الرسم البياني تظهر اولا لذلك يتم اختيارها  قبل الحواف اليمنى ، و على افتراض  ان البحث يتذكر انه  زار نقطة معينة سابقا ولن يكرر زيارتها مرة أخرى  ، سيزورالنقاط بالترتيب التالي : A، B، D ، F ، E، C ، G. .

تجنبزيارة النقطة مرة أخرى  يساعد على على تجنب التكرار الذي يجعلك تدور في دائرة مفرغة بلا نهاية  فذلك يضمن لك زيارة جميع النقاط ووجود نهاية لعملية البحث.

مراجع
  1. "معلومات عن البحث المتعمق الأول على موقع mathworld.wolfram.com". mathworld.wolfram.com. مؤرشف من الأصل في 15 ديسمبر 2019. الوسيط |CitationClass= تم تجاهله (مساعدة)
  2. "معلومات عن البحث المتعمق الأول على موقع academic.microsoft.com". academic.microsoft.com. مؤرشف من الأصل في 27 أكتوبر 2020. الوسيط |CitationClass= تم تجاهله (مساعدة)
    في كومنز صور وملفات عن: البحث المتعمق الأول
    • بوابة رياضيات
    • بوابة خوارزميات
    • بوابة علم الحاسوب
    This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.