الرجوع في الطريق

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

1. root(P): يرجع الحل المرشح الجزئي في الجذر من شجرة البحث
2. reject(P,c): يرجع صحيح إذا كان الحل المرشح الجزئي س لا يستحق أن نكمله
3. accept(P,c): يرجع صحيح إذا كانت س هي حل ل ب، و خطأ غير ذلك 
4. first(P,c): ينتج التمديد الأول للحل المرشح س
5. next(P,s): ينتج التمديد البديل التالي لحل مرشح، بعد التمديد ي س 
6. output(P,c): يستخدم الحل س ل ب، مناسب للتطبيق

خوارزمية الرجوع بالطريق تقلل المسائل لمناداة bt(root(P)) حيث أن bt هي ما يلي من اجراء الاستدعاء الذاتي تكراراً : 

procedure bt(c)
  if reject(P,c) then return
  if accept(P,c) then output(P,c)
  s ← first(P,c)
  while s ≠ Λ do
    bt(s)
    s ← next(P,s)

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

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

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

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

اجراءات الأول و التالي يستخدمون بخوارزميو الرجوع في الطريق لعد اطفال العقدة س من الشجرة، هذا هوة، الحلول المرشحة التي تختلف من س بخطوة تمديد واحدة. المنادي first(P,c) يجب أن ينتج أول طفل ل س، في بعض النظام؛ و عندما ننادي next(P,s)، يجب أن ترجع الأخوة الآخرى ل س، في ذلك الترتيب. الاقترانين الاثنان يجب أن يرجعو حل مرشح null مميز نرمز لها هنا ب Λ ، إذا الطفل المطلوب ليس موجود.

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

البسودو كود الفوق سوف ينادي المخرجات لكل الحلول المرشحة و هم حل للطلب المعطى ب. الخوارزمية من السهل التعديل عليها لتقف عندما نجد الحل الأول، أو عدد معين من الحلول؛ أو بعد فحص عدد معين من الحلول المرشحة الجزئية، أو بعد امضاء كمية معينة من وقت ال CPU.

المسائل التي تحقق الشروط العامة تحتوي بالعثور على قائمة من الأعداد الصحيحة س =(س[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) يحتاج فقط أن يفحص إذا كانت س كاملة، هذا هو، إذا كان عندها ن عناصر.

انه بشكل عام أفضل أن ترتب مجموعة من المتغيرات لتبدأ بأكثر واحدة حساسة. 

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

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

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