الاتساق المحلي

يتطلب اتساق العقدة أن تُلبى جميع القيم في نطاق المتغير كل قيد أحادي على المتغير، والعكس صحيح. ويمكن فرض هذا الشرط بسهولة عن طريق تقليص نطاق كل متغير إلى القيم التي تُلبّي جميع القيود الأحادية عليه. ونتيجةً لذلك، يمكن إهمال القيود الأحادية وافتراض دمجها في النطاقات.

على سبيل المثال، بالنظر إلى متغير${\displaystyle V}$بنطاق${\displaystyle \left\{1,2,3,4\right\}}$وقيد${\displaystyle V\leq 3}$سيؤدي اتساق العقدة إلى تقييد النطاق إلى${\displaystyle \left\{1,2,3\right\}}$وبذلك يمكن التخلص من القيد. هذه الخطوة التمهيدية تبسط المراحل اللاحقة.

يكون متغير في مسألة إرضاء القيود متسقًا مع متغير آخر إذا كانت كل قيمة من قيمه المسموح بها متسقة مع قيمة مسموح بها للمتغير الثاني. وبصورة رسمية، يكون المتغير${\displaystyle x_{i}}$هل يتوافق القوس مع متغير آخر؟${\displaystyle x_{j}}$إذا، لكل قيمة${\displaystyle a}$في مجال ${\displaystyle x_{i}}$توجد قيمة${\displaystyle b}$في مجال${\displaystyle x_{j}}$بحيث${\displaystyle (a,b)}$يفي بالشرط الثنائي بين${\displaystyle x_{i}}$و${\displaystyle x_{j}}$تكون المسألة متسقة قوسياً إذا كان كل متغير متسقاً قوسياً مع كل متغير آخر.

على سبيل المثال، ضع في اعتبارك القيد${\displaystyle x<y}$حيث تتراوح المتغيرات ضمن المجال من 1 إلى 3. لأن${\displaystyle x}$لا يمكن أن تكون القيمة 3 أبدًا، فلا يوجد قوس من 3 إلى قيمة في${\displaystyle y}$لذا من الآمن إزالة القيمة 3 من${\displaystyle x}$نطاق 's، مما ينتج عنه${\displaystyle \{1,2\}}$. على نفس المنوال،${\displaystyle y}$لا يمكن أن يكون الناتج 1 أبدًا، لذا لا يوجد قوس، وبالتالي يمكن إزالة 1 من${\displaystyle y}$نطاق 's، مما ينتج عنه${\displaystyle \{2,3\}}$.

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

إذا لم يكن أحد المتغيرات متسقًا مع متغير آخر، فيمكن جعله كذلك بإزالة بعض القيم من نطاقه. هذا هو شكل نشر القيود الذي يفرض الاتساق: إذ يُزيل من نطاق المتغير كل قيمة لا تُقابل قيمة في المتغير الآخر. يحافظ هذا التحويل على حلول المسألة، لأن القيم المُزالة ليست جزءًا من أي حل على أي حال.

يمكن لتقنية نشر القيود أن تجعل المسألة بأكملها متسقة من خلال تكرار عملية الإزالة هذه لجميع أزواج المتغيرات. قد تتطلب هذه العملية النظر في زوج معين من المتغيرات أكثر من مرة. في الواقع، قد تؤدي إزالة قيم من نطاق متغير ما إلى عدم اتساق متغيرات أخرى معه. على سبيل المثال، إذا${\displaystyle x_{3}}$هل القوس متوافق مع${\displaystyle x_{2}}$لكن الخوارزمية تقلل من نطاق${\displaystyle x_{2}}$، اتساق القوس${\displaystyle x_{3}}$مع${\displaystyle x_{2}}$لم يعد هذا الأمر سارياً، ويجب تطبيقه مرة أخرى.

تعتمد خوارزمية بسيطة على المرور على أزواج المتغيرات، مع تطبيق اتساق القوس، وتكرار هذه العملية حتى لا تتغير المجالات خلال دورة كاملة. أما خوارزمية AC-3، فتتفوق على هذه الخوارزمية بتجاهل القيود التي لم تُعدّل منذ آخر تحليل لها. تحديدًا، تعمل هذه الخوارزمية على مجموعة من القيود تحتوي في البداية على جميع القيود؛ وفي كل خطوة، تأخذ قيدًا وتطبق عليه اتساق القوس؛ وإذا كان من المحتمل أن تؤدي هذه العملية إلى انتهاك اتساق القوس لقيد آخر، فإنها تعيد ذلك القيد إلى مجموعة القيود المراد تحليلها. وبهذه الطريقة، بمجرد تطبيق اتساق القوس على قيد ما، لا يُعاد النظر في هذا القيد إلا إذا تغير مجال أحد متغيراته.

