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

ما هي خوارزمية التتبع العكسي؟

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

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

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

كيف تعمل خوارزمية التتبع العكسي؟

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

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

تحتوي خوارزمية التتبع الخلفي على الخطوات التالية بشكل عام لحل المشكلة:

الخطوة 1) التهيئة: ابدأ بحل أولي فارغ/جزئي.

الخطوة 2) الاختيار:استنادًا إلى معايير وقيود محددة، حدد خيارًا واحدًا لتوسيع الحل الحالي.

الخطوة 3) الاستكشاف:قم بحل المشكلة بشكل متكرر من خلال النظر في المرشح المختار والمضي قدمًا في عملية حل المشكلة.

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

الخطوة 5) الإنهاء:تتوقف عملية الرجوع إلى الوراء عند العثور على حل صالح، أو عند استنفاد جميع التركيبات.

الخطوة 6) الرجوع إلى الوراء:إذا لم يحل الخيار الحالي المشكلة المعطاة، فإنه يعود إلى الحالة السابقة. ثم يفكر في الخيار الجديد لحل المشكلة المعطاة.

الخطوة 7) كرر:استمر بهذه الخطوات حتى يتم حل المشكلة أو استكشاف جميع الخيارات.

الطبيعة التكرارية لخوارزمية التتبع العكسي

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

def find_solutions(n, other_params):
    if found_a_solution():
        increment_solutions_found()
        display_solution()
        if solutions_found >= solution_target:
            exit_program()
        return	

    for val in range(first, last+1):
        if is_valid(val, n):
            apply_value(val, n)
            find_solutions(n + 1, other_params)
            remove_value(val, n)

مصطلحات شائعة تتعلق بمشاكل التتبع

هذه بعض المصطلحات الأساسية المتعلقة بتقنية التتبع العكسي:

• ناقل الحل: يمثل الحلول على هيئة n-tuples، مثل (X1، X2، …، Xn).
• القيود:القواعد التي تحدد قيم X، الضمنية والصريحة.
• مساحة الحل:جميع قيم X الصالحة التي تلبي القيود الصريحة.
• شجرة الفضاء الحكومية:يمثل مساحة الحل كشجرة.
• مساحة الدولة:يصف المسارات في شجرة مساحة الحالة.
• حالة المشكلة:العقد في شجرة البحث تمثل الحلول الجزئية.
• حالات الحل:الحالات التي تشكل مجموعات الحلول الصحيحة في S.
• الإجابة على الدول:إرضاء القيود الضمنية وتقديم الحلول المرجوة.
• عقدة واعدة:يؤدي إلى الحلول المرغوبة ويبقى ممكنا.
• عقدة غير واعدة:يؤدي إلى حالات غير قابلة للتطبيق، ولم يتم استكشافها بشكل أكبر.
• العقدة الحية:تم إنشاؤه باستخدام أطفال غير مستكشفين.
• العقدة الإلكترونية:عقدة حية مع جيل فرعي مستمر.
• عقدة ميتة:لا يوجد مزيد من التوسع لجميع الأطفال الذين تم إنشاؤهم.
• إنشاء العقدة بالعمق أولاً:يستخدم أحدث عقدة حية باعتبارها العقدة الإلكترونية التالية.
• دالة التحديد:يقوم بتعظيم أو تقليل B(x1, x2, …, Xa) من أجل التحسين.
• الأشجار الثابتة:صياغة الشجرة مستقلة عن حالة المشكلة.
• الأشجار الديناميكية:تختلف صياغة الشجرة حسب حالة المشكلة.

متى تستخدم خوارزمية التتبع العكسي؟

يمكننا اختيار تقنية الرجوع إلى الوراء لحل مشكلة معقدة عندما:

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

أنواع مشاكل التتبع العكسي

هناك ثلاثة أنواع من المشكلات في خوارزميات التتبع العكسي: مشكلات القرار ومشكلات التحسين ومشكلات العد. دعنا نتعرف عليها أدناه.

