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

در الگوریتمهای پس‌گرد (backtrack) روشی به نام پس‌پرش (backjumping) وجود دارد که باعث کاهش فضای جستجو، در نتیجه افزایش بهره‌وری است. در پس‌گرد همواره یک سطح در درخت جستجو بالا می‌رویم زمانی‌که تمامی مقادیر گره‌ها بررسی شده باشند، اما در روش پس‌پرش ممکن است چندین سطح به بالا پرش انجام دهیم. در این مقاله، مقادیر امتحانی ثابتی در نظر گرفته‌ایم x1 , x2 , … ,xn که ممکن است به صورت غیر مرتب نیز از آن‌ها استفاده نماییم.
تعریف
در روش پس‌گرد زمانی‌که مقادیر یک متغیر مورد بررسی قرار بگیرد و جستجو بی‌نتیجه پایان یابد، الگوریتم مقدار آخرین متغیرهای گره پیشین مورد بررسی قرار می‌دهد ولی اگر به انتها رسید و تمامی گره‌ها بررسی شد و به جواب درستی نرسیدیم، مقدار گره جستجو را تغییر و عملیات جستجو دوباره تکرار می‌شود. اگر شرایط به این گونه باشد x1=a1,…،xk =ak وتمامی مقادیر برای xk+1 بدون نتیجه برای پیدا کردن راه کار به پایان برسد الگوریتم یک سطح به بالا یعنی گره xk می‌رود؛ و در صورت امکان، مقدار را عوض کرده و به بالا بازمی‌گردد و سپس دوباره این مراحل را تکرار می‌کند.
انتخاب مقدار تخصیص جزئی xk+1 همواره به صورت کامل برای پیدا کردن راه حل ضروری نیست چرا که اجبارا ما را به سمت جواب پایانی هدایت نمی‌کند. اگر شرایط به این گونه باشد x1=a1,…xk=ak و تمامی مقادیر برای xk+1 بدون نتیجه برای پیدا کردن راه کار به پایان برسد الگوریتم یک سطح به بالا یعنی گره xk رفته و در صورت امکان مقدار را عوض کرده سپس دوباره این مراحل را تکرار می‌کند. انتخاب مقدار تخصیص جزئی xk+1 همواره به صورت کامل برای پیدا کردن راه حل ضروری نیست اما یک پیشوند تخصیص جزئی ممکن است در حل مسائل ارزش زیادی داشته باشد. برای این منظور از ایندکسهایی با شرط j
نامناسب ناخته شده‌اند، ایندکسهایی که کوچکتر یا مساوی k که در محدوده xi هست می‌تواند به عنوان محلی برای پیدا کردن پرش امن از آن‌ها استفاده نمود. به صورت دقیقتر، زمانی‌که تمامی مقادیر برای xk+1 مورد بررسی قرار گرفت مجموعه‌ای از ایندکسهای متغیرهایی که باعث بوجود آمدن راه حل نهایی نمی‌شود شناسایی شده و بنابراین این نتیجه گرفته می‌شود که از ملاقات زیر درخت xk+1 هیچ راه حل قابل توجهی بدست نخواهد آمد. در این مواقع الگوریتم می‌تواند پرش به عقب به باارزشترین ایندکس موجود در مجموعه را انجام دهد.
از طریق الگوریتم زیر می‌توان به‌طور کامل زمان استفاده از پس‌پرش از گره‌هایی که بازدید نکردیم و این گره‌ها را کنار گذاشته‌ایم را بطور کامل متوجه شوید: زمانی‌که از یک گره به عقب بازمی‌گردیم مجموعه‌ای از متغیرها که درمحدودیت خود این گره و فرزندان آن وجود دارند و حتی والد والدین گره می‌توانند به عنوان کاندیدهای گره مقصد برای پرش مطرح شوند. در هر گره داخلی، مجموعه‌ای از متغیرها حفظ شده‌است. هر زمان که مجموعه‌ای از متغیرها از یکی از فرزندان یا نوادگان دریافت شد، این اطلاعات به مجموعه والد برای نگهداری بازگردانده می‌شود. زمانی‌که نیاز به پس‌پرش یا پس‌گرد از گره‌ای نیاز بود، متغیرهای آن گره از لیست این مجموعه حذف می‌شوند و این اطلاعات به گره مقصدی که به آن حرکت می‌کنیم تحویل داده می‌شود. الگوریتم این رفتار را انجام می‌دهد برای اینکه مجموعه‌ای را که در گره وجود دارد حاوی متغیرهایی است که در طول بررسی آن گره جمع‌آوری شده‌است و این اطلاعات حاوی نتایج با ارزشی در مورد گره‌های زیر دست است. یه این خاطر است که تنها زمانی‌که پرش به عقب اتفاق میفتدمجموعه متغیرها ارسال می‌شوند به گره مقصد، از این رو است که اطلاعات مربوط به گره‌ای که از آن پرش شده قابل چشم‌پوشی است.
کشمکش‌های احتمالی در پس‌پرش
همچنین یک روش بهینه شده در این الگوریتم وجود دارد که بعضی وقتها می‌تواند به پرشهای بسیار بلندتری دست یابد. این کار تنها با بررسی دو متغیر پیش رو در محدوده انجام نمی‌شود بلکه با بررسی اینکه آیا مانعی باعث نامناسب شناخته شدن یک گره شده‌است یا خیر نیز قابل انجام است. این الگوریتم یک عامل بن‌بست در گره را شناسایی می‌کند. در هر گره بزرگترین ایندکس یک متغیر که در یکی از نقاط برگ‌ها شناسایی شده باشد به عنوان گره امن پرش محسوب می‌شود.
خانه‌های نامناسب شناسایی شده در هر برگ امنیت نتیجه پرش را بسیار بالا می‌برند، از همین رو انتخاب کردن مناسبترین ایندکس، احتمال پرش‌های بلنتر را بشدت افزایش می‌دهد. به همین خاطر است که در این روش پرش به عقب، ترتیب خانه‌های نامناسب و دارای ارزش پایین‌تر هرگز بر خانه‌های دارای درجه و اهمیت بالاتر ترجیح داده نمی‌شود.
بعبارت دیگر، خانه یک گراف نسبت به خانه ترجیح داده می‌شود اگر بزرگترین ایندکس متغیر C پایین‌تر باشد از بزرگترین ایندکس متغیر D. در واقع به هنگام مواجه با متغیرهای مشترک، آن خانه از گراف انتخاب می‌شود که از ایندکسهای کوچکتری نسبت به سایرین برخوردار باشد.
الگوریتم در گره‌های برگ، کوچکترین ایندکس مثل را با آخرین ایندکس مورد ارزیابی قرارمیدهد تا از این راه خانه نامناسب را شناسایی کند. ازبین خانه‌های با ارزش شناسایی شده شروع به مقایسه ایندکسهای مجموعهx برای انتخاب بهترین خانه می‌کند. به این ترتیب، زمانی‌که الگوریتم مجددا بازمی‌گردد به متغیر xk+1، کمترین ایندکس جمع‌آوری شده بیانگر پرش امن است.
در عمل این الگوریتم بوسیله جمع‌آوری تمام ایندکسها ساده در یک مجموعه واحد و در واقع به جای تولید کردن لیستهای مجزابرای هر سازی می‌شود به صورت خاص‌تر این الگوریتم در هر گره به جمع‌آوری همه مجموعه‌هایی که از فرزندانش به هنگام پرش به عقب جمع‌آوری کرده‌است می‌پردازد. زمان پرش به عقب از این گره، این مجموعه حذف می‌شود و تمامی اطلاعاتی که تا به حال جمع‌آوری کرده به هنگام پرش به عقب یا بازگشت به عقب را به خانه مقصد تحویل می‌دهد.
این روش پرش به عقب توسط پتریک پراسر (Patrick Prosser) در سال ۱۹۹۳ برای مطلوب‌سازی مشکلات زمان بن‌بست ارائه شده‌است.
آموزش محدودیت