يُعدّ اتساق المسار خاصيةً مشابهةً لاتساق القوس، ولكنه يأخذ في الاعتبار أزواج المتغيرات بدلاً من متغير واحد فقط. يكون زوج المتغيرات متسقًا مساريًا مع متغير ثالث إذا أمكن تعميم كل تقييم متسق للزوج على المتغير الآخر بطريقة تُحقق جميع القيود الثنائية . رسميًا،${\displaystyle x_{i}}$و${\displaystyle x_{j}}$المسار متسق مع${\displaystyle x_{k}}$إذا، لكل زوج من القيم${\displaystyle (a,b)}$الذي يحقق القيد الثنائي بين${\displaystyle x_{i}}$و${\displaystyle x_{j}}$، توجد قيمة${\displaystyle c}$في مجال${\displaystyle x_{k}}$بحيث${\displaystyle (a,c)}$و${\displaystyle (b,c)}$تلبية القيد بين${\displaystyle x_{i}}$و${\displaystyle x_{k}}$وبين${\displaystyle x_{j}}$و${\displaystyle x_{k}}$، على التوالى.

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

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

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

يمكن تعميم اتساق القوس والمسار ليشمل القيود غير الثنائية باستخدام مجموعات من المتغيرات بدلاً من متغير واحد أو زوج. مجموعة من${\displaystyle i-1}$المتغيرات هي${\displaystyle i}$- متسق مع متغير آخر إذا كان كل تقييم متسق لـ${\displaystyle i-1}$يمكن توسيع المتغيرات بقيمة المتغير الآخر مع الحفاظ على الاتساق. وينطبق هذا التعريف على المشكلات بأكملها بشكل واضح. قوي${\displaystyle i}$الاتساق هو ${\displaystyle j}$- الاتساق للجميع${\displaystyle j\leq i}$.

تتطابق حالة الاتساق الثنائي مع اتساق القوس (جميع المسائل في هذه المقالة تفترض اتساق العقد). من جهة أخرى، يتطابق الاتساق الثلاثي مع اتساق المسار فقط إذا كانت جميع القيود ثنائية، لأن اتساق المسار لا يتضمن قيودًا ثلاثية بينما يتضمنها الاتساق الثلاثي.

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

قد يؤدي نشر القيود (فرض شكل من أشكال الاتساق المحلي) إلى مجال فارغ أو قيد غير قابل للتنفيذ . في هذه الحالة، لا يوجد حل للمشكلة. لكن العكس ليس صحيحًا بشكل عام: فقد تكون حالة غير متسقة متسقة قوسياً أو متسقة مسارياً دون وجود مجال فارغ أو قيد غير قابل للتنفيذ.

في الواقع، لا يرتبط الاتساق المحلي إلا باتساق مجموعات المتغيرات. فعلى سبيل المثال، يضمن اتساق القوس إمكانية تعميم أي تقييم متسق لمتغير ما على متغير آخر بشكل متسق. مع ذلك، عند تعميم قيمة واحدة لمتغير ما على متغيرين آخرين، لا يوجد ما يضمن اتساق هاتين القيمتين مع بعضهما. على سبيل المثال،${\displaystyle x_{1}=1}$قد يكون ذلك متسقًا مع${\displaystyle x_{2}=1}$ومع${\displaystyle x_{3}=1}$لكن هذين التقييمين قد لا يكونان متسقين مع بعضهما البعض.

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

وينطبق شرط مماثل على اتساق المسار. وفيما يلي الحالات الخاصة التي يمكن فيها إثبات إمكانية الإرضاء من خلال فرض اتساق القوس واتساق المسار.

1. إن فرض اتساق القوس يثبت إمكانية إرضاء المشكلات المكونة من قيود ثنائية بدون دورات ( شجرة من القيود الثنائية)؛
2. إن فرض اتساق المسار يؤدي إلى إرساء إمكانية تحقيق القيود الثنائية (ربما مع دورات) ذات المجالات الثنائية؛
3. فرض قوي${\displaystyle n}$يُثبت الاتساق إمكانية حل المشكلات التي تحتوي على${\displaystyle n}$المتغيرات.

