مشكلة إرضاء القيود المرجحة

📅 آخر تحديث: ٣١ يوليو ٢٠٢٦
✍️ نُشر في: ٣١ يوليو ٢٠٢٦
📷 يحتوي على 23 صور
الموسوعة الحرة

في مجال الذكاء الاصطناعي وبحوث العمليات ، تُعدّ مسألة إرضاء القيود الموزونة ( WCSP )، والمعروفة أيضًا بمسألة إرضاء القيود المُقَيَّمة ( VCSP )، تعميمًا لمسألة إرضاء القيود (CSP) حيث يُمكن انتهاك بعض القيود (وفقًا لدرجة الانتهاك) ويُمكن التعبير عن تفضيلات الحلول. يُتيح هذا التعميم تمثيل المزيد من المشكلات الواقعية، ولا سيما تلك التي تُعاني من قيود زائدة (لا يُمكن إيجاد حل دون انتهاك قيد واحد على الأقل)، أو تلك التي نسعى فيها لإيجاد حل بأقل تكلفة (وفقًا لدالة التكلفة ) من بين حلول مُتعددة مُمكنة.

التعريف الرسمي

شبكة القيود الموزونة (WCN)، والمعروفة أيضًا باسم شبكة دالة التكلفة (CFN)، هي ثلاثية⟨X،ج،ك⟩{\displaystyle \langle X,C,k\rangle }حيث X هي مجموعة محدودة من المتغيرات المنفصلة، ​​و C هي مجموعة محدودة من القيود المرنة وك>0{\displaystyle k>0}إما أن يكون عددًا صحيحًا طبيعيًا أو∞{\displaystyle \infty }.

كل قيد مرنجS∈ج{\displaystyle c_{S}\in C}يتضمن مجموعة مرتبة S من المتغيرات، تسمى نطاقها، ويتم تعريفها كدالة تكلفة منل(S){\displaystyle l(S)}ل⟨0،...،ك⟩{\displaystyle \langle 0,...,k\rangle }أينل(S){\displaystyle l(S)}هي مجموعة الحالات الممكنة لـ S. عندما تكون إحدى الحالاتأنا∈ل(S){\displaystyle I\in l(S)}يتم تحديد التكلفة k ، أيجS(أنا)=ك{\displaystyle c_{S}(I)=k}يقال إنه ممنوع. وإلا فهو مسموح به مع التكلفة المقابلة (صفر يعني الرضا التام).

في WCSP، وهي فئة فرعية محددة من Valued CSP (VCSP)، [ 1 ] يتم دمج التكاليف مع المشغل المحدد⊕{\displaystyle \oplus }يُعرَّف على النحو التالي:

∀α،β∈⟨0،...،ك⟩،α⊕β=مين(ك،α+β){\displaystyle \forall \alpha ,\beta \in \langle 0,...,k\rangle ,\alpha \oplus \beta =\min(k,\alpha +\beta )}.

المعكوس الجزئي لـ⊕{\displaystyle \oplus }يكون⊖{\displaystyle \ominus }مُعرَّف بواسطة:

لو0≤β≤α<ك{\displaystyle 0\leq \beta \leq \alpha <k}،α⊖β=α-β{\displaystyle \alpha \ominus \beta =\alpha -\beta }وإذا0≤β<ك{\displaystyle 0\leq \beta <k}،ك⊖β=ك{\displaystyle k\ominus \beta =k}.

دون الإخلال بعمومية المسألة، فإن وجود قيد صفريج∅{\displaystyle c_{\emptyset }}(تكلفة) بالإضافة إلى وجود قيد أحاديجx{\displaystyle c_{x}}يُفترض أن يكون ذلك لكل متغير x .

التكلفة الإجمالية للتنفيذ الكاملأنا∈ل(X){\displaystyle I\in l(X)}هو المجموع المحدود لتكلفة I علىجS{\displaystyle c_{S}}لجميع أنواع القيود المرنةجS∈ج{\displaystyle c_{S}\in C}، بما في ذلك التكلفة الصفريةج∅{\displaystyle c_{\emptyset }}والتكاليف الأحادية لـ I للمتغيرات في X.

