استكشف روعة تعقب رجوعي

التعقب الرجوعي (بالإنجليزية: Backtracking) خوارزمية عامة لإيجاد كل (أو بعض) حلول لبعض المسائل الحاسوبية، لا سيما في المسائل التي تحقق الشروط، أن البناء التدريجي للحلول المرشحة، والتخلي عن كل حل مرشح جزئي س («نرجع في الطريق») بمجرد أن يحدد أن س لا يمكن أن تكون حل كامل وصحيح.

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

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

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

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

Aslcon, Planner, Prolog.

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

المصطلح «التعقب الرجوعي» قد صيغ من عالم الرياضيات الأمريكي ديريك هينري ليمير في ال 1950. لغة معالجة الكلمات (SNOBOL) (1962) يمكن أن تكون الأولى التي أسست طريقة التعقب الرجوعي مبنية فيها.