بعض التعريفات أو النتائج المتعلقة بالاتساق النسبي لا تنطبق إلا في حالات خاصة.

عندما تتكون المجالات من أعداد صحيحة ، يمكن تعريف اتساق الحدود. يعتمد هذا النوع من الاتساق على اتساق القيم القصوى للمجالات، أي القيم الدنيا والقصوى التي يمكن أن يأخذها المتغير.

عندما تكون القيود جبرية أو منطقية ، فإن اتساق القوس يعادل إضافة قيد جديد أو تعديل قيد قديم نحويًا، ويمكن القيام بذلك عن طريق تركيب القيود بشكل مناسب.

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

عادةً ما يُكتب القيد الذي يفرض اختلاف عدد من المتغيرات${\displaystyle \mathop {\rm {alldifferent}} (x_{1},\ldots ,x_{n})}$أو alldifferent([X1,...,Xn]). هذا القيد يعادل عدم تساوي جميع أزواج المتغيرات المختلفة، أي${\displaystyle x_{i}\not =x_{j}}$لكل${\displaystyle i\not =j}$عندما يُختزل نطاق متغير ما إلى قيمة واحدة، يمكن إزالة هذه القيمة من جميع النطاقات الأخرى عن طريق نشر القيد عند فرض اتساق القوس. يتيح استخدام القيد المُخصص استغلال خصائص لا تنطبق على حالات عدم المساواة الثنائية الفردية .

تتمثل إحدى الخصائص في أن العدد الإجمالي للعناصر في نطاقات جميع المتغيرات يجب أن يكون على الأقل مساويًا لعدد المتغيرات. وبشكل أدق، بعد تطبيق اتساق القوس، يجب ألا يتجاوز عدد المتغيرات غير المُخصصة عدد القيم في اتحاد نطاقاتها. وإلا، فلن يتحقق الشرط. يمكن التحقق من هذا الشرط بسهولة على قيد من الشكل المذكور alldifferent، ولكنه لا يتوافق مع اتساق قوس شبكة عدم المساواة. أما الخاصية الثانية للقيد الواحد alldifferentفهي إمكانية التحقق بكفاءة من اتساق القوس الفائق باستخدام خوارزمية مطابقة ثنائية الأجزاء . على وجه الخصوص، يتم إنشاء رسم بياني باستخدام المتغيرات والقيم كمجموعتين من العقد، ويتم تشغيل خوارزمية مطابقة رسوم بيانية ثنائية الأجزاء متخصصة عليه للتحقق من وجود مثل هذه المطابقة. ^{[ 1 ]}

هناك نوع آخر من القيود شائع الاستخدام، وهو cumulativeقيد التراكم. وقد طُرح هذا القيد لحل مشكلات الجدولة والتوزيع. على سبيل المثال، cumulative([S1,...,Sm], [D1,...,Dm], [R1,...,Rm], L)يمكن استخدام قيد التراكم لتحديد حالة وجود mأنشطة، لكل منها وقت بدء siومدة زمنية، diوتستهلك كمية محددة riمن الموارد. ينص قيد التراكم على أن إجمالي كمية الموارد المتاحة هو L. توجد تقنيات متخصصة لنشر القيود التراكمية؛ وتُستخدم تقنيات مختلفة بناءً على نطاقات المتغيرات التي تم اختزالها إلى قيمة واحدة.

يُعدّ قيد "الواحد " قيدًا متخصصًا ثالثًا يُستخدم في برمجة منطق القيودelement . في هذا النوع من البرمجة، يُسمح باستخدام القوائم كقيم للمتغيرات. element(I, L, X)يتحقق القيد إذا Lكانت قائمةً وكان Xهو Iالعنصر رقم في هذه القائمة. توجد قواعد نشر قيود متخصصة لهذه القيود. على سبيل المثال، إذا تم اختزال Lو Iإلى نطاق قيمة واحدة، Xيُمكن تحديد قيمة فريدة لـ . وبشكل أعم، Xيُمكن استنتاج القيم المستحيلة لـ من نطاق .${\displaystyle I}$والعكس صحيح.

