مشكلة الإرضاء الأقصى

الموسوعة الحرة

في نظرية التعقيد الحسابي ، تُعرف مسألة الإرضاء الأقصى ( MAX-SAT ) بأنها مسألة تحديد الحد الأقصى لعدد البنود في صيغة منطقية معينة بصيغة الاقتران العادية ، والتي يمكن جعلها صحيحة من خلال تعيين قيم منطقية لمتغيرات الصيغة. وهي تعميم لمسألة الإرضاء المنطقي ، التي تسأل عما إذا كان هناك تعيين منطقي يجعل جميع البنود صحيحة.

مثال

صيغة الشكل الطبيعي الاقتراني

(x0∨x1)∧(x0∨¬x1)∧(¬x0∨x1)∧(¬x0∨¬x1){\displaystyle (x_{0}\lor x_{1})\land (x_{0}\lor \lnot x_{1})\land (\lnot x_{0}\lor x_{1})\land (\lnot x_{0}\lor \lnot x_{1})}

لا يمكن تحقيق هذه الصيغة: بغض النظر عن قيم الصواب المُسندة لمتغيريها، ستكون واحدة على الأقل من بنودها الأربعة خاطئة. مع ذلك، من الممكن إسناد قيم الصواب بطريقة تجعل ثلاثة من البنود الأربعة صحيحة؛ بل إن كل إسناد لقيم الصواب سيؤدي إلى ذلك. لذا، إذا عُرضت هذه الصيغة كمثال على مسألة MAX-SAT، فإن حل المسألة هو العدد ثلاثة.

صلابة

تُعد مشكلة MAX-SAT مشكلة OptP-complete، [ 1 ] وبالتالي فهي مشكلة NP-hard (كمشكلة قرار)، لأن حلها يؤدي بسهولة إلى حل مشكلة الإرضاء المنطقي ، وهي مشكلة NP-complete .

من الصعب أيضًا إيجاد حل تقريبي للمسألة يحقق عددًا من الشروط ضمن نسبة تقريب مضمونة للحل الأمثل. بتعبير أدق، المسألة كاملة من فئة APX ، وبالتالي لا تقبل مخطط تقريبي في زمن متعدد الحدود إلا إذا كانت P = NP. [ 2 ] [ 3 ] [ 4 ]

أقصى شبع مُرجّح

بشكلٍ أعم، يمكن تعريف نسخة موزونة من مسألة MAX-SAT كما يلي: بالنظر إلى صيغة رياضية اقترانية ذات أوزان غير سالبة مُخصصة لكل بند، ابحث عن قيم الصواب لمتغيراتها التي تُعظم الوزن المُجمع للبنود المُحققة. تُعد مسألة MAX-SAT حالةً من مسائل MAX-SAT الموزونة حيث تكون جميع الأوزان تساوي 1. [ 5 ] [ 6 ] [ 7 ]

خوارزميات التقريب

نصف القيمة التقريبية

يُعطي تعيين كل متغير عشوائيًا على أنه صحيح باحتمالية 1/2 تقريبًا متوقعًا من الدرجة 2. وبشكل أدق، إذا احتوى كل بند على k متغيرًا على الأقل ، فإن هذا يُعطي تقريبًا من الدرجة (1 − 2 − k ). [ 8 ] يمكن إزالة العشوائية من هذه الخوارزمية باستخدام طريقة الاحتمالات الشرطية . [ 9 ]

تقريب (1-1/ e )

يمكن أيضًا التعبير عن مسألة MAX-SAT باستخدام برنامج خطي صحيح (ILP). لنفترض وجود صيغة اقترانية عادية F بمتغيرات x₁ , x₂ , ..., xₙ ، ولنرمز ببنود F إلى C. لكل بند c في C ، لنرمز بمجموعتي المتغيرات غير المنفية في c و Sₒc على التوالي . تتوافق المتغيرات y و x في برنامج ILP مع متغيرات الصيغة F ، بينما تتوافق المتغيرات z و c مع البنود . برنامج ILP هو كما يلي:

أقصى∑ج∈جwج⋅zج{\displaystyle \sum _{c\in C}w_{c}\cdot z_{c}}(زيادة وزن البنود المستوفاة)
رهناً بـzج≤∑x∈Sج+yx+∑x∈Sج-(1-yx){\displaystyle z_{c}\leq \sum _{x\in S_{c}^{+}}y_{x}+\sum _{x\in S_{c}^{-}}(1-y_{x})}للجميعج∈ج{\displaystyle c\in C}(يكون الشرط صحيحاً إذا وفقط إذا كان يحتوي على متغير صحيح غير منفي أو متغير خاطئ منفي)
zج∈{0،1}{\displaystyle z_{c}\in \{0,1\}}للجميعج∈ج{\displaystyle c\in C}.(كل بند إما مستوفى أو غير مستوفى)
yx∈{0،1}{\displaystyle y_{x}\in \{0,1\}}للجميعx∈F{\displaystyle x\in F}.(كل متغير إما صحيح أو خاطئ)

يمكن تبسيط البرنامج أعلاه إلى البرنامج الخطي التالي L :

