ما معنى Backtracking في الخوارزميات وهياكل البيانات؟ شرح عملي بأمثلة
Backtracking (خوارزمية التراجع) هي أسلوب لحل المسائل يبني الحل قطعةً بقطعة، وكلما اكتشف أنّ القطعة الحالية تقود إلى طريق مسدود، يتراجع خطوة إلى الوراء ويجرّب خياراً آخر. تخيّل أنك تسير في متاهة: تدخل ممرّاً، فإن انتهى إلى جدار، ترجع إلى آخر مفترق وتختار ممرّاً غير الذي جرّبته. هذا بالضبط جوهر الـ backtracking، وهو أحد أهم الأنماط التي يُطلب فهمها في مقابلات العمل التقنية ومسائل الخوارزميات.
الفكرة المحورية التي تميّزه: بدل تجربة كل الحلول الكاملة ثم فحصها (كما يفعل البحث الشامل الأعمى)، فإنه يفحص صلاحية الحل الجزئي أولاً بأول، فيقطع فروعاً كاملة من شجرة الاحتمالات بمجرد أن يتأكد أنها لن تؤدي إلى حل. هذا القطع المبكر يُسمّى التقليم (Pruning)، وهو سرّ كفاءته.
كيف يعمل Backtracking خطوة بخطوة؟
يمكن تلخيص أي حل بأسلوب التراجع في أربع مراحل متكررة:
- اختر (Choose): أضِف خياراً واحداً إلى الحل الجزئي الحالي.
- تحقّق (Check): اسأل: هل ما زال هذا الحل الجزئي صالحاً وقابلاً للاكتمال؟
- تعمّق (Explore): إن كان صالحاً، انتقل إلى الخطوة التالية بشكل تكراري (recursion).
- تراجع (Un-choose / Backtrack): إن وصلت إلى طريق مسدود أو أردت تجربة بديل، احذف الخيار الأخير وأعِد الحالة كما كانت، ثم جرّب الخيار التالي.
الأمر أشبه بشجرة قرارات: كل عقدة خيار، وكل ورقة إمّا حل ناجح أو طريق مسدود. الـ backtracking يمشي في هذه الشجرة بعمق (Depth-First)، ويطوي الأغصان الميتة بدل السير فيها حتى نهايتها.
مثال ذهني بسيط: توليد كل التباديل
لو أردت ترتيب الحروف A و B و C بكل الطرق الممكنة، تختار حرفاً أول، ثم حرفاً ثانياً من المتبقّي، ثم الأخير، فتحصل على ABC. بعدها تتراجع لتغيّر الحرف الأخير، ثم الثاني، وهكذا حتى تستنفد الترتيبات الستة. لاحظ أنك في كل تراجع تُعيد الحرف إلى «المتاح» قبل تجربة غيره — وهذا هو جوهر «إعادة الحالة».
أمثلة شهيرة تُحلّ بالـ Backtracking
- لعبة سودوكو (Sudoku): تملأ أول خانة فارغة برقم من 1 إلى 9، تتحقق أنه لا يتكرر في الصف والعمود والمربع، ثم تنتقل للخانة التالية. إذا علِقت بلا رقم صالح، تتراجع وتغيّر رقماً سابقاً.
- مسألة الملكات الثماني (N-Queens): ضع ملكة في كل صف بحيث لا تتهدّد أي ملكتان. عند أول تعارض، تتراجع وتنقل الملكة السابقة.
- مشكلة مجموع الجزء (Subset Sum) والتقسيم.
- تلوين الخرائط والرسوم البيانية (Graph Coloring).
- حل المتاهات وإيجاد المسارات.
القاسم المشترك بين هذه المسائل: هناك قيود واضحة تسمح بالحكم على صلاحية حل جزئي دون إكماله، وهذا ما يجعل التراجع فعّالاً فيها تحديداً.
Backtracking مقابل تقنيات أخرى
كثيرون يخلطون بين التراجع وأساليب مجاورة. هذا الجدول يوضّح الفرق:
| التقنية | كيف تعمل | متى تتفوّق |
|---|---|---|
| Backtracking | بناء تدريجي مع تقليم الفروع الفاشلة مبكراً | مسائل القيود التي يمكن فحص صلاحيتها جزئياً |
| Brute Force (البحث الشامل) | توليد كل الحلول الكاملة ثم فحصها | مساحة حلول صغيرة جداً فقط |
| البرمجة الديناميكية (DP) | تخزين حلول المسائل الفرعية المتداخلة وإعادة استخدامها | وجود تداخل في المسائل الفرعية وبنية مثلى |
| الخوارزميات الجشعة (Greedy) | اختيار الأفضل محلياً في كل خطوة دون تراجع | حين يقود الاختيار المحلي إلى حل عام مثالي |
الخلاصة: الـ backtracking نسخة ذكية من البحث الشامل؛ فهو يجرّب كل الاحتمالات نظرياً، لكنه يتجنّب إضاعة الوقت في الفروع الميتة.
نقطة مهمة: التعقيد الزمني
من الأخطاء الشائعة اعتبار الـ backtracking «سريعاً دائماً». الحقيقة أنه في أسوأ الحالات قد يكون تعقيده أُسّياً (exponential)، لأنه قد يضطر لاستكشاف عدد ضخم من الفروع. جودة دالة التحقق من الصلاحية وقوة التقليم هما ما يحدّدان أداءه فعلياً. لذا، كلما جعلت شرط الرفض المبكر أدقّ، صار الحل أسرع بمراحل.
نصيحة عملية من واقع الكتابة: أكثر خطأ يقع فيه المبتدئون هو نسيان إعادة الحالة عند التراجع (مثل عدم إفراغ الخانة أو عدم إزالة العنصر من المجموعة المؤقتة). هذا يلوّث بقية المسار ويعطي نتائج خاطئة يصعب تتبّعها. اجعل قاعدتك: أيّ تعديل تُجريه قبل النزول التكراري، تراجع عنه بنفس الترتيب بعده.
الأسئلة الشائعة
هل الـ Backtracking هو نفسه البحث بالعمق (DFS)؟ هما متقاربان: التراجع يستخدم استكشافاً بالعمق فوق شجرة القرارات، لكنه يضيف عنصر التقليم وإعادة الحالة. كل backtracking نوع من DFS، لكن ليس كل DFS يتضمن تراجعاً بالمعنى الكامل.
متى أختار Backtracking بدل البرمجة الديناميكية؟ اختره حين تحتاج تعداد كل الحلول أو حين لا توجد مسائل فرعية متداخلة يمكن تخزينها. أما إن تكرّرت المسائل الفرعية، فالبرمجة الديناميكية أكفأ غالباً.
هل يمكن تسريعه؟ نعم، عبر تحسين ترتيب الخيارات (تجربة الأرجح أولاً)، وتقوية شروط التقليم، وأحياناً دمجه مع تقنيات مثل «الانتشار بالقيود» (Constraint Propagation) كما في حلّالات السودوكو المتقدمة.
هل يصلح للمسائل الكبيرة جداً؟ ليس دائماً؛ فمع اتساع مساحة البحث ينمو الزمن أُسّياً. عندها يُلجأ إلى خوارزميات تقريبية أو استدلالية (Heuristics) بدل الحل الدقيق.