إذا كانت الخوارزمية تقيّم المتغيرات بالترتيب التالي${\displaystyle x_{1},\ldots ,x_{n}}$، لا تكون الاتساق مفيدة إلا عندما تضمن أن تكون قيم المتغيرات ذات المؤشر الأدنى متسقة مع قيم المتغيرات ذات المؤشر الأعلى.

عند اختيار قيمة لمتغير ما، يمكن تجاهل القيم غير المتوافقة مع جميع قيم المتغير غير المُعيَّن. في الواقع، حتى لو كانت هذه القيم متوافقة مع التقييم الجزئي الحالي، فإن الخوارزمية ستفشل لاحقًا في إيجاد قيمة متوافقة للمتغير غير المُعيَّن. من ناحية أخرى، ليس من الضروري فرض التوافق مع المتغيرات التي تم تقييمها بالفعل: فإذا اختارت الخوارزمية قيمة غير متوافقة مع التقييم الجزئي الحالي، فسيتم اكتشاف عدم التوافق على أي حال.

بافتراض أن ترتيب تقييم المتغيرات هو${\displaystyle x_{1},\ldots ,x_{n}}$تكون مسألة إرضاء القيود متسقة اتجاهيًا إذا كان كل متغير${\displaystyle x_{i}}$هل يتوافق القوس مع أي متغير آخر؟${\displaystyle x_{j}}$بحيث${\displaystyle i<j}$اتساق المسار الاتجاهي مشابه، ولكنه يتضمن متغيرين.${\displaystyle x_{i},x_{j}}$يجب أن يكون المسار متسقًا مع${\displaystyle x_{z}}$فقط إذا${\displaystyle i,j<z}$يعني التناسق القوي للمسار الاتجاهي كلاً من تناسق المسار الاتجاهي وتناسق القوس الاتجاهي. ويمكن تقديم تعريفات مماثلة لأنواع التناسق الأخرى.

تعتمد عملية نشر القيود، التي تفرض اتساق القوس الاتجاهي، على التكرار على المتغيرات من الأخير إلى الأول، حيث يتم في كل خطوة فرض اتساق القوس لكل متغير ذي فهرس أقل معه. إذا كان ترتيب المتغيرات هو${\displaystyle x_{1},\ldots ,x_{n}}$، تقوم هذه الخوارزمية بالتكرار على المتغيرات من${\displaystyle x_{n}}$ل${\displaystyle x_{1}}$; للمتغير${\displaystyle x_{j}}$فهو يفرض اتساق القوس لكل متغير ذي فهرس أقل من${\displaystyle j}$مع${\displaystyle x_{j}}$.

مثال لا يتوافق مع اتجاه القوس:${\displaystyle x_{1}=2}$لا يتوافق مع أي قيمة من${\displaystyle x_{2}}$و${\displaystyle x_{2}=3}$لا يتوافق مع أي قيمة من${\displaystyle x_{3}}$لا يوجد قيد بين${\displaystyle x_{1}}$و${\displaystyle x_{3}}$(تم حذف الحواف المقابلة).	يبدأ ضمان اتساق القوس الاتجاهي بـ${\displaystyle x_{3}}$، ويجعل${\displaystyle x_{2}}$قوس متوافق معه عن طريق إزالة القيمة${\displaystyle x_{2}=3}$.	يتم تطبيق اتساق القوس الاتجاهي من خلال${\displaystyle x_{2}}$. منذ${\displaystyle x_{2}=3}$تمت إزالته بالفعل، كلاهما${\displaystyle x_{1}=2}$و${\displaystyle x_{1}=3}$تتم إزالتها.

يمكن فرض اتساق المسار الاتجاهي واتساق المسار الاتجاهي القوي بواسطة خوارزميات مشابهة لتلك المستخدمة في اتساق القوس. وتقوم هذه الخوارزميات بمعالجة المتغيرات من${\displaystyle x_{n}}$ل${\displaystyle x_{1}}$لكل متغير${\displaystyle x_{z}}$متغيران${\displaystyle x_{i},x_{j}}$مع${\displaystyle i,j<z}$يتم أخذها في الاعتبار، وتناسق مسارها مع${\displaystyle x_{z}}$يتم تطبيق ذلك. لا يلزم إجراء أي عملية إذا لم تتضمن المسألة أي قيد على${\displaystyle x_{i}}$و${\displaystyle x_{z}}$أو عدم وجود قيود بين${\displaystyle x_{j}}$و${\displaystyle x_{z}}$ومع ذلك، حتى لو لم يكن هناك قيد بين${\displaystyle x_{i}}$و${\displaystyle x_{j}}$يُفترض وجود قيد بسيط. إذا قلّص نشر القيد مجموعة التعيينات المُرضية، فإنه يُنشئ فعليًا قيدًا جديدًا غير بسيط. يُشابه نشر القيد الذي يفرض اتساقًا قويًا للمسار الاتجاهي هذا، ولكنه يفرض أيضًا اتساق القوس.

