البحث العميق أولاً

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

قام عالم الرياضيات الفرنسي شارل بيير تريمو ^{[ 1 ]} بدراسة نسخة من البحث العميق أولاً كاستراتيجية لحل المتاهات . ^{[ 2 ] [ 3 ]}

يختلف تحليل الوقت والمساحة لخوارزمية البحث العمقي أولاً (DFS) باختلاف مجال تطبيقها. في علوم الحاسوب النظرية، تُستخدم خوارزمية DFS عادةً لاجتياز رسم بياني كامل، وتستغرق وقتًا${\displaystyle O(|V|+|E|)}$، ^{[ 4 ]} حيث${\displaystyle |V|}$يمثل عدد الرؤوس و${\displaystyle |E|}$عدد الحواف . يتناسب هذا العدد خطيًا مع حجم الرسم البياني. وفي هذه التطبيقات، فإنه يستخدم أيضًا مساحة${\displaystyle O(|V|)}$في أسوأ الأحوال، يتم تخزين مجموعة الرؤوس على مسار البحث الحالي بالإضافة إلى مجموعة الرؤوس التي تمت زيارتها مسبقًا. وبالتالي، في هذا السياق، تكون حدود الوقت والمساحة مماثلة لحدود البحث بالعرض أولًا ، ويعتمد اختيار أي من هاتين الخوارزميتين بشكل أقل على تعقيدهما وأكثر على الخصائص المختلفة لترتيب الرؤوس التي تنتجها كل خوارزمية.

في تطبيقات البحث العمقي أولاً (DFS) في مجالات محددة، كالبحث عن حلول في الذكاء الاصطناعي أو زحف الويب، غالبًا ما يكون الرسم البياني المراد اجتيازه إما كبيرًا جدًا بحيث يتعذر زيارته بالكامل أو لانهائيًا (قد يعاني DFS من مشكلة عدم الانتهاء ). في مثل هذه الحالات، يُجرى البحث بعمق محدود فقط ؛ ونظرًا لمحدودية الموارد، كالذاكرة أو مساحة القرص، لا تُستخدم عادةً هياكل البيانات لتتبع مجموعة الرؤوس التي تمت زيارتها سابقًا. عند إجراء البحث بعمق محدود، يظل الوقت خطيًا بالنسبة لعدد الرؤوس والحواف الموسعة (مع أن هذا العدد لا يساوي حجم الرسم البياني بالكامل لأن بعض الرؤوس قد تُفحص أكثر من مرة والبعض الآخر لا يُفحص على الإطلاق)، لكن تعقيد المساحة لهذا النوع من DFS يتناسب فقط مع حد العمق، وبالتالي فهو أصغر بكثير من المساحة اللازمة للبحث بنفس العمق باستخدام البحث العرضي أولاً. في مثل هذه التطبيقات، يُعد DFS أكثر ملاءمةً للطرق الاستدلالية لاختيار فرع ذي احتمالية جيدة. عندما لا يكون حد العمق المناسب معروفًا مسبقًا، يُطبّق البحث العميق التكراري أولًا (DFS) بشكل متكرر مع سلسلة من الحدود المتزايدة. في نمط التحليل القائم على الذكاء الاصطناعي، مع عامل تفرع أكبر من واحد، يزيد البحث العميق التكراري وقت التشغيل بمعامل ثابت فقط مقارنةً بالحالة التي يكون فيها حد العمق الصحيح معروفًا، وذلك بسبب النمو الهندسي لعدد العقد في كل مستوى.

يمكن استخدام خوارزمية البحث العمقي أولاً (DFS) لجمع عينة من عقد الرسم البياني. ومع ذلك، فإن خوارزمية البحث العمقي أولاً غير الكاملة، على غرار خوارزمية البحث العرضي أولاً غير الكاملة ، تميل نحو العقد ذات الدرجة العالية .

بالنسبة للرسم البياني التالي:

يبدأ البحث العميق أولاً من العقدة A، بافتراض اختيار الحواف اليسرى في الرسم البياني الموضح قبل الحواف اليمنى، وبافتراض أن البحث يتذكر العقد التي تمت زيارتها سابقًا ولن يكررها (نظرًا لصغر حجم الرسم البياني)، فإنه سيزور العقد بالترتيب التالي: A، B، D، F، E، C، G. تشكل الحواف التي تم اجتيازها في هذا البحث شجرة تريموكس ، وهي بنية ذات تطبيقات مهمة في نظرية الرسوم البيانية . أما إجراء البحث نفسه دون تذكر العقد التي تمت زيارتها سابقًا فيؤدي إلى زيارة العقد بالترتيب A، B، D، F، E، A، B، D، F، E، وهكذا إلى ما لا نهاية، عالقًا في حلقة A، B، D، F، E، دون الوصول إلى C أو G.

