البحث المتعمق الأول
هذه مقالة غير مراجعة.(ديسمبر 2015) |
البحث المتعمق الاول
|
بحث تعمقي الأولوية / عامودي الأولوية أو البحث المتعمق (DFS ) هو خوارزمية لل عبور أو البحث داخل شجرة أو هياكل البيانات كالرسمة البيانية(graph) .[1] يبدأ المرء في الجذر ( اختيار نقطة من الشجرة لتكون جذر وهي النقطة نفسها التي بدأ منها البحث ) و يستكشف قدر الإمكان على طول كل فرع قبل التراجع .
تحققت النسخة الاولى من البحث المتعمق الأول في القرن ال19 من قبل عالم الرياضيات الفرنسي بيير تشارلز تريماو كإستراتيجية لحل متاهات.
الخصائص[عدل]
زمان ومساحة التحليل في DFS تختلف وفقا ل مجال تطبيقه. فمثلا في علم الحاسوب النظري، عادة ما تستخدم DFS لاجتياز أحد الرسم البياني بأكمله، ويستغرق وقتا طويلا Θ ( | V | + | E | ) ، خطي في حجم الرسم البياني. في هذه التطبيقات ويستخدم أيضا O الفضاء ( | V | ) في أسوأ الحالات لتخزين كومة من الرؤوس على مسار البحث الحالي فضلا عن مجموعة من القمم التي تم زيارتها بالفعل .
مثال[عدل]
في هذة الرسمة
https://ar.wikipedia.org/w/File:Graph.traversal.example.svg
يبدأ البحث من النقطة A، على افتراض أن الحواف اليسرى في الرسم البياني تظهر اولا لذلك يتم اختيارها قبل الحواف اليمنى، وعلى افتراض ان البحث يتذكر انه زار نقطة معينة سابقا ولن يكرر زيارتها مرة أخرى، سيزورالنقاط بالترتيب التالي : A، B، D ، F ، E، C ، G. .
تجنبزيارة النقطة مرة أخرى يساعد على على تجنب التكرار الذي يجعلك تدور في دائرة مفرغة بلا نهاية فذلك يضمن لك زيارة جميع النقاط ووجود نهاية لعملية البحث.
مراجع[عدل]
- ^ "معلومات عن البحث المتعمق الأول على موقع mathworld.wolfram.com"، mathworld.wolfram.com، مؤرشف من الأصل في 15 ديسمبر 2019.
![]() |
في كومنز صور وملفات عن: البحث المتعمق الأول |