بالنظر إلى شبكة WCN/CFN، فإن المهمة المعتادة (الصعبة حسابيًا) في مسألة WCSP هي إيجاد تجسيد كامل بأقل تكلفة. ويمكن تعريف مهام أخرى في مجال النماذج الرسومية ذي الصلة. [ 2 ]

حل مسائل WCSP الثنائية/الثلاثية

نهج عمليات نقل التكاليف

تمت دراسة اتساق العقدة (NC) واتساق القوس (AC)، اللذين طُرحا في سياق مسألة إرضاء القيود (CSP)، لاحقًا في سياق مسألة إرضاء القيود العالمية (WCSP). علاوة على ذلك، اقتُرحت عدة اتساقات حول أفضل شكل لاتساق القوس، منها: اتساق القوس الاتجاهي الكامل (FDAC) [ 3 ] ، واتساق القوس الاتجاهي الوجودي (EDAC) [ 4 ] ، واتساق القوس الافتراضي (VAC) [ 5 ] ، واتساق القوس المرن الأمثل (OSAC) [ 6 ] .

تعتمد الخوارزميات التي تُطبّق هذه الخصائص على تحويلات الحفاظ على التكافؤ (EPTs) التي تسمح بنقل التكاليف بأمان بين القيود. ثلاث عمليات أساسية لنقل التكاليف هي:

  • المشروع  : نقل التكاليف من القيود إلى القيود الأحادية
  • مشروع أحادي  : نقل التكلفة من قيد أحادي إلى قيد صفري
  • التمديد  : نقل التكلفة من قيد أحادي إلى قيد آخر
التحويلات الأساسية التي تحافظ على التكافؤ
التحويلات الأساسية التي تحافظ على التكافؤ.

يهدف تحويل الحفاظ على التكافؤ إلى تركيز التكاليف على القيد الصفري.ج∅{\displaystyle c_{\emptyset }}وإزالة النسخ والقيم بكفاءة مع إضافة تكلفة إلىج∅{\displaystyle c_{\emptyset }}أي أكبر من أو يساوي التكلفة المحظورة أو تكلفة أفضل حل تم التوصل إليه حتى الآن. تُستخدم عادةً طريقة التفرع والتقييد لحل مسائل إرضاء قواعد البيانات، مع حد أدنىج∅{\displaystyle c_{\emptyset }}والحد الأعلى k .

نهج بدون عمليات نقل التكاليف

يُعدّ خوارزمية PFC-MRDAC [ 7 ] بديلاً لخوارزميات نقل التكلفة، وهي خوارزمية كلاسيكية للتفرع والتقييد تقوم بحساب الحد الأدنى.لب{\displaystyle lb}في كل عقدة من شجرة البحث، يُقابل ذلك تقديرًا أقل من تكلفة أي حل يمكن الحصول عليه من هذه العقدة. تكلفة أفضل حل تم العثور عليه هيuب{\displaystyle ub}. متىلب≥uب{\displaystyle lb\geq ub}ثم يتم تقليم شجرة البحث من هذه العقدة.

وهناك نهج آخر أحدث يعتمد على إعادة التموضع الفائق [ 8 ] والذي يسمح بتخفيف المشكلة لحساب حدود أكثر دقة.

حل مسائل WCSP من الرتبة n

أثبتت خوارزميات نقل التكلفة كفاءتها العالية في حل المشكلات الواقعية عندما تكون القيود المرنة ثنائية أو ثلاثية (أي أن الحد الأقصى لعدد عناصر القيود في المسألة يساوي 2 أو 3). أما في حالة القيود المرنة ذات العدد الكبير من العناصر، فيصبح نقل التكلفة مشكلةً حقيقيةً نظرًا لضرورة التحكم في خطر التضخم التوافقي .

تم اقتراح خوارزمية تُسمى GAC w -WSTR [ 9 ] لفرض نسخة ضعيفة من خاصية اتساق القوس المعمم (GAC) على القيود المرنة المُعرَّفة امتداديًا عن طريق سرد الصفوف وتكاليفها. تجمع هذه الخوارزمية بين تقنيتين، هما: الاختزال الجدولي البسيط ( STR ) [ 10 ] ونقل التكلفة. يتم تحديد القيم التي لم تعد متسقة مع GAC، وحساب الحد الأدنى لتكاليفها. يُعد هذا مفيدًا بشكل خاص لتنفيذ عمليات الإسقاط بكفاءة ، وهي العمليات اللازمة لإنشاء GAC.