يُعد التعميق التكراري إحدى التقنيات لتجنب هذه الحلقة اللانهائية، وسيصل إلى جميع العقد.

يمكن وصف نتيجة البحث العميق أولاً في الرسم البياني بسهولة باستخدام شجرة ممتدة للرؤوس التي تم الوصول إليها أثناء البحث. بناءً على هذه الشجرة الممتدة، يمكن تقسيم حواف الرسم البياني الأصلي إلى ثلاث فئات: الحواف الأمامية ، التي تشير من عقدة في الشجرة إلى أحد أحفادها، والحواف الخلفية ، التي تشير من عقدة إلى أحد أسلافها، والحواف المتقاطعة ، التي لا تشير إلى أي من النوعين . أحيانًا تُصنف حواف الشجرة ، وهي الحواف التي تنتمي إلى الشجرة الممتدة نفسها، بشكل منفصل عن الحواف الأمامية. إذا كان الرسم البياني الأصلي غير موجه، فإن جميع حوافه إما حواف شجرة أو حواف خلفية.

إذا ( أ ) فإن { ب } آخر { ج } د

تطبيق تكراري لخوارزمية البحث العمقي أولاً: ^{[ 5 ]}

الإجراء DFS( G , v ) هو: قم بتصنيف الرأس v على أنه مكتشف لجميع الحواف الموجهة من v إلى w الموجودة في G.adjacentEdges ( v ). إذا لم يتم تصنيف الرأس w على أنه مكتشف، فقم باستدعاء DFS( G , w ) بشكل متكرر.

تطبيق غير تكراري لخوارزمية البحث العمقي أولاً مع تعقيد مساحة في أسوأ الحالات${\displaystyle O(|E|)}$، مع إمكانية وجود رؤوس مكررة على المكدس: ^{[ 6 ]}

الإجراء DFS_iterative( G , v ) هو: ليكن S مكدسًا ، أضف إليه v . طالما أن S غير فارغ، قم بإزالة v من S. إذا لم يتم تصنيف v على أنه مكتشف، فقم بتصنيفه على أنه مكتشف. لكل حافة من v إلى w في G.adjacentEdges ( v ) ، أضف w إلى S.

تزور هاتان النسختان من خوارزمية البحث العمقي أولاً (DFS) جيران كل رأس بترتيب معاكس: أول جار يزوره النموذج التكراري هو أول جار في قائمة الحواف المتجاورة، بينما في النموذج التكراري، أول جار يزوره هو آخر جار في قائمة الحواف المتجاورة. تزور النسخة التكرارية العقد من الرسم البياني المثال بالترتيب التالي: A، B، D، F، E، C، G. أما النسخة غير التكرارية فتزور العقد بالترتيب التالي: A، E، F، B، D، C، G.

يشبه التنفيذ غير التكراري البحث بالعرض أولاً، ولكنه يختلف عنه في جانبين:

1. يستخدم مكدسًا بدلًا من طابور، و
2. يؤدي ذلك إلى تأخير التحقق مما إذا تم اكتشاف رأس ما حتى يتم إخراج الرأس من المكدس بدلاً من إجراء هذا الفحص قبل إضافة الرأس.

إذا كانت G شجرة ، فإن استبدال طابور خوارزمية البحث بالعرض أولاً بمكدس سيؤدي إلى خوارزمية بحث بالعمق أولاً. بالنسبة للرسوم البيانية العامة، فإن استبدال مكدس تطبيق البحث بالعمق أولاً التكراري بطابور سيؤدي أيضاً إلى خوارزمية بحث بالعرض أولاً، وإن كانت غير قياسية إلى حد ما. ^{[ 7 ]}

هناك تطبيق آخر محتمل للبحث التكراري العميق أولاً يستخدم مكدسًا من مُكرِّرات قائمة جيران العقدة، بدلاً من مكدس العقد. وهذا يُنتج نفس عملية الاجتياز التي يُنتجها البحث التكراري العميق أولاً. ^{[ 8 ]}