أقصى∑ج∈جwج⋅zج{\displaystyle \sum _{c\in C}w_{c}\cdot z_{c}}(زيادة وزن البنود المستوفاة)
رهناً بـzج≤∑x∈Sج+yx+∑x∈Sج-(1-yx){\displaystyle z_{c}\leq \sum _{x\in S_{c}^{+}}y_{x}+\sum _{x\in S_{c}^{-}}(1-y_{x})}للجميعج∈ج{\displaystyle c\in C}(يكون الشرط صحيحاً إذا وفقط إذا كان يحتوي على متغير صحيح غير منفي أو متغير خاطئ منفي)
0≤zج≤1{\displaystyle 0\leq z_{c}\leq 1}للجميعج∈ج{\displaystyle c\in C}.
0≤yx≤1{\displaystyle 0\leq y_{x}\leq 1}للجميعx∈F{\displaystyle x\in F}.

الخوارزمية التالية التي تستخدم هذا الاسترخاء هي تقريب متوقع (1-1/ e ): [ 10 ]

  1. حل البرنامج الخطي L واحصل على الحل O
  2. اجعل المتغير x صحيحًا باحتمالية y x حيث y x هي القيمة المعطاة في O.

يمكن أيضًا إزالة العشوائية من هذه الخوارزمية باستخدام طريقة الاحتمالات الشرطية.

تقريب 3/4

تُحقق خوارزمية التقريب 1/2 نتائج أفضل عندما تكون البنود كبيرة، بينما تُحقق خوارزمية التقريب (1-1/ e ) نتائج أفضل عندما تكون البنود صغيرة. ويمكن دمجهما كما يلي:

  1. قم بتشغيل خوارزمية التقريب 1/2 (غير العشوائية) للحصول على تعيين الحقيقة X.
  2. قم بتشغيل التقريب (1-1/e) (غير العشوائي) للحصول على تعيين الحقيقة Y.
  3. قم بإخراج أي من X أو Y يحقق أقصى وزن للشروط المستوفاة.

هذا تقريب حتمي بعامل (3/4). [ 11 ]

مثال

في الصيغة

F=(x∨y)⏟وزن 1∧(x∨¬y)⏟وزن 1∧(¬x∨z)⏟وزن 2+ϵ{\displaystyle F=\underbrace {(x\lor y)} _{{\text{weight }}1}\land \underbrace {(x\lor \lnot y)} _{{\text{weight }}1}\land \underbrace {(\lnot x\lor z)} _{{\text{weight }}2+\epsilon }}

أينϵ>0{\displaystyle \epsilon >0}، سيُعيّن التقريب (1-1/ e ) كل متغير إلى القيمة "صحيح" باحتمالية 1/2، وبالتالي سيتصرف بشكل مطابق للتقريب 1/2. بافتراض أن تعيين قيمة x يتم أولاً أثناء عملية إزالة العشوائية، فإن الخوارزميات التي تمت إزالة عشوائيتها ستختار حلاً بوزن إجمالي3+ϵ{\displaystyle 3+\epsilon }بينما الحل الأمثل له وزن4+ϵ{\displaystyle 4+\epsilon }[ 12 ]​

مثال رائع من الفن

يعود الفضل في أحدث خوارزمية إلى أفيدور، بيركوفيتش، وزويك، [ 13 ] [ 14 ] ونسبة تقريبها 0.7968. كما قدموا خوارزمية أخرى يُعتقد أن نسبة تقريبها 0.8353.

حلول

طُوِّرت العديد من الحلول الدقيقة لمسألة MAX-SAT خلال السنوات الأخيرة، وعُرض الكثير منها في مؤتمر SAT الشهير، المتخصص في مسألة إرضاء الصيغ المنطقية والمشاكل ذات الصلة. في عام 2006، استضاف مؤتمر SAT أول تقييم لمسألة MAX-SAT ، حيث قارن أداء الحلول العملية لها، كما فعل سابقًا مع مسألة إرضاء الصيغ المنطقية الزائفة ومسألة الصيغة المنطقية الكمية . نظرًا لصعوبة حل مسألة MAX-SAT ذات الحجم الكبير، لا يمكن حلها بدقة بشكل عام، وغالبًا ما يُضطر إلى اللجوء إلى خوارزميات التقريب والأساليب الاستدلالية [ 15 ].

تم تقديم العديد من برامج الحل إلى تقييمات Max-SAT الأخيرة:

حالات خاصة

تُعدّ مسألة MAX-SAT إحدى امتدادات التحسين لمسألة إرضاء الصيغ المنطقية ، وهي مسألة تحديد ما إذا كان بالإمكان تعيين متغيرات صيغة منطقية معينة بطريقة تجعل الصيغة تُقيّم إلى القيمة TRUE. إذا اقتصرت الشروط على متغيرين على الأكثر، كما في مسألة إرضاء الصيغتين ، نحصل على مسألة MAX-2SAT . أما إذا اقتصرت على ثلاثة متغيرات على الأكثر لكل شرط، كما في مسألة إرضاء الصيغ الثلاث ، فنحصل على مسألة MAX-3SAT .

