books fulfillment of conditions
If you do not find what you're looking for, you can use more accurate words.
تحقيق الشروط (Info)
المسائل التي تحقق الشروط العامة تحتوي بالعثور على قائمة من الأعداد الصحيحة س =(س[1]، س[2]،....،س[ن])، كل واحدة في بعض نطاق {1، 2،....، م}، التي ترضي بعض القيود الاستبدادية (اقتران منطقي) ق.
لهذه الفئة من السائل، طلب البيانات ب يكون الاعدد الصحيح م و ن و المسند ق. في حل نموذجي بخوارزمية الرجوع في الطريق لهذه المسألة، واحد ممكن أن يعرف حل مرشح جزئي كقائمة من الأعداد الصحيحة س=(س[1]، س[2]،....،س[ك])، لا ك بين 0 و ن، التي سيتم تعيينها لأول ك متغيرات (ص[1]،ص[2]،....،ص[ك])، الجذر المرشح سوف يصبح قائمة فارغة(). الاجراءات الأولى و التالي سوف تصبح:
function first(P,c) k ← length(c) if k = n then return Λ else return (c[1], c[2], ..., c[k], 1) function next(P,s) k ← length(s) if s[k] = m then return Λ else return (s[1], s[2], ..., s[k-1], 1 + s[k])
هنا "length(c)" هو عدد العناصر في المجموعة س
المناداة reject(P,c) يجب أن يرجع صحيح إذا الشرط ق لا يمكن تحقيقها بأي مجموعة من ن أعداد صحيحة التي تبدأ بـ ك عناصر من س. لخوارزمية الرجوع في الطريق لتصبح فعالة، يجب أن يكون هنالك طريقة للكشف عن هذه الحالة، على الأقل لبعض الحلول المرشحة س، بدون عد كل $م^(ن-ك) ن$-صفوف.
مثلاُ، إذا ق هو الاقتران للعديد من المسندات المنطقية، ق = ق[1]^ق[2]^...^ق[ب]، و كل ق[أ] يعتمد فقط على مجموعة فرعية صغيرة من المتغيرات ص[1]، ...، ص[ن]، و بعدها اجراء الرفض يمكن أن يفحص الشروط ق[أ] التي تعتمد فقط على المتغيرات ص[1]، ...، ص[ك]، و ترجع صحيح إذا أي من هؤلاء الشروط التي ترجع خطأ. في الحقيقة، الرفض يحتاج فقط لفحص هؤلاء الشروط التي تعتمد على ص[ك]، بما أن الشروط تعتمد فقط على ص[1]، ...، ص[ك-1] سوف تختضع لفحص اضافي في شخرة البحث.
لنفترض ان الرفض هو مثل ما هو منفذ في الأعلى، و accept(P,c) يحتاج فقط أن يفحص إذا كانت س كاملة، هذا هو، إذا كان عندها ن عناصر.
انه بشكل عام أفضل أن ترتب مجموعة من المتغيرات لتبدأ بأكثر واحدة حساسة.
واحدة أيضاً تسمح للاقتران التالي لتختار أي متغير يجب تعيينه عند تمديد حل مرشح جزئي، على أساس القيم للمتغيرات المعينة مسبقاً. للمزيد من التحسينات التي يمكن الحصول عليها من التقنية تكاثر الشرط.
بالإضافة للاحتفاظ بالحد الأدنى للقيم المستخدمة في النسخ الاحتياطي، تنفيذ خوارزمية الرجوع في الطريق عادة تبقي أثر متغير، ليسجل القيمة عند تغيير السجل. ليكون التنفيذ فعالاً يجب أن نبتعد عن إنتاج مدخل لأثر متغير بين تغيرين متعاقبين عندما لا يكون هنالك نقطة اختيار، وخوارزمية الرجوع في الطريق سوق تزيل كل التغيرات كعملية واحدة.
كبديل لأثر متغير هو بالاحتفاظ بالطابع الزمني عند آخر تغيير قد حدث للمتغير. نقارن الطابع الزمني مع نقطة اختيار الطابع الزمني. إذا كانت نقطة الاختيار لها ارتباط زمني لاحق من ذلك المتغير، هو غير مهم لعودة المتغير عندما ننفذ هذه الخوارزمية على نقطة الاختيار، كما كانت متغيرة قبل ما حدثت نقطة الاختيار.
