الرئيسيةعريقبحث

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

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

تحققت النسخة الاولى  من البحث المتعمق الأول في القرن ال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. .

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

موسوعات ذات صلة :