التعقب الخلفي

من موسوعة حسوب
اذهب إلى: تصفح، ابحث

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

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

مسألة جولة الحصان

يوضع الحصان في الخانة الأولى من رقعة شطرنج فارغة، ويجب أن يتحرك الفارس وفق قواعد الشطرنج ليزور كل مربع في رقعة الشطرنج مرة واحدة فقط، تسمى هذه المسألة بجولة الحصان Knight's Tour.

مسألة فأر في متاهة

تقدّم هذه المسألة متاهة ممثّلة بواسطة مصفوفة ثنائية الأبعاد عناصرها هي N*N من الكتل، ويتحرك الفأر في هذه المتاهة من نقطة البداية (الجانب العلوي الأيسر) وعليه أن يصل إلى نقطة النهاية (الجانب السفلي الأيمن) ، ولكن ليس بمقدور الفأر أن يتحرك إلا باتجاهين هما الأمامي والسفلي.

مسألة ملكات الشطرنج

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

لعبة السودوكو

تستخدم لعبة السودوكو Sudoku مصفوفة ثنائية الأبعاد حجمها 9×9 وتحتوي على بعض الأرقام، والهدف هو تعبئة هذه المصفوفة بالأرقام (من 1 إلى 9) بشرط أن لا يتكرّر أي من هذه الأرقام في كل صف وعمود ومصفوفة فرعية ذات حجم 3×3 إطلاقًا.