الرئيسيةعريقبحث

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

☰ جدول المحتويات

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

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

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

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

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

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

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

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

انظر أيضاً

مراجع

  1. "معلومات عن الرجوع في الطريق على موقع mathworld.wolfram.com". mathworld.wolfram.com. مؤرشف من الأصل في 3 يوليو 2019.
  2. "معلومات عن الرجوع في الطريق على موقع xlinux.nist.gov". xlinux.nist.gov. مؤرشف من الأصل في 13 أكتوبر 2018.
  3. "معلومات عن الرجوع في الطريق على موقع aleph.nkp.cz". aleph.nkp.cz. مؤرشف من الأصل في 11 ديسمبر 2019.

Further reading

روابط خارجية

موسوعات ذات صلة :