GRASP: خوارزمية بحث لرضا الاقتراحات

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