يضمن الاتساق الاتجاهي إمكانية تعميم الحلول الجزئية التي تُحقق قيدًا ما بشكل متسق على متغير آخر ذي مؤشر أعلى. مع ذلك، لا يضمن هذا الاتساق أن تكون التعميمات على متغيرات مختلفة متسقة فيما بينها. على سبيل المثال، قد يُعمم حل جزئي بشكل متسق على متغير${\displaystyle x_{i}}$أو إلى متغير${\displaystyle x_{j}}$لكن هذين الامتدادين لا يتوافقان مع بعضهما البعض.

هناك حالتان لا يحدث فيهما هذا، ويضمن الاتساق الاتجاهي إمكانية الإرضاء إذا لم يكن أي مجال فارغًا ولم يكن أي قيد غير قابل للإرضاء.

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

ونتيجة لذلك، إذا كانت مشكلة القيد لها عرض 1 بالنسبة لترتيب متغيراتها (مما يعني أن الرسم البياني المقابل لها هو شجرة) وكانت المشكلة متسقة اتجاهيًا بالنسبة لنفس الترتيب، فيمكن إيجاد حل (إن وجد) عن طريق تعيين المتغيرات بشكل متكرر وفقًا للترتيب.

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

يُعتمد على العرض المُستحث بدلاً من العرض الأصلي لأن فرض اتساق المسار الاتجاهي قد يُضيف قيودًا. فإذا لم يكن متغيران ضمن القيد نفسه، ولكنهما ضمن قيد مع متغير أعلى، فقد تُخالف بعض أزواج قيمهما اتساق المسار. ويؤدي حذف هذه الأزواج إلى إنشاء قيد جديد. ونتيجةً لذلك، قد ينتج عن نشر القيد مسألةٌ تحتوي على عدد أكبر من الحواف في الرسم البياني مقارنةً بالرسم البياني الأصلي. ومع ذلك، فإن جميع هذه الحواف موجودة بالضرورة في الرسم البياني المُستحث، لأنها جميعًا تقع بين عقدتين أبويتين لنفس العقدة. يضمن العرض 2 إمكانية توسيع كل تقييم جزئي متسق إلى حل، ولكن هذا العرض نسبي للرسم البياني المُولّد. ولذلك، فإن كون العرض المُستحث 2 ضروري لضمان اتساق المسار الاتجاهي القوي، وبالتالي ضمان وجود حلول.

اتجاهي${\displaystyle i}$الاتساق هو الضمانة بأن كل مهمة متسقة لـ${\displaystyle i-1}$يمكن توسيع نطاق المتغيرات باستمرار ليشمل متغيرًا آخر أعلى منه في الترتيب. اتجاه قوي${\displaystyle i}$يتم تعريف الاتساق بطريقة مماثلة، ولكن جميع المجموعات التي لا تتجاوز${\displaystyle i-1}$تُؤخذ المتغيرات في الاعتبار. إذا كانت المشكلة ذات اتجاه قوي${\displaystyle i}$-متناسق وله عرض أقل من${\displaystyle i}$وليس لها مجال فارغ أو قيد غير قابل للتنفيذ، بل لها حلول.

يمكن جعل كل مشكلة ذات اتجاه قوي${\displaystyle i}$متسق، ولكن هذه العملية قد تزيد من عرض الرسوم البيانية المقابلة لها. إجراء نشر القيود الذي يفرض الاتساق الاتجاهي مشابه للإجراء المستخدم لاتساق القوس الاتجاهي واتساق المسار. تُدرس المتغيرات بالتتابع، من الأخير إلى الأول وفقًا للترتيب. بالنسبة للمتغير${\displaystyle x_{k}}$تأخذ الخوارزمية في الاعتبار كل مجموعة من${\displaystyle i-1}$المتغيرات التي لها مؤشر أقل من${\displaystyle k}$وهم في وضع مقيد مع${\displaystyle x_{k}}$اتساق هذه المتغيرات مع${\displaystyle x_{k}}$يتم التحقق من ذلك، وربما فرضه، عن طريق إزالة التعيينات المُرضية من القيد من بين جميع هذه التعيينات.${\displaystyle i}$المتغيرات (إن وجدت، أو إنشاء متغير جديد في حالة عدم وجودها).

