القفز للخلف

في برمجة القيود وحل مسائل SAT ، يُعدّ التراجع اللاحق (المعروف أيضًا بالتراجع غير الزمني ^{[ 1 ]} أو التراجع الذكي ^{[ 2 ]} ) تحسينًا لخوارزميات التراجع، حيث يُقلّل من مساحة البحث . بينما ينتقل التراجع دائمًا إلى مستوى أعلى في شجرة البحث عند اختبار جميع قيم المتغير، قد ينتقل التراجع اللاحق إلى مستويات أعلى. في هذه المقالة، سنعتمد ترتيبًا ثابتًا لتقييم المتغيرات.${\displaystyle x_{1},\ldots ,x_{n}}$يتم استخدامها، ولكن تنطبق نفس الاعتبارات على الترتيب الديناميكي للتقييم.

• 
  شجرة بحث تتم زيارتها من خلال التراجع المنتظم
• 
  قفزة للخلف: لم تتم زيارة العقدة الرمادية

عندما تختبر عملية التراجع جميع قيم متغير ما دون إيجاد حل، فإنها تعيد النظر في آخر المتغيرات التي تم تعيينها مسبقًا، فتغير قيمته أو تتراجع أكثر إذا لم تكن هناك قيم أخرى يجب تجربتها.${\displaystyle x_{1}=a_{1},\ldots ,x_{k}=a_{k}}$يمثل هذا التخصيص الجزئي الحالي وجميع القيم لـ${\displaystyle x_{k+1}}$بعد تجربة عدة حلول دون التوصل إلى حل، خلصت عملية التراجع إلى أنه لا يوجد حل موسع. ${\displaystyle x_{1}=a_{1},\ldots ,x_{k}=a_{k}}$موجود. ثم "تصعد" الخوارزمية إلى${\displaystyle x_{k}}$، التغيير${\displaystyle x_{k}}$قيمة 's إن أمكن، وإلا فارجع إلى الوراء.

لا يكون التخصيص الجزئي ضروريًا دائمًا لإثبات عدم وجود قيمة لـ${\displaystyle x_{k+1}}$يؤدي ذلك إلى حل. على وجه الخصوص، قد يكون لبادئة التخصيص الجزئي نفس الخاصية، أي أنه يوجد فهرس${\displaystyle j<k}$بحيث${\displaystyle x_{1},\ldots ,x_{j}=a_{1},\ldots ,a_{j}}$لا يمكن توسيعها لتشكيل حل مهما كانت قيمة لـ${\displaystyle x_{k+1}}$إذا استطاعت الخوارزمية إثبات هذه الحقيقة، فيمكنها مباشرةً النظر في قيمة مختلفة لـ${\displaystyle x_{j}}$بدلاً من إعادة النظر${\displaystyle x_{k}}$كما هو معتاد.

• 
  مثال على المهمة الحالية لـ${\displaystyle x_{1}x_{2}x_{3}x_{4}}$تمت تجربتها دون جدوى مع كل قيمة ممكنة لـ${\displaystyle x_{5}}$. التراجع يعود إلى${\displaystyle x_{4}}$، محاولة تعيين قيمة جديدة لها.
• 
  بدلاً من التراجع، تُجري الخوارزمية بعض التوضيحات الإضافية، مما يثبت أن التقييمات${\displaystyle x_{1}x_{2}x_{5}=211}$،${\displaystyle x_{1}x_{2}x_{5}=212}$، و${\displaystyle x_{1}x_{2}x_{5}=213}$ليست جزءًا من أي حل.
• 
  ونتيجة لذلك، فإن التقييم الحالي لـ${\displaystyle x_{1}x_{2}}$لا يُعد جزءًا من أي حل، ويمكن للخوارزمية أن تعود مباشرةً إلى${\displaystyle x_{2}}$، تجربة قيمة جديدة لها.

