بحث بتفضيل العمق

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

تحققت النسخة الأولى من بحث بتفضيل العمق في القرن ال19 على يد عالم الرياضيات الفرنسي بيير تشارلز تريماوCharles Pierre Trémaux (1859–1882) École polytechnique of Paris (X:1876), French engineer of the telegraph

in Public conference, December 2, 2010 – by professor Jean Pelletier-Thibert in Académie de Macon (Burgundy – France) – (Abstract published in the Annals academic, March 2011 – ) كإستراتيجية لحل المتاهات...

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

 شبه الرماز للبحث بتفضيل العمق 
إجراء ب.م.أ(العقدة س)
    ضع علامة بأن "س" تمت زيارتها
    لكل عقدة مجاورة "ص" لـ "س"
        إذا كانت "ص" لم تتم زيارتها
            نفّذ ب.م.أ(ص)

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

 إيجاد اطول مسار 
وفقاً لما ذكره كورمن وآخرون (1992)، العامل الأساسي الذي يميز خوارزمية البحث بالعمق أولاً، هو قدرتها على اكتشاف العقد (أو الرؤوس) التي لم تتم زيارتها بشكل عميق داخل المبيان. وبنائا عليه فإن البحث في العمق اولا هو الحل الامثل لمشكلة إيجاد اطول مسار.

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

خطوات العمليةː

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

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

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

5. تتوقف العملية عندما لا توجد أي عقدة مجاورة بحالة خطأ (أي غير مكتشفة).

6. في النهاية، يتم فحص قيمة المتغير  عː

 في حال كانت ع = 0 يكون المبيان متصل.
 في حال كانت ع > 0 يكون المبيان غير متصل.

 إكتشاف الحلقات 
تُستخدم خوارزمية البحث بالعمق أولاً للتأكد من وجود أو عدم وجود حلقات في المبيان.

 إيجاد المسارات وحل المتاهات 
يمكن استخدام خوارزمية البحث بالعمق أولاً لإيجاد أي مسار بين نقطتين، خصوصاً عندما لا يكون مطلوباً إيجاد أقصر مسار.

 مشاكل المعاكسة 
تُعتبر خوارزمية البحث بالعمق أولاً الأساس لخوارزميات المعاكسة، المستخدمة في مسائل مثل لغز N-Queens، وحل سودوكو، وتوليد التباديل.

 زحف الويب 
تُستخدم خوارزمية البحث بالعمق أولاً في محركات البحث وأدوات الزحف على الويب، حيث تتبع الروابط (وَصْلات ترابطية) بشكل منهجي لاكتشاف الصفحات وفهرستها.

 تحليل الشبكات 
تُساعد خوارزمية البحث بالعمق أولاً في تحليل بنية الشبكات، واكتشاف المكونات المترابطة، وتقييم موثوقية الشبكات.

 المراجع 

تصنيف:خوارزميات بحث
تصنيف:خوارزميات تعتمد على نظرية البيان
تصنيف:قوالب علم الحاسوب