الرجوع للخلف

الرجوع إلى الوراء هو فئة من الخوارزميات لإيجاد حلول لبعض المشاكل الحسابية ، وخاصة مشاكل إرضاء القيود ، والتي تبني بشكل تدريجي المرشحين للحلول، وتتخلى عن المرشح ("الرجوع إلى الوراء") بمجرد تحديد أنه لا يمكن إكمال المرشح إلى حل صالح. ^[1]

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

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

يعد الرجوع إلى الوراء أداة مهمة لحل مشاكل إرضاء القيود ، [ 2 ^] مثل الكلمات المتقاطعة والحساب اللفظي والسودوكو والعديد من الألغاز الأخرى. غالبًا ما تكون التقنية الأكثر ملاءمة للتحليل ، ^[3] لمشكلة حقيبة الظهر ومشكلات التحسين التوليفية الأخرى . إنها أيضًا استراتيجية تنفيذ البرنامج المستخدمة في لغات البرمجة Icon و Planner و Prolog .

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

تم صياغة مصطلح "الرجوع إلى الخلف" بواسطة عالم الرياضيات الأمريكي DH Lehmer في الخمسينيات من القرن العشرين. ^[4] ربما كانت لغة معالجة السلاسل الرائدة SNOBOL (1962) هي أول من قدم مرفقًا مدمجًا للرجوع إلى الخلف.

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

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

تجتاز خوارزمية التتبع العكسي شجرة البحث هذه بشكل متكرر ، من الجذر إلى الأسفل، بترتيب العمق أولاً . عند كل عقدة c ، تتحقق الخوارزمية مما إذا كان يمكن إكمال c إلى حل صالح. إذا لم يكن ذلك ممكنًا، يتم تخطي الشجرة الفرعية بأكملها التي تم جذرها في c ( تقليمها ). بخلاف ذلك، تتحقق الخوارزمية (1) مما إذا كانت c نفسها حلاً صالحًا، وإذا كان الأمر كذلك، فتبلغ المستخدم بذلك؛ و(2) تحصي بشكل متكرر جميع الأشجار الفرعية لـ c . يتم تعريف الاختبارين وأبناء كل عقدة من خلال إجراءات يقدمها المستخدم.

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

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

1. الجذر ( P ): إرجاع المرشح الجزئي في جذر شجرة البحث.
2. رفض ( P ، c ): قم بإرجاع true فقط إذا لم يكن المرشح الجزئي c يستحق الإكمال.
3. قبول ( P ، c ): إرجاع true إذا كان c هو حل لـ P ، و false بخلاف ذلك.
4. أولاً ( P ، c ): قم بإنشاء الامتداد الأول للمرشح c .
5. التالي ( P ، s ): إنشاء الامتداد البديل التالي للمرشح، بعد الامتداد s .
6. الإخراج ( P ، c ): استخدم الحل c لـ P ، بما يتناسب مع التطبيق.

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

إجراء backtrack(P, c) هو 
    إذا تم رفض(P, c) ثم العودة
     وإذا تم قبول(P, c) ثم الإخراج(P, c)
    س ← الأول(ص، ج)
    بينما s ≠ NULL افعل
        العودة إلى الخلف(ص، ث)
        س ← التالي(ص، س)

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

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

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

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

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

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

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

تتضمن الأمثلة حيث يمكن استخدام الرجوع إلى الوراء لحل الألغاز أو المشكلات ما يلي:

• الألغاز مثل لغز الملكات الثمانية ، والكلمات المتقاطعة ، والحساب اللفظي ، والسودوكو ^{[nb 1]} ، ولعبة بيج سوليتير .
• مشاكل التحسين التوليفي مثل التحليل ومشكلة حقيبة الظهر .
• لغات البرمجة الموجهة نحو الهدف مثل Icon و Planner و Prolog ، والتي تستخدم التتبع الداخلي لتوليد الإجابات.
• خوارزمية DPLL لحل مشكلة قابلية الإرضاء المنطقية .

فيما يلي مثال حيث يتم استخدام التتبع العكسي لمشكلة إرضاء القيد :

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

الدالة الأولى (P, c) هي
    ك ← الطول(ج)
    إذا كان k = n ، قم 
        بإرجاع NULL
     وإلا 
        قم بإرجاع (c[1]، c[2]، ...، c[k]، 1)

الدالة next(P, s) هي
    ك ← الطول(أطوال)
    إذا كان 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 -tuples.

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

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

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

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

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

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

• خيط أريادن (المنطق)  – طريقة حل المشكلات
• القفز للخلف  – في خوارزميات التتبع للخلف، تقنية تقلل من مساحة البحث
• التسلسل العكسي  – طريقة تكوين الاستدلالات
• خوارزمية العد  – خوارزمية تقوم بطباعة جميع الحلول لمشكلة ماالصفحات التي تعرض أوصاف ويكي بيانات كبديل
• خوارزميات حل السودوكو  – خوارزميات لإكمال السودوكو

• HBmeyer.de، رسوم متحركة تفاعلية لخوارزمية التتبع العكسي
• حل المشكلات التوافقية باستخدام STL والتتبع العكسي، والمادة وكود المصدر C++ لتنفيذ عام للتتبع العكسي