الإجراء DFS_iterative( G , v ) هو: ليكن S مكدسًا قم بتصنيف v على أنه مكتشف ، ثم أضف مؤشر G.adjacentEdges ( v ) إلى S. طالما أن S غير فارغة ، إذا كان S.peek ().hasNext() موجودًا، فقم بتعيين w إلى S.peek ().next(). إذا لم يتم تصنيف w على أنه مكتشف، فقم بتصنيفه على أنه مكتشف، ثم أضف مؤشر G.adjacentEdges ( w ) إلى S. وإلا، فقم بإزالة العنصر من S.

تتضمن الخوارزميات التي تستخدم البحث العميق أولاً كعنصر أساسي ما يلي:

• إيجاد المكونات المتصلة .
• الفرز الطوبولوجي .
• إيجاد المكونات المتصلة بـ 2 (الحواف أو الرؤوس).
• إيجاد المكونات المتصلة بثلاثة (حواف أو رؤوس).
• إيجاد جسور الرسم البياني.
• توليد الكلمات من أجل رسم مجموعة النهاية لمجموعة ما .
• إيجاد المكونات المترابطة بقوة .
• تحديد ما إذا كان نوع ما أقرب إلى نوع آخر في شجرة التطور الوراثي.
• اختبار التسطيح . ^{[ 9 ] [ 10 ]}
• حل الألغاز التي لها حل واحد فقط، مثل المتاهات . (يمكن تكييف خوارزمية البحث العمقي أولاً لإيجاد جميع حلول المتاهة عن طريق تضمين العقد الموجودة على المسار الحالي فقط في المجموعة التي تمت زيارتها.)
• قد يستخدم توليد المتاهات خوارزمية البحث العميق العشوائي.
• إيجاد الاتصال الثنائي في الرسوم البيانية .
• ^{[ 11 ]} يتم تقاسم خلافة العرش بين ممالك الكومنولث .

قام جون ريف بدراسة التعقيد الحسابي لخوارزمية البحث العمقي أولاً (DFS) . وبشكل أدق، بالنظر إلى رسم بياني${\displaystyle G}$، يترك${\displaystyle O=(v_{1},\dots ,v_{n})}$ليكن هذا الترتيب الذي تحسبه خوارزمية البحث العميق التكرارية القياسية. يُسمى هذا الترتيب بترتيب البحث العميق المعجمي. درس جون ريف تعقيد حساب ترتيب البحث العميق المعجمي، بالنظر إلى رسم بياني ومصدر. نسخة القرار من المشكلة (اختبار ما إذا كان رأس u يقع قبل رأس v في هذا الترتيب) هي مسألة P- كاملة ، ^{[ 12 ]} مما يعني أنها "كابوس للمعالجة المتوازية ". ^{[ 13 ] : 189}

يمكن حساب ترتيب البحث العميق أولاً (ليس بالضرورة الترتيب المعجمي) بواسطة خوارزمية متوازية عشوائية في فئة التعقيد RNC . ^{[ 14 ]} وحتى عام 1997، ظل من غير المعروف ما إذا كان من الممكن إنشاء اجتياز عميق أولاً بواسطة خوارزمية متوازية حتمية، في فئة التعقيد NC . ^{[ 15 ]}

• البحث بالعرض أولاً – خوارزمية للبحث في عقد الرسم البياني 
• البحث التكراري العميق أولاً – استراتيجية البحث الشجري 
• لعبة البحث – لعبة ثنائية اللاعبين ذات محصلة صفرية 
• اجتياز الشجرة – لمزيد من التفاصيل حول اجتياز الشجرة بالترتيب المسبق، والترتيب الداخلي، والترتيب اللاحق، اجتياز الشجرة بالترتيب العمق أولاً

• هياكل البيانات المفتوحة - القسم 12.3.2 - البحث العميق أولاً ، بات مورين
• مكتبة Boost Graph للغة C++: البحث العميق أولاً
• رسوم متحركة للبحث العميق أولاً (للرسم البياني الموجه)
• البحث العميق أولاً والبحث العرضي أولاً: الشرح والرمز
• شرح توضيحي لخوارزمية البحث العميق أولاً (تطبيقات بلغة جافا وسي++)
• YAGSBPL – مكتبة C++ قائمة على القوالب للبحث في الرسوم البيانية والتخطيط
• تصور البحث العميق أولاً