پس‌پرش (الگوریتم)

در الگوریتمهای پس‌گرد (backtrack) روشی به نام پَس‌پَرش (backjumping) وجود دارد که باعث کاهش فضای جستجو، در نتیجه افزایش بهره‌وری است. در پس‌گرد همواره یک سطح در درخت جستجو بالا می‌رویم زمانی‌که تمامی مقادیر گره‌ها بررسی شده باشند، اما در روش پس‌پرش ممکن است چندین سطح به بالا پرش انجام دهیم. در این مقاله، مقادیر امتحانی ثابتی در نظر گرفته‌ایم x1 , x2 , … ,xn که ممکن است به صورت غیر مرتّب نیز از آن‌ها استفاده نماییم.

ساده‌سازی‌ها

به منظور ساده‌سازی حجم عظیمی از گره‌هایی که در زیر درخت xk+1 وجود دارند، اطلاعات ضروری برای پس‌پرش امن در زمان بازدید از زیر درخت گره xk+1 جمع‌آوری می‌شود. پیدا کردن یک پرش امن را می‌توان توسط دو ملاحظات ساده شده انجام داد. اولین موضوع، الگوریتم نیازمند پرش امن است اما لزوماً به دنبال بلندترین پرش امن ممکن نیست.
موضوع دوم این است که گره‌های موجود در زیر درخت xl که از آن‌ها با استفاده از پس‌پرش پریدیم را می‌توان به‌طور کامل نادیده بگیریم. به صراحت می‌توان گفت تمام گره‌هایی در مسیر خانه xm تا خانه xl هستند نامرتبط با زیر درخت xm هستند؛ بنابراین می‌توان تمامی گره‌های این زیر مجموعه را نادیده گرفت.
در واقع اگر در این الگوریتم از گره xl تا xm به سمت پایین حرکت کردیم و در بین راه مجبور به پرش به عقب شدیم، می‌توانیم مستقیماً به گره xm مراجعت نماید. در واقع در اینجا پرش به عقب بیانگر این نکته‌است که گره‌هایی که فی‌مابین گره‌های xl و xm هستند کاملاً نامرتبط اند به زیر درخت گره xm. به عبارت دیگر پرش به عقب نشان دهنده این نکته‌است که بازدیداز یک ناحیه درخت جستجو می‌توانسته کاملاً اشتباه باشد؛ بنابراین این قسمت از درخت جستجو می‌تواند کاملاً نادیده گرفته شود و پرش به گره xl ویا والدهای بالاتر گره والد اتفاق بیفتد
در هرگره می‌توان از این نکته برای جمع‌آوری مجموعه‌ای از اطلاعات بخصوص یافتن متغیرهای پیشین اختصاص داده شده به منظور اثبات این نکته که هیچ راه حلی در زیر درخت گره مورد نظر وجود ندارد استفاده نمود. این مجموعه جمع‌آوری اطلاعات در زمان اجرای الگوریتم ساخته می‌شود. زمانی‌که از یک گره برگشت به عقب می‌کنیم مجموعه تمام متغیرهای آن گره و اطلاعات جمع‌آوری شده دربارهٔ آن گره که مقصد پس‌پرش یا مقصد Backtrack آن کجا بوده‌است کاملاً حذف می‌شود. این اتفاق از آنجایی رخ می‌دهد که گره‌های پرش شده از پس‌پرش هرگز شانس بازدید شدن را نخواهند داشت بنابراین این گره‌ها خودکار حذف می‌شوند.

پس‌پرش‌های بر پایه گراف

