Maxsat باستخدام خوارزمية DPLL؟

Question

من الممكن العودة من خوارزمية DPLL M كحد أقصى لمشكلة ماكس السبت؟:

لدي عينة:

href="https://gist.github.com/davefernig/e670bda722d558817f2ba0e90ebce66f" rel="nofollow noreferrer"> https://gist.github.com/davefernig/e670bda722d558817f2ba0e90ebce66f

يمكننا تعديل التكرار لإرجاع نتيجة Max-Sat؟

الموارد: https://en.wikipedia.org/wiki/dpll_algorithm

Answer 1

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

قد ترتبط مشكلة Maxsat بإيجاد الفمويلات الفرعية غير المستهلكة غير مرضية (SUMES) للمثيل.تحديد ما إذا كانت مجموعة من البنود هي مشكلة DP كاملة.من المتوقع أن يكون هذا أكثر صعوبة من اكتمال NP، لذلك من غير المرجح أن يكون تعديل DPLL لإعادة الحلول الجزئية أمرا مثمرا.بالنظر إلى أن الفئة DP موجودة في $ \ delta ^ po2 $ قد تقوم بإقامة مخطط يستدعي DPLL (أو الخوارزميات ذات الصلة) عدد متعدد الحدود من المرات لإنتاج Maxsatالنتيجة.