تُنتج هذه العملية اتجاهًا قويًا${\displaystyle i}$- مثال متسق. ومع ذلك، قد يضيف أيضًا قيودًا جديدة إلى المثال. ونتيجة لذلك، حتى لو كان عرض المشكلة الأصلية${\displaystyle i}$قد يكون عرض المثال الناتج أكبر. في هذه الحالة، لا يعني الاتساق القوي الاتجاهي إمكانية الإرضاء حتى لو لم يكن أي مجال فارغًا ولم يكن أي قيد غير قابل للإرضاء.

مع ذلك، لا تُضيف عملية نشر القيود إلا قيودًا إلى المتغيرات التي تقل قيمتها عن قيمة المتغير الذي تُعالجه حاليًا. ونتيجةً لذلك، لا يتم تعديل أو إضافة أي قيد على متغير ما بمجرد أن تتعامل الخوارزمية مع هذا المتغير. بدلًا من النظر في قيمة ثابتة${\displaystyle i}$يمكن تعديلها لتشمل عدد آباء كل متغير مُعتبر (آباء المتغير هم المتغيرات ذات الفهرس الأقل من فهرس المتغير والتي ترتبط به بقيد). وهذا يُعادل النظر في جميع آباء متغير مُحدد في كل خطوة. بعبارة أخرى، لكل متغير${\displaystyle x_{i}}$من الأخير إلى الأول، يتم تضمين جميع آبائه في قيد جديد يحد من قيمهم إلى القيم المتوافقة مع${\displaystyle x_{i}}$بما أن هذه الخوارزمية يمكن اعتبارها تعديلاً للخوارزمية السابقة بقيمة${\displaystyle i}$ يتم تغيير ذلك إلى عدد الآباء لكل عقدة، ويسمى ذلك الاتساق التكيفي .

تفرض هذه الخوارزمية اتجاهية قوية${\displaystyle i}$-الاتساق مع${\displaystyle i}$يساوي العرض المُستحث للمسألة. تكون الحالة الناتجة قابلةً للحل إذا وفقط إذا لم يتم جعل أي مجال أو قيد فارغًا. في هذه الحالة، يمكن إيجاد حل بسهولة عن طريق تعيين قيمة عشوائية لمتغير غير مُعين بشكل متكرر، ونشر هذا التقييم الجزئي إلى متغيرات أخرى. لا تكون هذه الخوارزمية دائمًا ذات زمن متعدد الحدود، حيث أن عدد القيود المُدخلة من خلال فرض اتساق اتجاهي قوي قد يُؤدي إلى زيادة أسية في الحجم. ومع ذلك، يمكن حل المسألة في زمن متعدد الحدود إذا لم يُؤدِ فرض الاتساق الاتجاهي القوي إلى زيادة حجم الحالة بشكل فائق متعدد الحدود . ونتيجةً لذلك، إذا كان للحالة عرض مُستحث محدود بثابت، فيمكن حلها في زمن متعدد الحدود.

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

تعتمد خوارزمية حذف المجموعات على الانتقال من المتغير الأعلى إلى المتغير الأدنى بالتتابع. في كل خطوة، يتم تطبيق القيود الموجودة في مجموعات هذا المتغير.${\displaystyle x_{i}}$تُؤخذ هذه القيود في الاعتبار. وبحسب التعريف، فإنها لا تشمل إلا المتغيرات الأقل من${\displaystyle x_{i}}$تُعدّل الخوارزمية القيد بين هذه المتغيرات الأدنى (إن وُجد، وإلا فإنها تُنشئ قيدًا جديدًا). ​​وعلى وجه الخصوص، فإنها تُجبر قيمها على أن تكون قابلة للتمديد إلى${\displaystyle x_{i}}$بما يتوافق مع القيود الموجودة في مجموعة${\displaystyle x_{i}}$ثم يُوضع هذا القيد الجديد، إن وُجد، في الخانة المناسبة. بما أن هذا القيد لا يشمل إلا المتغيرات الأقل من${\displaystyle x_{i}}$، تتم إضافته إلى مجموعة من المتغيرات التي تقل عن${\displaystyle x_{i}}$.

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

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

