خوارزمية بحث

في علم الحاسوب، خوارزمية بحث هي خوارزمية لإيجاد عنصر مع خصائص معينة في مجموعة من العناصر.^[1] قد تكون العناصر محفوظة بشكل فردي كسجلات في قاعدة بيانات؛ أو بالإمكان ان تكون عناصر فراغ بحثي محدد بواسطة صيغة رياضية، على سبيل المثال، جذور معادلة مع متغيرات صحيحة؛ أو مزيج من الاثنين، مثل دوائر هاملتون في رسم بياني.

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

عندما تكون البيانات مرتبة، بالإمكان تحسين البحث بصورة كبيرة عن طريق استخدام البحث الثنائي.

تطبيقات خوارزميات البحث

تُستخدم خوارزميات البحث في مجموعة واسعة من المجالات لحل المشكلات التي تتطلب إيجاد حل مثالي أو مقبول من بين مجموعة كبيرة من الخيارات. تشمل بعض التطبيقات المحددة ما يلي:^[2]

مشاكل الاستمثال التوافقي، تهدف هذه المشاكل إلى إيجاد أفضل حل ممكن من مجموعة محدودة من الخيارات. ومن أمثلتها:

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

مشاكل تلبية القيود، تُعنى هذه المشاكل بإيجاد حالة تحقق مجموعة من الشروط أو القيود. ومن أمثلتها:

مشكلة مبرهنة الألوان الأربعة: إسناد ألوان لمناطق الخريطة بحيث لا تتجاور منطقتان لهما نفس اللون.
ملء ألغاز سودوكو أو الكلمات المتقاطعة: إيجاد الأرقام أو الكلمات التي تفي بجميع قواعد اللغز.

تطبيقات متنوعة

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

انظر أيضا

بحث شامل
خوارزمية بحث ثنائي
شجرة بحث ثنائية
خوارزمية ترتيب ضرورية لبعض خوارزميات البحث
محرك بحث

المراجع

↑ "معلومات عن خوارزمية بحث على موقع babelnet.org". babelnet.org. مؤرشف من الأصل في 2019-12-16.
↑ Taillard, Éric D. (2023). Taillard, Éric D. (ed.). A Short List of Combinatorial Optimization Problems (بالإنجليزية). Cham: Springer International Publishing. pp. 31–61. DOI:10.1007/978-3-031-13714-3_2. ISBN:978-3-031-13714-3.

دونالد كانوث فن برمجة الحاسوب. المجلد 3: البحث والترتيب. ISBN 0-201-89685-0.

[1] "معلومات عن خوارزمية بحث على موقع babelnet.org". babelnet.org. مؤرشف من الأصل في 2019-12-16.

[2] Taillard, Éric D. (2023). Taillard, Éric D. (ed.). A Short List of Combinatorial Optimization Problems (بالإنجليزية). Cham: Springer International Publishing. pp. 31–61. DOI:10.1007/978-3-031-13714-3_2. ISBN:978-3-031-13714-3.

[1]

[2]