تعتمد كفاءة خوارزمية القفز العكسي على مدى ارتفاع القفزة العكسية التي يمكنها القيام بها. من الناحية المثالية، يمكن للخوارزمية أن تقفز من${\displaystyle x_{k+1}}$إلى أي متغير${\displaystyle x_{j}}$إن المهمة الحالية لـ${\displaystyle x_{1},\ldots ,x_{j}}$لا يمكن تمديدها لتشكيل حل بأي قيمة من${\displaystyle x_{k+1}}$إذا كان هذا هو الحال،${\displaystyle j}$يُطلق عليه اسم القفزة الآمنة .

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

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

الحالة التي تكون فيها جميع قيم متغير معين${\displaystyle x_{k+1}}$وهي لا تتفق مع الحل الجزئي الحالي${\displaystyle x_{1},\ldots ,x_{k}=a_{1},\ldots ,a_{k}}$يُطلق عليه اسم طريق مسدود . يحدث هذا بالضبط عندما يكون المتغير${\displaystyle x_{k+1}}$هي ورقة من شجرة البحث (والتي تتوافق مع العقد التي تحتوي على أوراق فقط كأبناء في أشكال هذه المقالة).

لا تقوم خوارزمية التراجع التي وضعها جون غاشنيغ بالتراجع إلا في النهايات المسدودة للأوراق. ^{[ 3 ]} بعبارة أخرى، فهي تعمل بشكل مختلف عن التراجع فقط عندما تكون كل قيمة ممكنة لـ${\displaystyle x_{k+1}}$تم اختبارها وأظهرت نتائج غير متسقة دون الحاجة إلى التفرع على متغير آخر.

يمكن إيجاد قفزة آمنة ببساطة عن طريق التقييم، لكل قيمة${\displaystyle a_{k+1}}$، أقصر بادئة لـ${\displaystyle x_{1},\ldots ,x_{k}=a_{1},\ldots ,a_{k}}$غير متسق مع${\displaystyle x_{k+1}=a_{k+1}}$بمعنى آخر، إذا${\displaystyle a_{k+1}}$قيمة محتملة لـ${\displaystyle x_{k+1}}$، تتحقق الخوارزمية من اتساق التقييمات التالية:

${\displaystyle x_{1}=a_{1}}$	...	${\displaystyle x_{k-1}=a_{k-1}}$	${\displaystyle x_{k}=a_{k}}$	${\displaystyle x_{k+1}=a_{k+1}}$
${\displaystyle x_{1}=a_{1}}$	...	${\displaystyle x_{k-1}=a_{k-1}}$		${\displaystyle x_{k+1}=a_{k+1}}$
...
${\displaystyle x_{1}=a_{1}}$				${\displaystyle x_{k+1}=a_{k+1}}$

أصغر مؤشر (أدنى مستوى في القائمة) الذي تكون فيه التقييمات غير متسقة سيكون قفزة آمنة إذا${\displaystyle x_{k+1}=a_{k+1}}$كانت القيمة الوحيدة الممكنة لـ${\displaystyle x_{k+1}}$بما أن كل متغير يمكن أن يأخذ عادةً أكثر من قيمة واحدة، فإن الفهرس الأقصى الذي ينتج عن فحص كل قيمة هو قفزة آمنة، وهي النقطة التي تقفز عندها خوارزمية جون غاشنيغ.

عمليًا، يمكن للخوارزمية التحقق من التقييمات المذكورة أعلاه في نفس الوقت الذي تتحقق فيه من اتساق${\displaystyle x_{k+1}=a_{k+1}}$.

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

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

لا يمكن إجراء القفز العكسي عند العقد الداخلية كما هو الحال بالنسبة للعقد الطرفية. في الواقع، إذا كانت بعض تقييمات${\displaystyle x_{k+1}}$يتطلب الأمر تفرعًا، وذلك لأنها تتوافق مع التعيين الحالي. ونتيجة لذلك، فإن البحث عن بادئة لا تتوافق مع هذه القيم للمتغير الأخير لن ينجح.

في مثل هذه الحالات، ما الذي أثبت التقييم؟${\displaystyle x_{k+1}=a_{k+1}}$عدم المشاركة في حل من خلال التقييم الجزئي الحالي${\displaystyle x_{1},\ldots ,x_{k}}$هو البحث التكراري . على وجه الخصوص، "تعرف" الخوارزمية أنه لا يوجد حل من هذه النقطة فصاعدًا لأنها تعود إلى هذه العقدة بدلاً من التوقف بعد العثور على حل.

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

