خوارزمية التتبّع الرجعي

خوارزمية التتبّع الرجعي (backtracking algorithm) أسلوب لحل المسائل عبر البحث الشامل. وتتمثل فكرتها الجوهرية في البدء من حالة أولية والبحث الشامل في جميع الحلول الممكنة. وعند العثور على حل صحيح، يُسجَّل. وتستمر هذه العملية حتى العثور على حل أو تجربة جميع الخيارات الممكنة دون العثور على حل.

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

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

/* الاجتياز المسبق: المثال 1 */
function preOrder(root: TreeNode | null, res: TreeNode[]): void {
    if (root === null) {
        return;
    }
    if (root.val === 7) {
        // سجّل الحل
        res.push(root);
    }
    preOrder(root.left, res);
    preOrder(root.right, res);
}

المحاولة والتتبّع الرجعي

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

في المثال 1، تمثل زيارة كل عقدة «محاولة»، بينما يمثل تجاوز عقدة ورقية أو عبارة return التي تعيد الاجتياز إلى العقدة الأب «تتبّعاً رجعياً».

ومن الجدير بالذكر أن التتبّع الرجعي لا يقتصر على عودة الدوال وحدها. ولتوضيح ذلك، لنوسّع المثال 1 قليلاً.

استناداً إلى شيفرة المثال 1، نحتاج إلى استخدام قائمة path لتسجيل مسار العقد المزارة. وعندما نصل إلى عقدة قيمتها $7$، ننسخ path ونضيفها إلى قائمة النتائج res. وبعد اكتمال الاجتياز، تحتوي res على جميع الحلول. والشيفرة كما يلي:

/* الاجتياز المسبق: المثال 2 */
function preOrder(
    root: TreeNode | null,
    path: TreeNode[],
    res: TreeNode[][]
): void {
    if (root === null) {
        return;
    }
    // محاولة
    path.push(root);
    if (root.val === 7) {
        // سجّل الحل
        res.push([...path]);
    }
    preOrder(root.left, path, res);
    preOrder(root.right, path, res);
    // تتبّع رجعي
    path.pop();
}

في كل «محاولة»، نسجّل المسار بإضافة العقدة الحالية إلى path؛ وقبل «التتبّع الرجعي»، نحتاج إلى إزالة العقدة من path، لاستعادة الحالة قبل هذه المحاولة.

وبمراقبة العملية الموضحة في الشكل التالي، يمكننا فهم المحاولة والتتبّع الرجعي على أنهما «التقدم» و«الإلغاء»، وهما عمليتان متعاكستان.

التشذيب

تحتوي مسائل التتبّع الرجعي المعقدة عادةً على قيد واحد أو أكثر. ويمكن عادةً استخدام القيود في «التشذيب».

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

/* الاجتياز المسبق: المثال 3 */
function preOrder(
    root: TreeNode | null,
    path: TreeNode[],
    res: TreeNode[][]
): void {
    // تشذيب
    if (root === null || root.val === 3) {
        return;
    }
    // محاولة
    path.push(root);
    if (root.val === 7) {
        // سجّل الحل
        res.push([...path]);
    }
    preOrder(root.left, path, res);
    preOrder(root.right, path, res);
    // تتبّع رجعي
    path.pop();
}

«التشذيب» مصطلح معبّر. وكما يوضح الشكل التالي، أثناء عملية البحث، نقوم «بتشذيب» فروع البحث التي لا تحقق القيود، متجنبين بذلك كثيراً من المحاولات بلا معنى، وبالتالي نحسّن كفاءة البحث.

شيفرة الإطار

بعد ذلك، نحاول استخلاص إطار عام يتمحور حول «المحاولة والتتبّع الرجعي والتشذيب» في التتبّع الرجعي لتحسين عمومية الشيفرة.

في شيفرة الإطار التالية، تمثّل state الحالة الحالية للمسألة، وتمثّل choices الخيارات المتاحة في الحالة الحالية:

/* إطار خوارزمية التتبّع الرجعي */
func backtrack(state *State, choices []Choice, res *[]State) {
    // تحقق مما إذا كان حلاً
    if isSolution(state) {
        // سجّل الحل
        recordSolution(state, res)
        // أوقف البحث
        return
    }
    // اجتز جميع الخيارات
    for _, choice := range choices {
        // تشذيب: تحقق من صلاحية الاختيار
        if isValid(state, choice) {
            // محاولة: اتخذ قراراً وحدّث الحالة
            makeChoice(state, choice)
            backtrack(state, choices, res)
            // تتبّع رجعي: ألغِ الاختيار واستعد الحالة السابقة
            undoChoice(state, choice)
        }
    }
}

