تعقب رجوعي

وصف الطريقة

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

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

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

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

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

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

أمثلة

مسائل الاندماج الامثل مثل التحليل ومسألة حقيبة السرقة.

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

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

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

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

تحقيق الشروط

• الاجراءات الأولى والتالي سوف تصبح:
• function first(P,c)
• k ← length(c)
• if k = n

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

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

سودو كود

• root(P): يرجع الحل المرشح الجزئي في الجذر من شجرة البحث
• reject(P,c): يرجع صحيح إذا كان الحل المرشح الجزئي س لا يستحق أن نكمله
• accept(P,c): يرجع صحيح إذا كانت س هي حل ل ب، وخطأ غير ذلك

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

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

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

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

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

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

وعلى صعيد آخر، إجراء الرفض يجب أن يكون اقتران قيمته منطقية حيث يرجع صحيح أو خطأ إذا كان متيقن لا يمكن إيجاد تمديد ل س لإيجاد حل صالح ل ب. إذا كان الاجراء لا يصل لاستنتاج واضح، يجب أن يرجع خطأ. أي حل إذا ارجع صحيح وكان غير صحيح يمكن أن يسبب إجراء bt أن يضيع بعض الحلول الصالحة.هذا الاجراء من الممكن أن يعتبر أن reject(P,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)

first(P,c): ينتج التمديد الأول للحل المرشح س

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

output(P,c): يستعمل الحل س ل ب، مناسب للتطبيق

وفي هذا الصدد، next(P,s): ينتج التمديد البديل التالي لحل مرشح، بعد التمديد ي س

then return Λ

• else return (c[1], c[2], ..., c[k], 1)
• function next(P,s)
• k ← length(s)
• if s[k] = m

then return Λ

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

• انظر كذلك
• عودية
• مراجع

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

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

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

وفي هذا السياق، else return (s[1], s[2], ..., s[k-1], 1 + s[k])هنا "length(c)" هو عدد العناصر في المجموعة س

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

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

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