تمت دراسة دوال التكلفة العالمية ذات الدلالات المخصصة (مثل SoftAllDifferent و SoftAmong) وتعقيد الوقت المتعدد. [ 11 ]

حلول

المعايير

تتوفر العديد من معايير الأداء الواقعية لمسألة جدولة التكاليف العالمية (WCSP) على الرابطين التاليين: http://genoweb.toulouse.inra.fr/~degivry/evalgm [ 12 ] و https://forgemia.inra.fr/thomas.schiex/cost-function-library (الإصدار الأقدم متوفر على الرابط: http://costfunction.org/en/benchmark ). كما تتوفر المزيد من معايير الأداء لمسألة جدولة التكاليف العالمية (MaxCSP) على الرابط التالي: http://www.cril.univ-artois.fr/~lecoutre/#/benchmarks (موقع قديم، انظر أيضًا http://xcsp.org/series ).

انظر أيضاً

مراجع

  1. ↑ إم سي كوبر، إس دي جيفري، وتي شيكس. مسائل إرضاء القيود ذات القيم، الصفحات 185-207. دار نشر سبرينغر الدولية، 2020.
  2. ↑ م. كوبر، س. دي جيفري، وت. شيكس. النماذج الرسومية: الاستعلامات، التعقيد، الخوارزميات (دليل تعليمي). في الندوة الدولية السابعة والثلاثين حول الجوانب النظرية لعلوم الحاسوب (STACS-20)، المجلد 154 من LIPIcs، الصفحات 4:1-4:22، مونبلييه، فرنسا، 2020.
  3. ↑ م. كوبر. عمليات الاختزال في إرضاء القيود الضبابية أو ذات القيم. مجموعات وأنظمة ضبابية، 134(3):311–342، 2003.
  4. ↑ إس. دي جيفري، إف. هيراس، إم. زيتنيكي، وجيه. لاروسا. اتساق القوس الوجودي: الاقتراب من اتساق القوس الكامل في مسائل إرضاء القيود الموزونة. في وقائع المؤتمر الدولي المشترك للذكاء الاصطناعي 2005، الصفحات 84-89، 2005.
  5. ↑ م. كوبر، س. دي جيفري، م. سانشيز، ت. شيكس، م. زيتنيكي. اتساق القوس الافتراضي لـ CSP الموزون. في وقائع AAAI '08، الصفحات 253-258، 2008.
  6. ↑ م. كوبر، س. دي جيفري، م. سانشيز، ت. شيكس، م. زيتنيكي، وت. فيرنر. إعادة النظر في اتساق القوس الناعم. الذكاء الاصطناعي، 174(7-8):449–478، 2010.
  7. ↑ إي سي فرويدر و آر جيه والاس. إرضاء القيود الجزئية. الذكاء الاصطناعي، 58(1-3):21–70، 1992.
  8. ↑ تي دلاسك، تي فيرنر، وإس دي جيفري. حدود على مسائل إرضاء القيود الموزونة باستخدام نشر القيود وإعادة المعايرة الفائقة. في وقائع مؤتمر CP-21، مونبلييه، فرنسا، 2021.
  9. ↑ سي. ليكوتر، ن. باريس، أ. روسيل، س. تاباري. نشر قيود الجدول المرن. في وقائع مؤتمر CP'12، الصفحات 390-405، 2012.
  10. ↑ سي. ليكوتر. STR2: اختزال جدولي بسيط مُحسَّن لقيود الجدول. القيود، 16(4):341–371، 2011.
  11. ^ د ألوش، سي بيسيير، بي بويزومولت، إس دي جيفري، بي جوتيريز، جي إتش إم لي، كوالالمبور ليونج، إس لودني، جي بي ميتيفير، تي شيكس، واي وو. التحولات التي تحافظ على قابلية تتبع وظائف التكلفة العالمية. الذكاء الاصطناعي، 238: 166-189، 2016.
  12. ↑ ب. هيرلي، ب. أوسوليفان، د. ألوش، ج. كاتسيريلوس، ت. شيكس، م. زيتنيكي، س. دي جيفري. التقييم متعدد اللغات للحلول الدقيقة في التحسين المتقطع للنموذج الرسومي. القيود، 21(3):413-434، 2016.