البحث غير المطلع هو فئة من خوارزميات البحث ذات الأغراض العامة والتي تعمل بطريقة القوة الغاشمة. لا تحتوي خوارزميات البحث غير المطلعة على معلومات إضافية حول الحالة أو مساحة البحث بخلاف كيفية اجتياز الشجرة، لذلك يُطلق عليها أيضًا اسم البحث الأعمى.
فيما يلي الأنواع المختلفة لخوارزميات البحث غير المطلعة:
1. بحث العرض أولاً:
- يعد بحث العرض الأول هو إستراتيجية البحث الأكثر شيوعًا لاجتياز شجرة أو رسم بياني. تقوم هذه الخوارزمية بالبحث بشكل عريض في شجرة أو رسم بياني، لذلك يُطلق عليها بحث العرض أولاً.
- تبدأ خوارزمية BFS في البحث من العقدة الجذرية للشجرة وتوسع كل العقد اللاحقة عند المستوى الحالي قبل الانتقال إلى العقد من المستوى التالي.
- تعد خوارزمية بحث العرض الأول مثالاً على خوارزمية بحث الرسم البياني العام.
- تم تنفيذ بحث العرض الأول باستخدام بنية بيانات قائمة انتظار FIFO.
مزايا:
- سيوفر BFS حلاً في حالة وجود أي حل.
- إذا كان هناك أكثر من حل لمشكلة معينة، فسوف توفر BFS الحل الأدنى الذي يتطلب أقل عدد من الخطوات.
سلبيات:
- يتطلب الكثير من الذاكرة حيث يجب حفظ كل مستوى من مستويات الشجرة في الذاكرة لتوسيع المستوى التالي.
- يحتاج BFS إلى الكثير من الوقت إذا كان الحل بعيدًا عن العقدة الجذرية.
مثال:
في بنية الشجرة أدناه، أظهرنا اجتياز الشجرة باستخدام خوارزمية BFS من عقدة الجذر S إلى عقدة الهدف K. تجتاز خوارزمية بحث BFS في طبقات، لذلك ستتبع المسار الذي يظهر بالسهم المنقط، و المسار الذي تم اجتيازه سيكون:
S---> A--->B---->C--->D---->G--->H--->E---->F---->I---->K
تعقيد الوقت: يمكن الحصول على التعقيد الزمني لخوارزمية BFS من خلال عدد العقد التي تم اجتيازها في BFS حتى العقدة الأقل عمقًا. حيث d = عمق الحل الضحل و b هي عقدة في كل حالة.
ت (ب) = 1+ب2+ب3+....+ بد= يا (بد)
تعقيد الفضاء: يتم تحديد التعقيد الفضائي لخوارزمية BFS من خلال حجم ذاكرة الحدود وهو O(bد).
الاكتمال: اكتمل BFS، مما يعني أنه إذا كانت عقدة الهدف الأقل عمقًا على عمق محدود، فسيجد BFS حلاً.
الأمثلية: يعد BFS هو الأمثل إذا كانت تكلفة المسار دالة غير متناقصة لعمق العقدة.
2. البحث في العمق أولاً
- بحث العمق الأول هو خوارزمية متكررة لاجتياز بنية بيانات الشجرة أو الرسم البياني.
- ويسمى بحث العمق أولاً لأنه يبدأ من العقدة الجذرية ويتبع كل مسار إلى عقدة العمق الأكبر قبل الانتقال إلى المسار التالي.
- يستخدم DFS بنية بيانات المكدس لتنفيذه.
- تشبه عملية خوارزمية DFS خوارزمية BFS.
ملحوظة: التراجع هو أسلوب خوارزمي لإيجاد جميع الحلول الممكنة باستخدام التكرار.
ميزة:
- يتطلب DFS ذاكرة أقل جدًا لأنه يحتاج فقط إلى تخزين مجموعة من العقد على المسار من العقدة الجذرية إلى العقدة الحالية.
- يستغرق الوصول إلى عقدة الهدف وقتًا أقل من خوارزمية BFS (إذا كانت تسير في المسار الصحيح).
العيب:
- هناك احتمال أن تستمر العديد من الحالات في التكرار، وليس هناك ضمان لإيجاد الحل.
- تستخدم خوارزمية DFS للبحث العميق وفي بعض الأحيان قد تذهب إلى الحلقة اللانهائية.
مثال:
في شجرة البحث أدناه، أظهرنا تدفق بحث العمق أولاً، وسيتبع الترتيب على النحو التالي:
العقدة الجذرية--->العقدة اليسرى ---->العقدة اليمنى.
سيبدأ البحث من العقدة الجذرية S، ثم يجتاز A، ثم B، ثم D وE، وبعد اجتياز E، سوف يتراجع عن الشجرة نظرًا لعدم وجود خليفة آخر لـ E، ولم يتم العثور على عقدة الهدف. بعد التراجع، ستجتاز العقدة C ثم G، وهنا ستنتهي حيث وجدت عقدة الهدف.
الاكتمال: تكتمل خوارزمية بحث DFS ضمن مساحة الحالة المحدودة حيث ستقوم بتوسيع كل عقدة داخل شجرة بحث محدودة.
تعقيد الوقت: سيكون التعقيد الزمني لـ DFS مكافئًا للعقدة التي اجتازتها الخوارزمية. يتم إعطاؤه بواسطة:
تي(ن)= 1+ ن2+ ن3+.........+ نم=يا(نم)
حيث m = أقصى عمق لأي عقدة ويمكن أن يكون هذا أكبر بكثير من d (أصغر عمق للحل)
تعقيد الفضاء: تحتاج خوارزمية DFS إلى تخزين مسار واحد فقط من العقدة الجذرية، وبالتالي فإن تعقيد مساحة DFS يعادل حجم المجموعة الهامشية، وهي عن .
أفضل: تعتبر خوارزمية بحث DFS غير مثالية، لأنها قد تولد عددًا كبيرًا من الخطوات أو تكلفة عالية للوصول إلى عقدة الهدف.
3. خوارزمية البحث محدودة العمق:
تشبه خوارزمية البحث المحدود العمق بحث العمق الأول بحد محدد مسبقًا. يمكن أن يحل البحث المحدود العمق عيب المسار اللانهائي في بحث العمق الأول. في هذه الخوارزمية، سيتم التعامل مع العقدة عند حد العمق لأنها لا تحتوي على عقد لاحقة.
يمكن إنهاء البحث المحدود العمق بشرطين للفشل:
- قيمة الفشل القياسية: تشير إلى أن المشكلة ليس لها أي حل.
- قيمة فشل القطع: لا تحدد أي حل للمشكلة ضمن حد عمق معين.
مزايا:
البحث المحدود العمق فعال في الذاكرة.
سلبيات:
- البحث المحدود العمق له أيضًا عيب عدم الاكتمال.
- وقد لا يكون الحل الأمثل إذا كان للمشكلة أكثر من حل.
مثال:
الاكتمال: تكتمل خوارزمية بحث DLS إذا كان الحل أعلى من حد العمق.
تعقيد الوقت: التعقيد الزمني لخوارزمية DLS هو يا(بℓ) .
ناتاشا دلال
تعقيد الفضاء: التعقيد الفضائي لخوارزمية DLS هو O (بℓ) .
أفضل: يمكن النظر إلى البحث المحدود العمق كحالة خاصة من DFS، كما أنه ليس الأمثل حتى لو كان ℓ>d.
4. خوارزمية البحث ذات التكلفة الموحدة:
البحث ذو التكلفة الموحدة هو خوارزمية بحث تستخدم لاجتياز شجرة أو رسم بياني مرجح. يتم تشغيل هذه الخوارزمية عندما تتوفر تكلفة مختلفة لكل حافة. الهدف الأساسي للبحث ذو التكلفة الموحدة هو العثور على مسار إلى عقدة الهدف التي لديها أقل تكلفة تراكمية. يقوم البحث ذو التكلفة الموحدة بتوسيع العقد وفقًا لتكاليف مسارها من العقدة الجذرية. يمكن استخدامه لحل أي رسم بياني/شجرة حيث تكون التكلفة المثالية مطلوبة. يتم تنفيذ خوارزمية بحث موحدة التكلفة من خلال قائمة انتظار الأولوية. فهو يعطي الأولوية القصوى لأقل تكلفة تراكمية. البحث عن التكلفة الموحدة يعادل خوارزمية BFS إذا كانت تكلفة المسار لجميع الحواف هي نفسها.
مزايا:
- يعد البحث عن التكلفة الموحدة هو الأمثل لأنه في كل ولاية يتم اختيار المسار الأقل تكلفة.
سلبيات:
- لا يهتم بعدد الخطوات التي يتضمنها البحث ويهتم فقط بتكلفة المسار. ولهذا السبب قد تكون هذه الخوارزمية عالقة في حلقة لا نهائية.
مثال:
الاكتمال:
اكتمل البحث عن التكلفة الموحدة، على سبيل المثال، إذا كان هناك حل، فسوف تجده UCS.
تعقيد الوقت:
دع ج* هي تكلفة الحل الأمثل ، و ه هي كل خطوة للاقتراب من عقدة الهدف. ثم يكون عدد الخطوات = C*/ε+1. لقد اتخذنا هنا +1، حيث نبدأ من الحالة 0 وننتهي إلى C*/ε.
ومن ثم، فإن التعقيد الزمني الأسوأ للبحث ذو التكلفة الموحدة هو يا(ب1 + [ج*/ه])/ .
تعقيد الفضاء:
نفس المنطق ينطبق على التعقيد الفضائي، لذا فإن التعقيد الفضائي الأسوأ للبحث ذو التكلفة الموحدة هو يا(ب1 + [ج*/ه]) .
أفضل:
يعد البحث ذو التكلفة الموحدة هو الأمثل دائمًا لأنه يحدد فقط المسار بأقل تكلفة للمسار.
5. التعميق التكراري - البحث الأول:
خوارزمية التعميق التكراري عبارة عن مزيج من خوارزميات DFS وBFS. تكتشف خوارزمية البحث هذه أفضل حد للعمق وتقوم بذلك عن طريق زيادة الحد تدريجيًا حتى يتم العثور على الهدف.
تقوم هذه الخوارزمية بإجراء بحث العمق أولاً حتى 'حد العمق' المحدد، وتستمر في زيادة حد العمق بعد كل تكرار حتى يتم العثور على عقدة الهدف.
تجمع خوارزمية البحث هذه بين فوائد البحث السريع لبحث العرض الأول وكفاءة ذاكرة بحث العمق أولاً.
تعتبر خوارزمية البحث التكراري مفيدة للبحث غير المدروس عندما تكون مساحة البحث كبيرة وعمق عقدة الهدف غير معروف.
مزايا:
- فهو يجمع بين فوائد خوارزمية بحث BFS وDFS من حيث سرعة البحث وكفاءة الذاكرة.
سلبيات:
- العيب الرئيسي لـ IDFFS هو أنه يكرر كل أعمال المرحلة السابقة.
مثال:
يُظهر هيكل الشجرة التالي البحث التكراري للعمق أولاً. تقوم خوارزمية IDFFS بتكرارات مختلفة حتى لا تجد عقدة الهدف. يتم إعطاء التكرار الذي تقوم به الخوارزمية على النحو التالي:
التكرار الأول -----> أ
التكرار الثاني ----> أ، ب، ج
التكرار الثالث ------> أ، ب، د، ه، ج، و، ز
التكرار الرابع ------> أ، ب، د، ح، أنا، ه، ج، و، ك، ز
في التكرار الرابع، سوف تجد الخوارزمية عقدة الهدف.
الاكتمال:
تكتمل هذه الخوارزمية إذا كان عامل التفرع محدودًا.
تعقيد الوقت:
لنفترض أن b هو عامل التفرع والعمق هو d، ثم التعقيد الزمني الأسوأ هو يا(بد) .
تعقيد الفضاء:
سيكون التعقيد المكاني لـ IDFFS يا (دينار بحريني) .
أفضل:
تعتبر خوارزمية IDFS مثالية إذا كانت تكلفة المسار دالة غير متناقصة لعمق العقدة.
6. خوارزمية البحث ثنائية الاتجاه:
تقوم خوارزمية البحث ثنائي الاتجاه بتشغيل عمليتي بحث متزامنتين، حالة أولية لنموذج واحد تسمى البحث الأمامي والأخرى من عقدة الهدف تسمى البحث الخلفي، للعثور على عقدة الهدف. يستبدل البحث ثنائي الاتجاه رسمًا بيانيًا واحدًا للبحث برسمين فرعيين صغيرين يبدأ أحدهما البحث من قمة أولية والآخر يبدأ من قمة الهدف. يتوقف البحث عندما يتقاطع هذان الرسمان البيانيان مع بعضهما البعض.
يمكن أن يستخدم البحث ثنائي الاتجاه تقنيات البحث مثل BFS، وDFS، وDLS، وما إلى ذلك.
مزايا:
- البحث ثنائي الاتجاه سريع.
- يتطلب البحث ثنائي الاتجاه ذاكرة أقل
سلبيات:
- تنفيذ شجرة البحث ثنائية الاتجاه أمر صعب.
مثال:
في شجرة البحث أدناه، تم تطبيق خوارزمية البحث ثنائي الاتجاه. تقسم هذه الخوارزمية رسمًا بيانيًا/شجرة واحدة إلى رسمين بيانيين فرعيين. يبدأ العبور من العقدة 1 في الاتجاه الأمامي ويبدأ من عقدة الهدف 16 في الاتجاه الخلفي.
تنتهي الخوارزمية عند العقدة 9 حيث يلتقي عمليتا البحث.
الاكتمال: يكتمل البحث ثنائي الاتجاه إذا استخدمنا BFS في كلا البحثين.
تعقيد الوقت: التعقيد الزمني للبحث ثنائي الاتجاه باستخدام BFS هو يا(بد) .
جافا فرز الفقاعة
تعقيد الفضاء: التعقيد المكاني للبحث ثنائي الاتجاه هو يا(بد) .
أفضل: البحث ثنائي الاتجاه هو الأمثل.