قد تكون مسألة إرضاء القيود متسقة علائقياً، ولا تحتوي على مجال فارغ أو قيد غير قابل للإرضاء، ومع ذلك تكون غير قابلة للإرضاء. ومع ذلك، توجد بعض الحالات التي لا يكون فيها هذا ممكناً.

الحالة الأولى هي حالة العلاقات القوية${\displaystyle m}$مشكلة متسقة عندما تحتوي المجالات على أكثر من${\displaystyle m}$العناصر. في هذه الحالة، تقييم متسق لـ${\displaystyle k}$يمكن دائمًا توسيع المتغيرات لتشمل متغيرًا واحدًا آخر. إذا${\displaystyle x_{1}=a_{1},\ldots ,x_{k}=a_{k}}$هذا التقييم و${\displaystyle x_{k+1}}$المتغير، لا يوجد سوى${\displaystyle m}$القيم المحتملة التي يمكن أن يأخذها المتغير. إذا كانت جميع هذه القيم غير متسقة مع التقييم، فهناك${\displaystyle m}$القيود (غير الفريدة بالضرورة) التي يتم انتهاكها أثناء التقييم وإحدى قيمها المحتملة. ونتيجة لذلك، لا يمكن توسيع نطاق التقييم ليشمل جميع هذه القيود.${\displaystyle m}$القيود الأقل من أو تساويها، مما ينتهك شرط العلاقات القوية${\displaystyle m}$-تناسق.

أما الحالة الثانية فتتعلق بمقياس القيود، وليس بالمجالات. القيد هو${\displaystyle m}$يكون الشرط محكمًا إذا أمكن توسيع كل تقييم لجميع متغيراته باستثناء متغير واحد لتلبية القيد إما بجميع القيم الممكنة للمتغير الآخر أو بأكثر من${\displaystyle m}$من قيمها. مشكلة في امتلاكها${\displaystyle m}$تكون القيود الصارمة قابلة للتنفيذ إذا وفقط إذا كانت ذات علاقة قوية${\displaystyle m+1}$-ثابت.

الحالة الثالثة هي حالة القيود الثنائية التي يمكن تمثيلها بمصفوفات محدبة الصفوف. يمكن تمثيل القيد الثنائي بمصفوفة ثنائية الأبعاد.${\displaystyle M}$، أين${\displaystyle M_{ij}}$تكون القيمة 0 أو 1 اعتمادًا على ما إذا كان${\displaystyle i}$القيمة رقم -th في مجال${\displaystyle x_{i}}$و${\displaystyle j}$القيمة رقم -th في مجال${\displaystyle x_{j}}$تحقق الشرط. يكون صف هذه المصفوفة محدبًا إذا كانت جميع العناصر التي تحتويها من العدد 1 متتالية (بمعنى آخر، إذا كان عنصران يساويان 1، فإن جميع العناصر بينهما تساوي 1 أيضًا). وتكون المصفوفة محدبة صفّيًا إذا كانت جميع صفوفها محدبة.

الشرط الذي يجعل اتساق المسار العلائقي القوي مكافئًا لقابلية الإرضاء هو وجود مسائل إرضاء القيود التي يوجد فيها ترتيب للمتغيرات يجعل جميع القيود ممثلة بمصفوفات محدبة صفية. تستند هذه النتيجة إلى حقيقة أن مجموعة الصفوف المحدبة التي تحتوي على عنصر مشترك ثنائيًا تحتوي أيضًا على عنصر مشترك عالميًا. وبالنظر إلى التقييم على${\displaystyle k}$المتغيرات، القيم المسموح بها لـ${\displaystyle k+1}$يتم تحديد القيم من خلال اختيار بعض الصفوف من بعض القيود. على وجه الخصوص، لكل متغير من بين${\displaystyle k}$أحدها، الصف بالنسبة لقيمته في المصفوفة التي تمثل القيد الذي يربطه بـ${\displaystyle k+1}$يمثل أحدها القيم المسموح بها للمتغير الأخير. ولأن هذه الصفوف محدبة، ولأنها تشترك في عنصر واحد بين كل زوج منها بسبب اتساق المسار، فإنها تشترك أيضًا في عنصر مشترك، يمثل قيمة المتغير الأخير المتوافقة مع القيم الأخرى.