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

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

من ويكيبيديا، الموسوعة الحرة
اذهب إلى التنقل اذهب إلى البحث
Question book-new.svg
المحتوى هنا ينقصه الاستشهاد بمصادر. يرجى إيراد مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (فبراير 2016)
N write.svg
هذه مقالة غير مراجعة. ينبغي أن يزال هذا القالب بعد أن يراجعها محرر ما عدا الذي أنشأها؛ إذا لزم الأمر فيجب أن توسم المقالة بقوالب الصيانة المناسبة. (ديسمبر 2015)

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

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