خوارزمية ديفيس-بوتنام-لوفلاند
المحتويات

قبل الخوض في التفاصيل، خوارزمية ديفيس–بوتنام–لوغيمان–لوفلاند هي خوارزمية بحث كاملة تعتمد على الاسترجاع الخلفي، وتُستعمل في مجالَي المنطق وعلوم الحاسوب لحل مسألة الاستيفاء المنطقي لحساب القضايا المكتوبة على الصيغة العادية التوافقية. وتعرض الأقسام التالية جوانب أخرى من الموضوع.
في هذا الإطار، طُورت الخوارزمية في عام 1961 على يد مارتن ديفيس، وجورج لوغيمان، ودونالد لوفلاند، بوصفها تطويرًا لخوارزمية سابقة تُعرف بـ خوارزمية ديفيس–بوتنام، التي أُقترحت عام 1960 من قِبل ديفيس وهيلاري بوتنام، وكانت تعتمد على أسلوب الاستنتاج بالتوسيط.
وفي السياق ذاته، في بعض الأدبيات الأقدم، كثيرًا ما يُشار إلى هذه الخوارزمية باسم طريقة ديفيس–بوتنام أو "خوارزمية دي بي، رغم أنها تختلف من حيث البنية والآلية. ومن التسميات الأخرى الشائعة مع الحفاظ على التمييز خوارزمية دي إل إل ودي بي إل إل.
التنفيذ والتطبيق
ومن جهة أخرى، في المسابقات الدولية لمشكلات الاستيفاء المنطقي، تصدرت البرامج المعتمدة على هذه الخوارزمية، مثل تشاف زد، وميني سات، المراتب الأولى في نسختي عامي 2004 و2005. كما تُستعمل الخوارزمية على نطاق واسع في تطبيقات أخرى، منها الإثبات الآلي للنظريات، ومسائل الإرضاء وفق نظريات رياضية مختلفة، حيث تُستبدل المتغيرات الافتراضية بصيغ تنتمي إلى نظريات مثل الحساب الخطي أو نظرية الأعداد.
من جانب آخر، ونظرًا لأهميتها، شكّل تطوير محلّلات فعالة لهذه المسألة موضوعًا بحثيًا لسنوات عديدة. يُعد نظام البحث الشامل عبر الفضاء الاحتمالي الذي طُوّر ما بين عامي 1996 و1999 من أوائل التنفيذات التي استعملت خوارزمية ديفيس–بوتنام–لوغيمان–لوفلاند.
ومن جهة أخرى، تُعد مسألة الاستيفاء المنطقي من المسائل المهمة من الناحيتين النظرية والعملية. ففي نظرية التعقيد الحسابي، كانت أول مسألة يُثبت أنها كاملة من نوع كثيرة الحدود غير القطعية، كما أنها تدخل في مجموعة واسعة من التطبيقات، مثل التحقق النموذجي، والتخطيط الآلي والجدولة، والتشخيص في مجال الذكاء الاصطناعي.
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