كيفية الحصول على قيم 2 سبت

Question

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

كيف يمكنني العثور بكفاءة على مجموعة قانونية من القيم التي ستفي بمثيل 2-SAT؟

أنا أعمل في C ++ مع مكتبة Boost وسأقدر الكود الذي يمكن دمجه بسهولة.

شكرا لك مقدما

Answer 1

إذا كان لديك خوارزمية قرار لاكتشاف ما إذا كان هناك مهمة صالحة لـ 2-SAT ، فيمكنك استخدام ذلك لمعرفة المهمة الفعلية بالفعل.

أول خوارزمية قرار 2-SAT على التعبير كله. افترض أنها تقول أن هناك مهمة صالحة.

الآن إذا كان X_1 حرفيًا ، فقم بتعيين x_1 ليكون 0. الآن احسب 2-SAT للتعبير الناتج (سيتعين عليك تعيين بعض الحرفيات الأخرى بسبب هذا ، على سبيل المثال يظهر x_1 أو x_3 ، تحتاج أيضًا إلى تعيين x_3 إلى 1).

إذا كان الانفصال الناتج 2 مريض ، فيمكنك أن تأخذ x_1 ليكون 0 ، وإلا خذ x_1 إلى 1.

الآن يمكنك العثور على هذا عن كل حرفي.

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

يمكنك العثور على مزيد من المعلومات هنا: http://en.wikipedia.org/wiki/2-satisbibility

الجزء ذي الصلة:

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

الحرفية في كل مكون متصل بقوة إما كل الصفر أو كل 1.

Answer 2

هناك خوارزمية واحدة على الأقل تسرد جميع الحلول لمشكلة 2-SAT ، بقلم توماس فيدر: http://www.springerlink.com/content/j582276p06276l12/