التراجع

لتطبيق خوارزمية التراجع على فئة محددة من المسائل، يجب توفير البيانات P الخاصة بالمسألة المراد حلها، بالإضافة إلى ستة معلمات إجرائية : root ، reject ، accept ، first ، next ، و output . تأخذ هذه الإجراءات بيانات المسألة P كمعلمة، وتقوم بما يلي:

1. root ( P ): إرجاع المرشح الجزئي في جذر شجرة البحث.
2. reject ( P , c ): تُرجع القيمة true فقط إذا لم يكن المرشح الجزئي c يستحق الإكمال.
3. accept ( P , c ): return true if c is a solution of P , , false otherwise.
4. first ( P , c ): توليد الامتداد الأول للمرشح c .
5. next ( P , s ): توليد الامتداد البديل التالي لمرشح، بعد الامتداد s .
6. output ( P , c ): استخدم الحل c لـ P ، حسب ما يناسب التطبيق.

تُختزل خوارزمية التراجع المشكلة إلى استدعاء backtrack ( P , root ( P ))، حيث يكون التراجع هو الإجراء التكراري التالي:

الإجراء backtrack(P, c) هو: إذا تم رفض (P, c) فقم بالإرجاع، وإذا تم قبول (P, c) فقم بالإخراج (P, c). s ← first(P, c) بينما s ≠ NULL نفّذ التراجع (P، s) s ← next(P, s)

يجب أن تكون دالة الرفض دالة منطقية تُرجع القيمة "صحيح" فقط إذا كان من المؤكد أن أي امتداد ممكن للدالة c لا يُمثل حلاً صحيحاً للمسألة P. إذا لم تتمكن الدالة من الوصول إلى نتيجة محددة، فيجب أن تُرجع القيمة "خطأ" . قد تؤدي النتيجة "صحيح" غير الصحيحة إلى تفويت دالة التراجع لبعض الحلول الصحيحة. يمكن للدالة أن تفترض أن دالة الرفض ( P , t ) تُرجع القيمة "خطأ" لكل سلف t للدالة c في شجرة البحث.

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

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

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

تستخدم خوارزمية التراجع الإجراءين الأول والتالي لحصر أبناء العقدة c في الشجرة ، أي المرشحين الذين يختلفون عن c بخطوة امتداد واحدة. يجب أن يُعيد استدعاء الإجراء الأول ( P , c ) الابن الأول لـ c ، بترتيب معين؛ ويجب أن يُعيد استدعاء الإجراء التالي ( P , s ) الشقيق التالي للعقدة s ، بنفس الترتيب. يجب أن تُعيد كلتا الدالتين مرشحًا مميزًا بقيمة "NULL" إذا لم يكن الابن المطلوب موجودًا.

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

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

تتمثل مشكلة إرضاء القيود العامة في إيجاد قائمة من الأعداد الصحيحة x = ( x [1], x [2], …, x [ n ]) ، كل منها في نطاق {1, 2, …, m }، والتي تحقق قيدًا عشوائيًا (دالة منطقية) F.

في هذا النوع من المسائل، تكون بيانات الحالة P هي العددين الصحيحين m و n ، والمسند F. في حل التراجع النموذجي لهذه المسألة، يمكن تعريف مرشح جزئي على أنه قائمة من الأعداد الصحيحة c = ( c [1], c [2], …, c [k]) ، لأي قيمة k بين 0 و n ، والتي سيتم تعيينها لأول k متغير x [1], x [2], …, x [ k ] . سيكون المرشح الجذري حينها هو القائمة الفارغة (). ستكون الإجراءات الأولى والتالية هي

الدالة first(P, c) هي k ← length(c) إذا كان k = n، فأرجع NULL، وإلا فأرجع (c[1]، c[2]، ...، c[k]، 1) .

الدالة next(P, s) هي k ← الطول(ات) إذا كان s[k] = m ، فأرجع NULL، وإلا فأرجع ( s [1], s[2], ..., s[k − 1], 1 + s[k])

هنا الطول ( c ) هو عدد العناصر في القائمة c .

يجب أن تُرجع الدالة reject ( P , c ) القيمة true إذا لم يكن بالإمكان تحقيق القيد F بواسطة أي قائمة من n عددًا صحيحًا تبدأ بالعناصر k من c . ولكي يكون التراجع فعالًا، يجب أن تكون هناك طريقة لاكتشاف هذه الحالة، على الأقل لبعض المرشحين c ، دون الحاجة إلى تعداد جميع تلك المجموعات المكونة من m ^{n − k} n .

على سبيل المثال، إذا كانت F عبارة عن اقتران لعدة دوال منطقية، F = F [1] ∧ F [2] ∧ … ∧ F [ p ] ، وكان كل F [ i ] يعتمد فقط على مجموعة فرعية صغيرة من المتغيرات x [1]، …، x [ n ] ، فإن إجراء الرفض يمكنه ببساطة التحقق من الحدود F [ i ] التي تعتمد فقط على المتغيرات x [1]، …، x [ k ] ، وإرجاع القيمة "صحيح" إذا كانت أي من هذه الحدود تُرجع القيمة "خطأ" . في الواقع، لا يحتاج إجراء الرفض إلا إلى التحقق من الحدود التي تعتمد على x [ k ]، لأن الحدود التي تعتمد فقط على x [1]، …، x [ k -1] ستكون قد تم اختبارها في مراحل سابقة من شجرة البحث.

بافتراض أن الرفض يتم تنفيذه كما هو مذكور أعلاه، فإن القبول ( P ، c ) يحتاج فقط إلى التحقق مما إذا كانت c كاملة، أي ما إذا كانت تحتوي على n عنصرًا.

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

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

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

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