ملخص

مراجعة النقاط الرئيسية

• خوارزمية التتبّع الرجعي في جوهرها أسلوب بحث شامل. فهي تجد الحلول التي تحقق شروطاً محددة عبر اجتياز فضاء الحلول بالعمق أولاً. وتُسجَّل أثناء عملية البحث كل حل يستوفي الشروط عند العثور عليه. وينتهي البحث إما بعد العثور على جميع الحلول وإما بعد اكتمال الاجتياز.
• تتكوّن عملية البحث في خوارزمية التتبّع الرجعي من جزأين: المحاولة والتتبّع الرجعي. فهي تجرّب خيارات مختلفة عبر البحث بالعمق أولاً، وعند مصادفة حالات تخالف القيود، تلغي الاختيار السابق، وتعود إلى الحالة السابقة، وتواصل استكشاف خيارات أخرى. وهاتان العمليتان متعاكستان في الاتجاه.
• تحتوي مسائل التتبّع الرجعي عادةً على قيود متعددة يمكن استخدامها في تنفيذ عمليات التشذيب. ويمكن للتشذيب أن ينهي فروع البحث غير الضرورية مبكراً، بما يحسّن كفاءة البحث تحسيناً كبيراً.
• تُستخدم خوارزمية التتبّع الرجعي أساساً لحل مسائل البحث ومسائل استيفاء القيود. ورغم أنه يمكن حل مسائل التحسين التوافقي بالتتبّع الرجعي، فغالباً ما تتوفر حلول أكثر كفاءة أو أفضل أداءً.
• تهدف مسألة التباديل إلى إيجاد جميع التباديل الممكنة لعناصر مجموعة معطاة. ونستخدم مصفوفة لتسجيل ما إذا كان كل عنصر قد اختير، وبذلك نشذّب فروع البحث التي تحاول اختيار العنصر نفسه مراراً، بما يضمن اختيار كل عنصر مرة واحدة بالضبط.
• في مسألة التباديل، إذا احتوت المجموعة على عناصر مكررة، فستحتوي النتيجة النهائية على تباديل مكررة. ويلزمنا فرض قيد يقتضي ألا تُختار العناصر المتساوية إلا مرة واحدة في كل جولة، ويتحقق ذلك عادةً باستخدام مجموعة تجزئة.
• تهدف مسألة مجموع المجموعات الجزئية إلى إيجاد جميع المجموعات الجزئية في مجموعة معطاة التي يساوي مجموعها قيمة مستهدفة. وبما أن المجموعة غير مرتبة، لكن عملية البحث تُخرج النتائج بكل الترتيبات، تنشأ مجموعات جزئية مكررة. لذلك نرتّب البيانات قبل التتبّع الرجعي ونستخدم متغيراً للدلالة على نقطة بداية الاجتياز في كل جولة، وبذلك نشذّب فروع البحث التي تولّد مجموعات جزئية مكررة.
• في مسألة مجموع المجموعات الجزئية، تولّد العناصر المتساوية في المصفوفة مجموعات جزئية مكررة. ونستفيد من الشرط المسبق أن المصفوفة مرتبة، عبر التحقق مما إذا كان العنصران المتجاوران متساويين، لتنفيذ التشذيب، بما يضمن ألا تُختار العناصر المتساوية إلا مرة واحدة في كل جولة.
• تهدف مسألة الملكات $n$ إلى إيجاد ترتيبات لوضع $n$ ملكة على رقعة شطرنج $n \times n$ بحيث لا تستطيع أي ملكتين مهاجمة إحداهما الأخرى. وتشمل قيود هذه المسألة قيد الصف وقيد العمود وقيدي القطر الرئيسي والقطر المضاد. ولتحقيق قيد الصف، نعتمد استراتيجية الوضع صفاً بصف، بما يضمن وضع ملكة واحدة بالضبط في كل صف.
• التعامل مع قيد العمود وقيود الأقطار متشابه. فلقيد العمود، نستخدم مصفوفة لتسجيل ما إذا كان في كل عمود ملكة، وبذلك نبيّن ما إذا كانت الخانة المختارة صالحة. ولقيود الأقطار، نستخدم مصفوفتين لتسجيل ما إذا كانت هناك ملكات على كل قطر رئيسي أو مضاد على حدة. ويكمن التحدي في إيجاد نمط فهارس الصف والعمود الذي يميّز الخانات الواقعة على القطر الرئيسي (المضاد) نفسه.

أسئلة وأجوبة

س: كيف يمكننا فهم العلاقة بين التتبّع الرجعي والتعاود؟

إجمالاً، التتبّع الرجعي استراتيجية خوارزمية، بينما التعاود أداة على نحو أدق.

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