خوارزمية البحث

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

تُعدّ خوارزميات البحث المحلي فئة فرعية مهمة ، إذ تنظر إلى عناصر فضاء البحث على أنها رؤوس رسم بياني، وتُحدد حوافها بمجموعة من القواعد الاستدلالية المناسبة للحالة. وتقوم هذه الخوارزميات بمسح الفضاء بالانتقال من عنصر إلى آخر على طول الحواف، على سبيل المثال وفقًا لمعيار الانحدار الأسرع أو معيار الأفضل أولًا ، أو في بحث عشوائي . وتشمل هذه الفئة مجموعة واسعة من أساليب الاستدلال الميتاهوريستية العامة ، مثل التلدين المحاكي ، والبحث المحظور ، وفرق A ، ^{[ 7 ]} والبرمجة الجينية ، التي تجمع بين قواعد استدلالية عشوائية بطرق محددة. أما عكس البحث المحلي فهو أساليب البحث الشامل. ويُمكن تطبيق هذا الأسلوب عندما يكون فضاء البحث غير محدود، وتكون جميع جوانب الشبكة المُعطاة متاحة للكيان الذي يُشغّل خوارزمية البحث. ^{[ 8 ]}

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

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

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

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

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

توجد أيضًا طرق بحث مصممة خصيصًا للحواسيب الكمومية ، مثل خوارزمية غروفر ، وهي نظريًا أسرع من البحث الخطي أو البحث الشامل حتى بدون استخدام هياكل البيانات أو الطرق الاستدلالية. ورغم أن الأفكار والتطبيقات الكامنة وراء الحواسيب الكمومية لا تزال نظرية تمامًا، فقد أُجريت دراسات باستخدام خوارزميات مثل خوارزمية غروفر، والتي تحاكي بدقة النسخ الفيزيائية الافتراضية لأنظمة الحوسبة الكمومية. ^{[ 9 ]}