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

البحث المتعمق الاول بيانات عامّة الصنف uninformed search algorithm (en) — graph traversal (en) بنية البيانات بيان

بحث تعمقي الأولوية / عامودي الأولوية أو البحث المتعمق (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. .

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