منطق این نوع پرش به عقب که در گراف‌ها بکار برده می‌شود به این صورت است که یک پرش امن می‌تواند به وسیلهٔ چک کردن این نکته که کدام متغیر از سری x1,…،xk تناسب دارد با متغیرهای xk+1,xk+2,… که توسط گره‌های برگ معرفی می‌شوند. برای هر گره برگ و هر متغیر xi ی که ایندکس‌های i> نامناسب ناخته شده‌اند، ایندکسهایی که کوچکتر یا مساوی k که در محدوده xi هست می‌تواند به عنوان محلی برای پیدا کردن پرش امن از آن‌ها استفاده نمود. به صورت دقیقتر، زمانی‌که تمامی مقادیر برای xk+1 مورد بررسی قرار گرفت مجموعه‌ای از ایندکس‌های متغیرهایی که باعث به وجود آمدن راه حل نهایی نمی‌شود شناسایی شده و بنابراین این نتیجه گرفته می‌شود که از ملاقات زیر درخت xk+1 هیچ راه حل قابل توجهی بدست نخواهد آمد. در این مواقع الگوریتم می‌تواند پرش به عقب به باارزشترین ایندکس موجود در مجموعه را انجام دهد.
از طریق الگوریتم زیر می‌توان به‌طور کامل زمان استفاده از پس‌پرش از گره‌هایی که بازدید نکردیم و این گره‌ها را کنار گذاشته‌ایم را به‌طور کامل متوجه شوید: زمانی‌که از یک گره به عقب بازمی‌گردیم مجموعه‌ای از متغیرها که درمحدودیت خود این گره و فرزندان آن وجود دارند و حتی والد والدین گره می‌توانند به عنوان کاندیدهای گره مقصد برای پرش مطرح شوند. در هر گره داخلی، مجموعه‌ای از متغیرها حفظ شده‌است. هر زمان که مجموعه‌ای از متغیرها از یکی از فرزندان یا نوادگان دریافت شد، این اطلاعات به مجموعه والد برای نگهداری بازگردانده می‌شود. زمانی‌که نیاز به پس‌پرش یا پس‌گرد از گره‌ای نیاز بود، متغیرهای آن گره از لیست این مجموعه حذف می‌شوند و این اطلاعات به گره مقصدی که به آن حرکت می‌کنیم تحویل داده می‌شود. الگوریتم این رفتار را انجام می‌دهد برای اینکه مجموعه‌ای را که در گره وجود دارد حاوی متغیرهایی است که در طول بررسی آن گره جمع‌آوری شده‌است و این اطلاعات حاوی نتایج با ارزشی در مورد گره‌های زیر دست است. یه این خاطر است که تنها زمانی‌که پرش به عقب اتفاق میفتدمجموعه متغیرها ارسال می‌شوند به گره مقصد، از این رو است که اطلاعات مربوط به گره‌ای که از آن پرش شده قابل چشم‌پوشی است.

کشمکش‌های احتمالی در پس‌پرش

همچنین یک روش بهینه شده در این الگوریتم وجود دارد که بعضی وقتها می‌تواند به پرش‌های بسیار بلندتری دست یابد. این کار تنها با بررسی دو متغیر پیش رو در محدوده انجام نمی‌شود بلکه با بررسی اینکه آیا مانعی باعث نامناسب شناخته شدن یک گره شده‌است یا خیر نیز قابل انجام است. این الگوریتم یک عامل بن‌بست در گره را شناسایی می‌کند. در هر گره بزرگترین ایندکس یک متغیر که در یکی از نقاط برگ‌ها شناسایی شده باشد به عنوان گره امن پرش محسوب می‌شود.
خانه‌های نامناسب شناسایی شده در هر برگ امنیت نتیجه پرش را بسیار بالا می‌برند، از همین رو انتخاب کردن مناسبترین ایندکس، احتمال پرش‌های بلنتر را بشدت افزایش می‌دهد. به همین خاطر است که در این روش پرش به عقب، ترتیب خانه‌های نامناسب و دارای ارزش پایین‌تر هرگز بر خانه‌های دارای درجه و اهمیت بالاتر ترجیح داده نمی‌شود.
بعبارت دیگر، خانه  یک گراف نسبت به خانه  ترجیح داده می‌شود اگر بزرگترین ایندکس متغیر C پایین‌تر باشد از بزرگترین ایندکس متغیر D. در واقع به هنگام مواجه با متغیرهای مشترک، آن خانه از گراف انتخاب می‌شود که از ایندکس‌های کوچکتری نسبت به سایرین برخوردار باشد.
الگوریتم در گره‌های برگ، کوچکترین ایندکس مثل  را با آخرین ایندکس مورد ارزیابی قرارمیدهد تا از این راه خانه نامناسب را شناسایی کند. ازبین خانه‌های با ارزش شناسایی شده شروع به مقایسه ایندکس‌های مجموعهx برای انتخاب بهترین خانه می‌کند. به این ترتیب، زمانی‌که الگوریتم مجدداً بازمی‌گردد به متغیر xk+1، کمترین ایندکس جمع‌آوری شده بیانگر پرش امن است.
در عمل این الگوریتم به وسیلهٔ جمع‌آوری تمام ایندکس‌ها ساده در یک مجموعه واحد و در واقع به جای تولید کردن لیستهای مجزابرای هر ‌سازی می‌شود به صورت خاص تر این الگوریتم در هر گره به جمع‌آوری همه مجموعه‌هایی که از فرزندانش به هنگام پرش به عقب جمع‌آوری کرده‌است می‌پردازد. زمان پرش به عقب از این گره، این مجموعه حذف می‌شود و تمامی اطلاعاتی که تا به حال جمع‌آوری کرده به هنگام پرش به عقب یا بازگشت به عقب را به خانه مقصد تحویل می‌دهد.
این روش پرش به عقب توسط پتریک پراسر (Patrick Prosser) در سال ۱۹۹۳ برای مطلوب‌سازی مشکلات زمان بن‌بست ارائه شده‌است.