قضايا التنفيذ في مشكلة ارتياح 2

Question

أريد تطبيق مشكلة 2-SAT مقابل 100000 حرفي. لذلك سيكون هناك 200000 رأس. لذلك أنا عالق على الحصول على مجموعة من جميع القمم القابلة للوصول من كل قمة، تعقيد الفضاء O(200000^2) وهو أمر غير قابل للإصلاح لذا يرجى اقتراح حلا لهذا. ويرجى رمي بعض الضوء على التنفيذ الفعال لمشكلة 2-SAT.

Answer 1

من ويكيبيديا:

... 2-leassibility يمكن حلها في الوقت متعدد الحدود. كما Aspvall، Plass & Tarjan (1979) لوحظ، مثيل إرضاء 2 قابلة للحل إذا وتمكن كل متغير من المثيل فقط إلى مكون متصل بشدة من الرسم البياني للتأديب من نفي نفس المتغير. نظرا لأنه قد يتم العثور على مكونات متصلة بشدة في الوقت الخطي من خلال خوارزمية تعتمد على البحث الأول في العمق، فإن نفس الوقت الخطي المرتبط ينطبق أيضا على رضايا 2.

لن أدعي أن أفهم معظم هذه الفقرة، لكنها ستظهر ذلك يكون خوارزمية يمكن استخدامها لحل مشكلة 2 SAT، وهي موصوفة ضمن المستند المشار إليه (خوارزمية خطية لاختبار حقيقة بعض الصيغ المنطقي الكمي). يبدو أنه يمكن شراؤها عبر الإنترنت لمدة 20 دولار أمريكي. لست متأكدا مما إذا كان هذا مفيدا أم لا، ولكن هناك!

تحديث: يمكن العثور على PDF مجانا من نفس المستند هنا. وبعد الائتمان يذهب إلى liori. لهذا البحث.

Answer 2

هذا الخيط بأكمله مبهجة بعض الشيء. نعم، يمكن للمرء أن يحل 2 جلست في الوقت الخطي، ولكن لا - لا يمكنك حلها لهذا المتغيرات العديدة. الوقت المناسب لحل 2-SAT هو خطي فيما يتعلق بعدد الآثار، والتي يمكن أن تصل إلى 200 000 متغيرات تصل إلى (200000 * 199999) / 2 علاوة على ذلك، إذا كنت تستخدم هذا الحل، فستحتاج إلى نفس كمية الذاكرة وبعد هناك حل آخر (لا يستخدم مكونات متصلة بشدة أبطأ ولكن لا يحتاج إلى الكثير من الذاكرة).