/* إطار خوارزمية التتبّع الرجعي */
function backtrack(state: State, choices: Choice[], res: State[]): void {
    // تحقق مما إذا كان حلاً
    if (isSolution(state)) {
        // سجّل الحل
        recordSolution(state, res);
        // أوقف البحث
        return;
    }
    // اجتز جميع الخيارات
    for (let choice of choices) {
        // تشذيب: تحقق من صلاحية الاختيار
        if (isValid(state, choice)) {
            // محاولة: اتخذ قراراً وحدّث الحالة
            makeChoice(state, choice);
            backtrack(state, choices, res);
            // تتبّع رجعي: ألغِ الاختيار واستعد الحالة السابقة
            undoChoice(state, choice);
        }
    }
}

بعد ذلك، نحل المثال 3 استناداً إلى شيفرة الإطار. فالحالة state هي مسار اجتياز العقد، والخيارات choices هي عقدتا الابن اليسرى واليمنى للعقدة الحالية، والنتيجة res هي قائمة مسارات:

/* خوارزمية التتبّع الرجعي: المثال 3 */
function backtrack(
    state: TreeNode[],
    choices: TreeNode[],
    res: TreeNode[][]
): void {
    // تحقق مما إذا كان حلاً
    if (isSolution(state)) {
        // سجّل الحل
        recordSolution(state, res);
    }
    // اجتز جميع الخيارات
    for (const choice of choices) {
        // تشذيب: تحقق من صلاحية الاختيار
        if (isValid(state, choice)) {
            // محاولة: اتخذ قراراً وحدّث الحالة
            makeChoice(state, choice);
            // تابع إلى الجولة التالية من الاختيار
            backtrack(state, [choice.left, choice.right], res);
            // تتبّع رجعي: ألغِ الاختيار واستعد الحالة السابقة
            undoChoice(state);
        }
    }
}

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

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

المصطلحات الشائعة

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

جدول   المصطلحات الشائعة في خوارزمية التتبّع الرجعي

المزايا والقيود

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

غير أنه عند التعامل مع مسائل واسعة النطاق أو معقدة، قد تكون كفاءة تشغيل خوارزمية التتبّع الرجعي غير مقبولة.

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

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

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

أمثلة نموذجية على التتبّع الرجعي

يمكن استخدام خوارزمية التتبّع الرجعي لحل كثير من مسائل البحث ومسائل تحقيق القيود ومسائل التحسين التوافقي.

مسائل البحث: هدف هذه المسائل إيجاد حلول تحقق شروطاً محددة.

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

مسائل تحقيق القيود: هدف هذه المسائل إيجاد حلول تحقق جميع القيود.

• مسألة الملكات n: ضع $n$ ملكة على رقعة شطرنج $n \times n$ بحيث لا تهاجم إحداها الأخرى.
• سودوكو: املأ الأعداد من $1$ إلى $9$ في شبكة $9 \times 9$ بحيث لا يحتوي كل صف وكل عمود وكل شبكة فرعية $3 \times 3$ على أرقام مكررة.
• تلوين الرسوم البيانية: بمعطى رسم بياني غير موجه، لوّن كل رأس بأقل عدد من الألوان بحيث يكون لأي رأسين متجاورين لونان مختلفان.

مسائل التحسين التوافقي: هدف هذه المسائل إيجاد حل أمثل يحقق شروطاً معينة في فضاء توافقي.

• حقيبة الظهر 0-1: بمعطى مجموعة من العناصر وحقيبة ظهر، لكل عنصر قيمة ووزن. وفي ظل قيد سعة الحقيبة، اختر العناصر لتعظيم القيمة الإجمالية.
• مسألة البائع المتجول: بدءاً من نقطة في رسم بياني، زُر جميع النقاط الأخرى مرة واحدة بالضبط ثم عد إلى نقطة البداية، وأوجد أقصر مسار.
• الزمرة العظمى: بمعطى رسم بياني غير موجه، أوجد أكبر رسم فرعي كامل، أي رسم فرعي تكون فيه أي رأسين متصلتين بضلع.

لاحظ أن التتبّع الرجعي ليس الحل الأمثل لكثير من مسائل التحسين التوافقي.

• تُحل مسألة حقيبة الظهر 0-1 عادةً باستخدام البرمجة الديناميكية لتحقيق كفاءة زمنية أعلى.
• مسألة البائع المتجول مسألة شهيرة من صنف NP-Hard؛ ومن الحلول الشائعة لها الخوارزميات الجينية وخوارزميات مستعمرة النمل.
• مسألة الزمرة العظمى مسألة كلاسيكية في نظرية الرسوم البيانية، ويمكن حلها باستخدام خوارزميات استكشافية مثل الخوارزميات الجشعة.