توجد العديد من المشاكل المتعلقة بإمكانية إرضاء الصيغ المنطقية ذات الشكل الطبيعي الاقتراني.

  • مشاكل اتخاذ القرار :
  • مسائل التحسين، حيث يكون الهدف هو زيادة عدد البنود التي يتم استيفاؤها إلى أقصى حد:
    • MAX-SAT، والنسخة الموزونة المقابلة لها Weighted MAX-SAT
    • MAX- k SAT، حيث يحتوي كل بند على k متغير بالضبط:
    • تُطرح مسألة إمكانية الإرضاء الجزئي الأقصى (PMAX-SAT) سؤالاً حول الحد الأقصى لعدد البنود التي يمكن تحقيقها من خلال أي تخصيص لمجموعة فرعية معينة من البنود. ويجب تحقيق بقية البنود.
    • تُطرح مسألة الإرضاء المرن (soft-SAT)، عند إعطاء مجموعة من مسائل الإرضاء المرن، سؤالاً حول الحد الأقصى لعدد تلك المسائل التي يمكن إرضاؤها بأي تخصيص. [ 16 ]
    • مشكلة الحد الأدنى من إمكانية الإرضاء.
  • يمكن توسيع مسألة MAX-SAT لتشمل الحالة التي تنتمي فيها متغيرات مسألة إرضاء القيود إلى مجموعة الأعداد الحقيقية. وتتلخص المسألة في إيجاد أصغر قيمة لـ q بحيث لا يكون تقاطع القيود المُرخى q فارغًا. [ 17 ]

انظر أيضاً

مراجع

  1. ↑ م. كرينتل (1988). "تعقيد مسائل التحسين". مجلة علوم الحاسوب والنظم . 36 (3): 490-509 . doi : 10.1016/0022-0000(88)90039-6 . hdl : 1813/6559 .
  2. ↑ مارك كرينتل. تعقيد مسائل التحسين . وقائع مؤتمر STOC '86. 1986.
  3. ↑ كريستوس باباديميتريو. التعقيد الحسابي. أديسون-ويسلي، 1994.
  4. ↑ كوهين، كوبر، جيفونز. توصيف كامل للتعقيد في مسائل تحسين القيود المنطقية . CP 2004.
  5. ↑ فازيراني 2001 ، ص 131.
  6. ↑ بورشرز، برايان؛ فورمان، جوديث (1998-12-01). "خوارزمية دقيقة ثنائية المراحل لمسائل MAX-SAT و MAX-SAT الموزونة". مجلة التحسين التوافقي . 2 (4): 299-306 . doi : 10.1023/A:1009725216438 . ISSN 1382-6905 . S2CID 6736614 .  
  7. ↑ دو، دينغزو؛ غو، جون؛ باردالوس، بانوس م. (1997-01-01). مسألة الإرضاء: النظرية والتطبيقات : ورشة عمل DIMACS، 11-13 مارس 1996. الجمعية الرياضية الأمريكية. ص 393. ISBN   9780821870808.
  8. ^ وزيراني 2001 ، ليما 16.2.
  9. ^ وزيراني 2001 ، القسم 16.2.
  10. ↑ فازيراني 2001 ، ص 136.
  11. ^ فازيراني 2001 ، النظرية 16.9.
  12. ^ وزيراني 2001 ، مثال 16.11.
  13. ↑ أفيدور، آدي؛ بيركوفيتش، إيدو؛ زويك، أوري (2006). "خوارزميات تقريب محسّنة لـ MAX NAE-SAT وMAX SAT". التقريب والخوارزميات عبر الإنترنت . المجلد 3879. برلين، هايدلبرغ: سبرينغر برلين هايدلبرغ. الصفحات 27-40 . doi : 10.1007/11671411_3 . ISBN   978-3-540-32207-8.
  14. ↑ ماكاريشيف، كونستانتين؛ ماكاريشيف، يوري (2017). "خوارزميات التقريب لمسائل إرضاء القيود" . Drops-Idn/V2/Document/10.4230/Dfu.vol7.15301.287 : 39 صفحة، 753340 بايت. doi : 10.4230/DFU.VOL7.15301.287 . ISSN 1868-8977 . 
  15. ↑ باتيتي، روبرتو؛ بروتاسي، ماركو (1998). "الخوارزميات التقريبية والأساليب الاستدلالية لمسألة MAX-SAT" . دليل التحسين التوافقي . ص 77-148 . doi : 10.1007/978-1-4613-0303-9_2 . ISBN  978-1-4613-7987-4.
  16. ↑ جوزيب أرجيليتش وفيليب مانيا. حلول Max-SAT الدقيقة للمشاكل المقيدة للغاية . في مجلة الاستدلال 12(4) ص 375-392. سبرينغر، 2006.
  17. ↑ جاولين، ل.؛ والتر، إ. (2002). "تقدير مينيمكس غير خطي قوي مضمون" (ملف PDF) . معاملات IEEE في التحكم الآلي . 47 (11): 1857-1864 . doi : 10.1109/TAC.2002.804479 .