بحث بتفضيل العمق
 | هذه المقالة بحاجة لمراجعة خبير مختص في مجالها. |
 | تحتوي هذه المقالة اصطلاحات معربة غير مُوثَّقة. لا تشمل ويكيبيديا العربية الأبحاث الأصيلة، ويلزم أن تُرفق كل معلومة فيها بمصدر موثوق به. |
 | |
| الصنف |
|
|---|---|
بحث بتفضيل العمق (بالإنجليزية: depth-first search) طريقة للبحث داخل بيان (شجرة، شجرة اثنانية، بيان كثيف، بيان طفيف).[1] خوارزمية بحث بتفضيل العمق غير مفيدة في ذاتها، لكن تبرز أهميتها عند توظيفها لعمل مهام اخرى (مثلː عد المكونات المترابطة، و البت بالترابط، أو حتى إيجاد الحواف الفاصلة.
تحققت النسخة الأولى من بحث بتفضيل العمق في القرن ال19 على يد عالم الرياضيات الفرنسي بيير تشارلز تريماو[2] كإستراتيجية لحل المتاهات.[3][4]
استراتيجية البحث
[عدل]تتمثل استراتيجية البحث -كما يوحي الاسم- في البحث أعمق متى أمكن ذلك. فالبحث بتفضيل العمق يستكشف كل الحواف الخارجة من اخر رأس تم اكتشافه، والذي ما زالت هناك حواف صادرة منه لم يتم المرور بها بعد. بمعنى آخرː عند تمثيل البحث بالعمق اولا، إذا وصلت الخوارزمية الى رأس جديد، فإنها لا تعود إلى الخلف مباشرة، بل تستمر في التقدم منه عبر أي حافة غير مستكشفة متاحة. وعندما تنفذ جميع الحواف من هذا الرأس، تعود الخوارزمية إلي الرأس الذي سبقه لتبحث عن حواف أخرى غير مستكشفة، وتكرر هذه العملية حتى تتم زيارة جميع الرؤوس. في حال بقاء رؤوس غير مستكشفة فأن الخوارزمية تعتبرها مصدرا وتكرر البحث من ذلك المصدر. الخوارزمية تستمر بالتكرار حتى تتم زيارة جميع الرؤوس[5]
شبه الرماز للبحث بتفضيل العمق
[عدل]إجراء ب.م.أ(العقدة س)
ضع علامة بأن "س" تمت زيارتها
لكل عقدة مجاورة "ص" لـ "س"
إذا كانت "ص" لم تتم زيارتها
نفّذ ب.م.أ(ص)
استخدامات البحث بالعمق اولا
[عدل]خوارزمية البحث في العمق أولا، تكون فعالة بشكل كبير عند التعامل مع الاشجار ذات الكم الكبير من العقد، بسبب انها تبحث عن العقد في زمن اقصر.[6]
إيجاد اطول مسار
[عدل]وفقاً لما ذكره كورمن وآخرون (1992)، العامل الأساسي الذي يميز خوارزمية البحث بالعمق أولاً، هو قدرتها على اكتشاف العقد (أو الرؤوس) التي لم تتم زيارتها بشكل عميق داخل المبيان. وبنائا عليه فإن البحث في العمق اولا هو الحل الامثل لمشكلة إيجاد اطول مسار.[7]
يمكن تمثيل عملية التحقق من إتصال المبيان بإستخدام إقتران التكرار، يسمى "المَزارُ" والذي يبدأ من رأس المصدر أو الجذر في حال كان المبيان شجرة.
خطوات العمليةː
- نفترض أن الرأس س هو رأس المصدر. تم وضح حالتها "صحيح"، للإشارة على ان هذا الرأس تمت زيارته.
- نقوم بإنقاص قيمة المتغير ع بمقدار 1، والذي يمثل العقد الغير مكتشفة.
- من ثم، تقوم الخوارزمية بالبحث عن العقدة المصنفة على انها الاصغر بالمقارنة مع س.
- في حالة وجود العقدة ذات الرقم الاصغر. يتم إستدعاء الإقتران بشكل متكرر على هذه العقدة، وإنقاص ع بمقدار 1.
4 .تستمر هذه العملية على نفس المنوال، حيث يتم استدعاء إقتران التكرار على العقد المجاورة غير المزارة حسب ترتيب أرقامها.
5. تتوقف العملية عندما لا توجد أي عقدة مجاورة بحالة خطأ (أي غير مكتشفة).
6. في النهاية، يتم فحص قيمة المتغير عː
- في حال كانت ع = 0 يكون المبيان متصل.
- في حال كانت ع > 0 يكون المبيان غير متصل.
إكتشاف الحلقات
[عدل]تُستخدم خوارزمية البحث بالعمق أولاً للتأكد من وجود أو عدم وجود حلقات في المبيان.
يمكن استخدام خوارزمية البحث بالعمق أولاً لإيجاد أي مسار بين نقطتين، خصوصاً عندما لا يكون مطلوباً إيجاد أقصر مسار.
مشاكل المعاكسة
[عدل]تُعتبر خوارزمية البحث بالعمق أولاً الأساس لخوارزميات المعاكسة، المستخدمة في مسائل مثل لغز N-Queens، وحل سودوكو، وتوليد التباديل.
زحف الويب
[عدل]تُستخدم خوارزمية البحث بالعمق أولاً في محركات البحث وأدوات الزحف على الويب، حيث تتبع الروابط (وَصْلات ترابطية) بشكل منهجي لاكتشاف الصفحات وفهرستها.
تحليل الشبكات
[عدل]تُساعد خوارزمية البحث بالعمق أولاً في تحليل بنية الشبكات، واكتشاف المكونات المترابطة، وتقييم موثوقية الشبكات.
المراجع
[عدل]- ^ Even، Guy؛ Even، Shimon، المحررون (2011). Depth-First Search (ط. 2). Cambridge: Cambridge University Press. ص. 46–64. ISBN:978-0-521-51718-8. مؤرشف من الأصل في 2018-06-17.
- ^ 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 – ISSN [http://www.worldcat.org/issn/0980-6032 0980-6032 ])
- ^ Even، Shimon (2011)، Graph Algorithms (ط. 2nd)، Cambridge University Press، ص. 46–48، ISBN:978-0-521-73653-4، مؤرشف من الأصل في 2022-10-02.
- ^ Sedgewick، Robert (2002)، Algorithms in C++: Graph Algorithms (ط. 3rd)، Pearson Education، ISBN:978-0-201-36118-6.
- ^ Thomas H. Cormen Charles E. Leiseron Ronald L. Rivest Clifford Stein، Thomas Charles Ronald Clifford (2009). Introduction to Algorithms (ط. 3ed). Massachusetts Institute of Technology.
{{استشهاد بكتاب}}:|طبعة=يحوي نصًّا زائدًا (مساعدة)صيانة الاستشهاد: التاريخ والسنة (link) - ^ "Analysis Of The Depth First Search Algorithms" (PDF). مؤرشف من الأصل (PDF) في 2022-04-26. اطلع عليه بتاريخ 2025.
{{استشهاد ويب}}: تحقق من التاريخ في:|تاريخ-الوصول=(مساعدة) - ^ "Implementation and Analysis of Depth-First Search (DFS) Algorithm for Finding The Longest Path". Research Gate. 2011. مؤرشف من الأصل في 2022-06-22. اطلع عليه بتاريخ 2025.
{{استشهاد ويب}}: تحقق من التاريخ في:|تاريخ-الوصول=(مساعدة) - ^ "Connectivity algorithm with depth first search (DFS) on simple graphs". Research Gate. 2018. اطلع عليه بتاريخ 2025.
{{استشهاد ويب}}: تحقق من التاريخ في:|تاريخ-الوصول=(مساعدة) - ^ "Exploring Maze Navigation: A Comparative Study of DFS, BFS, and A* Search Algorithms" (PDF).
