books method description

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

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

خوارزمية الرجوع في الطريق تقطع شجرة البحث هذه بطريقة الاستدعاء الذاتي تكراراً، من الاجذر الاسفل، الترتيب الغمق أولاً. في كل عقدة س، الخوارزمية تراجع إذا كانت س ممكن أن تكون حل صالح. إذا لم تكن، كل الشجرة المتفرعة من س سوف نتخطاها (نقطعها). وإلا، الخوارزمية (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 هي ما يلي من اجراء الاستدعاء الذاتي تكراراً : 

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

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

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

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

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

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

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

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

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