الرجوع في الطريق

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

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

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

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

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

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

وصف الطريقة

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

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

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

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

سودو كود

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

1. root(P): يرجع الحل المرشح الجزئي في الجذر من شجرة البحث
2. reject(P,c): يرجع صحيح إذا كان الحل المرشح الجزئي س لا يستحق أن نكمله
3. accept(P,c): يرجع صحيح إذا كانت س هي حل ل ب، وخطأ غير ذلك 
4. first(P,c): ينتج التمديد الأول للحل المرشح س
5. next(P,s): ينتج التمديد البديل التالي لحل مرشح، بعد التمديد ي س 
6. output(P,c): يستخدم الحل س ل ب، مناسب للتطبيق

خوارزمية الرجوع بالطريق تقلل المسائل لمناداة bt(root(P)) حيث أن bt هي ما يلي من إجراء الاستدعاء الذاتي تكراراً: 

procedure bt(c)
  if reject(P,c) then return
  if accept(P,c) then output(P,c)
  s ← first(P,c)
  while s ≠ Λ do
    bt(s)
    s ← next(P,s)

النظر في الاستخدام 

إجراء الرفض يجب أن يكون اقتران قيمته منطقية حيث يرجع صحيح أو خطأ إذا كان متيقن لا يمكن إيجاد تمديد ل س لإيجاد حل صالح ل ب. إذا كان الاجراء لا يصل لاستنتاج واضح، يجب أن يرجع خطأ. أي حل إذا ارجع صحيح وكان غير صحيح يمكن أن يسبب إجراء bt أن يضيع بعض الحلول الصالحة.هذا الاجراء من الممكن أن يعتبر أن reject(P,c) أرجع خطأ لكل اب أعلى ت من س في شجرة البحث.  

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

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

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

اجراءات الأول والتالي يستخدمون بخوارزميو الرجوع في الطريق لعد أطفال العقدة س من الشجرة، هذا هوة، الحلول المرشحة التي تختلف من س بخطوة تمديد واحدة. المنادي first(P,c) يجب أن ينتج أول طفل ل س، في بعض النظام؛ وعندما ننادي next(P,s)، يجب أن ترجع الأخوة الآخرى ل س، في ذلك الترتيب. الاقترانين الاثنان يجب أن يرجعو حل مرشح null مميز نرمز لها هنا ب Λ ، إذا الطفل المطلوب ليس موجود.

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

الوقوف في وقت مبكر أو مختلف

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

أمثلة

لعبة السودوكو تحل بخوارزمية الرجوع في الطريق

أمثلة تقليدية هي:

• ألغاز مثل لغز الووزراء الثمانية، الكلمات المتقاطعة، الحساب اللفظي، سودوكو، وتد السوليتير.
•  مسائل الاندماج الامثل مثل التحليل ومسألة حقيبة السرقة.
• لغات البرمجة المنطقية مثل ايكون، بلانرز، وبرولوج، التي تستخدم خوارزمية الرجوع في الطريق الأجوبة الصادرة داخلياً. 

يوجد في الأسفل مثال على المسائل التي تحقق الشروط:

تحقيق الشروط

المسائل التي تحقق الشروط العامة تحتوي بالعثور على قائمة من الأعداد الصحيحة س =(س[1]، س[2]....س[ن])، كل واحدة في بعض نطاق {1، 2.... م}، التي ترضي بعض القيود الاستبدادية (اقتران منطقي) ق. 

لهذه الفئة من السائل، طلب البيانات ب يكون الاعدد الصحيح م ون والمسند ق. في حل نموذجي بخوارزمية الرجوع في الطريق لهذه المسألة، واحد ممكن أن يعرف حل مرشح جزئي كقائمة من الأعداد الصحيحة س=(س[1]، س[2]....س[ك])، لا ك بين 0 ون، التي سيتم تعيينها لأول ك متغيرات (ص[1]، ص[2]....ص[ك])، الجذر المرشح سوف يصبح قائمة فارغة ().  الاجراءات الأولى والتالي سوف تصبح:

function first(P,c)
  k ← length(c)
  if k = n
    then return Λ
  else return (c[1], c[2], ..., c[k], 1)

function next(P,s)
  k ← length(s)
  if s[k] = m
    then return Λ
  else return (s[1], s[2], ..., s[k-1], 1 + s[k])

هنا "length(c)" هو عدد العناصر في المجموعة س

المناداة reject(P,c) يجب أن يرجع صحيح إذا الشرط ق لا يمكن تحقيقها بأي مجموعة من ن أعداد صحيحة التي تبدأ بـ ك عناصر من س. لخوارزمية الرجوع في الطريق لتصبح فعالة، يجب أن يكون هنالك طريقة للكشف عن هذه الحالة، على الأقل لبعض الحلول المرشحة س، بدون عد كل $م^(ن-ك) ن$-صفوف.

مثلاُ، إذا ق هو الاقتران للعديد من المسندات المنطقية، ق = ق[1]^ق[2]^...^ق[ب]، وكل ق[أ] يعتمد فقط على مجموعة فرعية صغيرة من المتغيرات ص[1]... ص[ن]، وبعدها إجراء الرفض يمكن أن يفحص الشروط ق[أ] التي تعتمد فقط على المتغيرات ص[1]... ص[ك]، وترجع صحيح إذا أي من هؤلاء الشروط التي ترجع خطأ. في الحقيقة، الرفض يحتاج فقط لفحص هؤلاء الشروط التي تعتمد على ص[ك]، بما أن الشروط تعتمد فقط على ص[1]... ص[ك-1] سوف تختضع لفحص اضافي في شخرة البحث.  

لنفترض ان الرفض هو مثل ما هو منفذ في الأعلى، و accept(P,c) يحتاج فقط أن يفحص إذا كانت س كاملة، هذا هو، إذا كان عندها ن عناصر.

انه بشكل عام أفضل أن ترتب مجموعة من المتغيرات لتبدأ بأكثر واحدة حساسة. 

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

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

كبديل لأثر متغير هو بالاحتفاظ بالطابع الزمني عند آخر تغيير قد حدث للمتغير. نقارن الطابع الزمني مع نقطة اختيار الطابع الزمني. إذا كانت نقطة الاختيار لها ارتباط زمني لاحق من ذلك المتغير، هو غير مهم لعودة المتغير عندما ننفذ هذه الخوارزمية على نقطة الاختيار، كما كانت متغيرة قبل ما حدثت نقطة الاختيار. 

انظر أيضاً

• Ariadne's thread (logic)
• Backjumping
• Recursion (computer science)

روابط خارجية

• HBmeyer.de, Interactive animation of a backtracking algorithm
• Solving Combinatorial Problems with STL and Backtracking, Article and C++ source code for a generic implementation of backtracking
• Sample Java Code, Sample code for backtracking of 8 Queens problem.