• 
  في هذا المثال، تعود الخوارزمية إلى${\displaystyle x_{k+1}}$، بعد تجربة جميع قيمها الممكنة، بسبب نقاط التناقض الثلاث المتقاطعة.
• 
  تبقى النقطة الثانية غير متسقة حتى لو كانت قيم${\displaystyle x_{k-1}}$و${\displaystyle x_{k}}$يتم استبعادها من تقييمها الجزئي (لاحظ أن قيم المتغير موجودة في عناصره الفرعية).
• 
  أما التقييمات الأخرى غير المتسقة فتبقى كذلك حتى بدون${\displaystyle x_{k-2}}$،${\displaystyle x_{k-1}}$، و${\displaystyle x_{k}}$
• k-2 لأنها أصغر قيمة للمتغيرات التي تحافظ على جميع التناقضات. سيتم تجربة قيمة جديدة لـ x_k-2." id="mwAYw">
  يمكن للخوارزمية أن تعود إلى الوراء${\displaystyle x_{k-2}}$بما أن هذه هي أقل المتغيرات التي تحافظ على جميع التناقضات. قيمة جديدة لـ${\displaystyle x_{k-2}}$سيتم المحاولة.

بمعنى آخر، عندما تكون جميع قيم${\displaystyle x_{k+1}}$بعد تجربة ذلك، يمكن للخوارزمية الرجوع إلى متغير سابق${\displaystyle x_{i}}$شريطة أن يكون التقييم الحالي للحقيقة${\displaystyle x_{1},\ldots ,x_{i}}$يتعارض مع جميع تقييمات الصدق لـ${\displaystyle x_{k+1},x_{k+2},...}$في العقد الورقية التي تنحدر من العقدة${\displaystyle x_{k+1}}$.

التبسيطات

بسبب العدد الكبير المحتمل للعقد الموجودة في الشجرة الفرعية لـ${\displaystyle x_{k+1}}$المعلومات اللازمة للقفز للخلف بأمان من${\displaystyle x_{k+1}}$يتم جمع البيانات أثناء زيارة الشجرة الفرعية. يمكن تبسيط إيجاد قفزة آمنة من خلال اعتبارين. أولهما أن الخوارزمية تحتاج إلى قفزة آمنة، ولكنها تعمل مع قفزة ليست أعلى قفزة آمنة ممكنة.

التبسيط الثاني هو أن العقد في الشجرة الفرعية لـ${\displaystyle x_{l}}$يمكن تجاهل الخطوات التي تم تخطيها بالقفزة الخلفية أثناء البحث عن قفزة خلفية لـ${\displaystyle x_{l}}$وبشكل أدق، جميع العقد التي تم تخطيها بالقفز للخلف من العقدة${\displaystyle x_{m}}$حتى العقدة${\displaystyle x_{l}}$لا علاقة لها بالشجرة الفرعية التي جذرها في${\displaystyle x_{m}}$وكذلك فروعها الفرعية الأخرى غير ذات صلة.

في الواقع، إذا تعطلت خوارزمية من العقدة${\displaystyle x_{l}}$ل${\displaystyle x_{m}}$عبر مسار، لكنه يتراجع في طريق عودته، ثم كان بإمكانه الذهاب مباشرة من${\displaystyle x_{l}}$ل${\displaystyle x_{m}}$بدلاً من ذلك. في الواقع، تشير القفزة الخلفية إلى أن العقد بين${\displaystyle x_{l}}$و${\displaystyle x_{m}}$لا علاقة لها بالشجرة الفرعية التي جذرها في${\displaystyle x_{m}}$بمعنى آخر، يشير التراجع إلى أن زيارة منطقة معينة من شجرة البحث كانت خطأً. لذا، يمكن تجاهل هذا الجزء من شجرة البحث عند النظر في احتمال حدوث تراجع من${\displaystyle x_{l}}$أو من أحد أسلافها.

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

• التراجع
• التعلم المقيد
• تعلم البنود المدفوعة بالصراع
• النظر إلى الأمام (التراجع)
• برنامج GRASP (لحل مشكلة SAT)