1. مشكلة القرار: في هذا النوع من المشكلات، يكون الهدف هو تحديد ما إذا كان هناك حل قابل للتطبيق. نتحقق من الإجابات "نعم" و"لا". على سبيل المثال، مشكلة الملكات n. إنها مشكلة قرار تفحص احتمالية وضع n ملكات على رقعة شطرنج n × n دون مهاجمة بعضها البعض.
2. مشكلة التحسين:في مسائل التحسين، يكون الهدف هو إيجاد أفضل حل ممكن بين العديد من الخيارات. وقد يتضمن هذا تحديد القيم القصوى والدنيا لدالة أو متغير معين. على سبيل المثال، ضع في اعتبارك مسألة حقيبة الظهر، حيث يكون الهدف هو تعظيم القيمة الإجمالية للعناصر الموجودة في الحقيبة مع الالتزام بحد وزنها.
3. مشكلة التعداد:الهدف من ذلك هو إيجاد كل الحلول الممكنة لمشكلة معينة. نقوم بإدراج كل خيار صالح دون أي إغفالات. على سبيل المثال، إنشاء كل مجموعات الحروف الممكنة من مجموعة معينة من الأحرف.

تطبيقات التتبع العكسي وأمثلة عليه

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

1. Sudoku Solver: تحتوي هذه المشكلة على شبكة فرعية 3×3 تحتوي على أرقام مكررة. ستُظهِر تقنية التتبع العكسي أن الحل يعود بـ false، مما يشير إلى الحاجة إلى وضع رقم مختلف.

function solveSudoku(board):
    if no empty cells:
        return true  # Sudoku is solved
    for each empty cell (row, col):
        for num from 1 to 9:
            if num is valid in (row, col):
                place num in (row, col)
                if solveSudoku(board):
                    return true
                remove num from (row, col)
    return false  # No valid solution

2. مشكلة N-Queen:يحدد أسلوب التتبع العكسي كيفية تقديم الملكات على رقعة شطرنج N × N بحيث لا تهدد أي منهن الأخرى.

function solveNQueens(board, col):
    if col >= N:
        return true  # All queens are placed
    for each row in the column col:
        if isSafe(board, row, col):
            place queen at (row, col)
            if solveNQueens(board, col + 1):
                return true
            remove queen from (row, col)
    return false  # No valid solution in this branch

3. مشكلة مجموع المجموعة الفرعية:يتم استخدامه للعثور على مجموعة فرعية من الأرقام من مجموعة معينة والتي يصل مجموعها إلى مبلغ هدف معين.

function subsetSum(nums, target, index, currentSubset):
    if target == 0:
        print(currentSubset)  # Subset with the target sum found
        return
    if index >= len(nums) or target < 0:
        return
   currentSubset.add(nums[index])
   subsetSum(nums, target - nums[index], index + 1, currentSubset)
   currentSubset.remove(nums[index])
   subsetSum(nums, target, index + 1, currentSubset)

4. مشكلة دورة هاميلتونيان:يمكن تطبيق التتبع العكسي للعثور على جولة مغلقة في الرسم البياني تزور كل رأس مرة واحدة بالضبط.
5. مشكلة الفأر في المتاهة:يتم استخدام تقنية الرجوع إلى الوراء للعثور على مسار الفأر من نقطة بداية المتاهة إلى الخروج.

مزايا وعيوب خوارزمية التتبع العكسي

مزايا خوارزمية التتبع العكسي

تُستخدم تقنيات التتبع العكسي لحل المشكلات المعقدة، ولها العديد من المزايا مثل:

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

عيوب خوارزمية التتبع العكسي

كما أن تقنيات التتبع العكسي لها بعض القيود، مثل تعقيد الوقت. وهذه التقنية لها العيوب التالية:

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

الفرق بين التتبع العكسي والتكرار

خاتمة

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

بالإضافة إلى ذلك، يمكن لنماذج التعلم الآلي توجيه قرارات التتبع استنادًا إلى الأنماط التي تم تعلمها مسبقًا.

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