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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

در الگوریتم‌های پس‌گرد (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 استفاده میکنیم همانند x1,…,xj=a1,…,aj. این کار زمانی اتفاق می‌افتد که قابل بسط بیشتر برای ساختن یک راه حل برای xk+1 نیستیم. اگر الگوریتم بتواند اثبات کند این نکته را، می‌تواند به صورت مستقیم یک گره جدیدی برای xj به جای xk جدید انتخاب نماید.

Backjump-variables-1.svg Backjump-variables-2.svg Backjump-variables-3.svg
در این مثال مقدار فعلی اختصاص داده شده x1x2x3x4 به صورت نا موفق با با گره x5 آزمون شده‌است. در روش پس‌گرد به گره x4 رفته و مقدار این گره را برای بررسی انتخاب میکند. به جای روش پس‌گَرد، الگوریتم برخی پیچیدگیهایی اضافه میکند برای اثبات این نکته که x1x2x5=211 , x1x5=22 , x1x2x5=213 هیچ کمکی به پیدا کردن راه حل مسئله ندارند. در نتیجه، مقایسه فعلی x1x2 بخشی از جواب راه حل نیست و الگوریتم میتواند مستقیما عمل پس‌پرش را انجام دهد و یک مقدار جدیدی را مورد آزمون قرار دهد.

میزان بهره‌وری الگوریتم پس‌پرش میزان پرش به عقبی است که می‌تواند اتفاق بیافتد. به صورت ایده آل در این روش میتوان از xk+1 پرش کرد به هر متغیری مانند xj که در سری وجود دارد رفت و یا در بدترین حالت پیش آمده عمل پرش به xk+1 انجام پذیرد. که به این خانه، خانه پرش امن گفته میشود.

تشخیص این نکته که آیا پرش امن است یا خیر همواره امکان پذیر نیست، پیدا کردن روشهایی برای اطمینان یافتن پرشهای امن کاری است که در این الگوریتم سهی میشود انجام داد. عملا در الگوریتم پس‌پرش از حداقل ایندکس گذاریها برای پیدا کردن خانه امن استفاده میشود تا بهره وری کل الگوریتم حفظ شود. الگوریتم‌های مختلف روشهای متنوعی را برای یافتن پرش امن مورد استفاده قرار می‌دهند. که البته هزینه‌های هر کدام از این روشها نیز متفاوت است. اما ممکن است هزینه‌های تحمیلی ارزش این را داشته باشد که کاهش جستجوی بخش‌هایی از درخت حذف نماید.

پس‌پرش در گره‌های برگ[ویرایش]

در پس‌پرش ساده‌ترین شرایط زمانی است که بدون اینکه شاخهٔ دیگری مورد برسی قرار بگیرد ثابت شود تمامی مقادیری که یک گره با موارد مورد جستجو نامرتب هستند. قید رضایت بخش این است که قدم بعدی بسیار با اطمینان و محکم برداشته شود که موجب خراب شدن روند جستجو با توجه به تمامی متغیّرهای درگیر نشود در غیر این صورت این گام نامناسب نامیده میشود. این موضوع بیانگر این نکته‌است که پیدا کردن قدم کاملا مناسب بعضی وقتها وابسته به گره‌هایی است که تا به حال درگیر نشده‌اند و برخی متغیرهای تخصیص داده نشده ممکن نیست مورد بررسی قرار بگیرند مادامیکه شرایط دیگری بوجود نیاید.

به شرایطی که در آن همه مقادیر داده شده متغیر xk+1 دارای مقادیر نامناسب در سری x1,…,xk = a1,…,ak باشد را گره بن‌بست مینامیم. این شرایط دقیقا زمانی می‌تواند رخ دهد که متغیر xk+1 یک برگ از درخت جستجو باشد. (دقیقا همانند گره‌هایی که تنها برگ‌هایی به عنوان فرزند دارند و در شکل این مقاله میتوانید آنرا ببینید)

الگوریتم پس‌پرش ارائه شده توسط Gasching تنها عملیات پرش به عقب را در برگ‌های انتهایی درخت انجام میدهد در این روش مقادیر احتمالی برای xk+1 امتحان شده در گره آخر، در صورت نامناسب بودن نتیجه مقایسه عملیات فرآیند برگشت به عقب را فراخوانی میکند. درواقع این روش کمی با عملیات پرش به عقب معمول متفاوت است.

پرش امن به سادگی با محاسبهٔ ساده‌ای برای هر مقدار ak+1 بدست میآید، کمترین پیشوند موجود در سری x1,…,xk = a1,…,ak بدست میآید. به عنوان مثال اگر برای ak+1 مقدار xk+1 محتمل باشد، الگوریتم ما حالت‌های مناسب و محتمل زیر را بررسی و در مورد مناسب بودن خانه نتیجه گیری میکند:

x_1=a_1 ... x_{k-1}=a_{k-1} x_k=a_k x_{k+1}=a_{k+1}
x_1=a_1 ... x_{k-1}=a_{k-1} x_{k+1}=a_{k+1}
...
x_1=a_1 x_{k+1}=a_{k+1}

پرش امن برای خانه‌هایی که نامناسب شناخته میشوند کوچکترین ایندکس گره‌است مثلا پرش امن در شرایط xk+1=ak+1 تنها مقدار محتمل مناسب برای xk+1 است. از آنجاییکه هر متغیر معمولا می‌تواند بیش از یک مقدار بپذیرد، حداکثرایندکسی که از بررسی هر مقدار بیرون میآید را پرش امن مینامیم و این دقیقا زمانی است که الگوریتم گشینگ پرش مینماید.

در عمل این الگوریتم همزمان مشغول انجام محاسبه‌های گفته شده در بالا و نیز بررسی کردن سازگاری xk+1=ak+1 است.

پس‌پرش در گره‌های داخلی[ویرایش]

در قسمت قبل روش کار الگوریتم برای زمان‌هایی که شاخهٔ دیگری وجود ندارد و زمانیکه مقادیر یک متغیر به صورت نامتناسب در انتهای شاخه بود را مورد بررسی قراردادیم. در روش قبلی به هنگام جستجوی درخت زمانی اجازه پس‌پرش داده میشد که در گره‌های برگ قرارمیداشتیم و گره دیگری وجود نمیداشت.

یک گره داخلی از درخت جستجو نشان دهنده تخصیص یک متغیر است که سازگار با قبلی. اگر گره مناسب برای و حائز شرایطی برای پس‌پرش پیدا نشد از روش پس‌گرد استفاده میشود.

گره‌های درونی در پس‌پرش نمیتوانند همانند حرکتی که در برگهای انتهایی یک درخت انجام می‌گرفت را انجام بدهند. اگر درجایی محاسبه xk+1 نیازمند حرکت در شاخه‌ها شد این به این خاطر است متغیر اختصاص داده شده مناسب است و از همین متغیر میتوان برای مقایسه‌ها استفاده نمود. در نتیجه گشتن به دنبال پیشوندی که با مقادیر متغیر انتخاب شده نامناسب باشد هرگز به عنوان گره مناسب شناخته نمیشود.

در این جور مواقع الگوریتم متوجه شده‌است که مقادیر xk+1=ak+1 راه حل را برای موضوع مورد نظر به ارمغان نمیآورد و موضوع به جستجوی بازگشتی از سری x1,…,xk تبدیل میشود. در واقع الگوریتم میداند که هیچ راه حلی در این نقط وجود ندارد که به حل کل موضوع کمک کند زیرا به جای خاتمه دادن، مجددا به همین نقطه‌ای که در حال حاضر قرار داد بر خواهد گشت و دچار حلقه بی انتها میگردد.

این بازگشت مربوط است به تعداد بن‌بست‌ها و نقاطی که الگوریتم آنهارا به عنوان نقاط نامناسب و خارج از راه حل شناسایی کرده‌است. برای پس‌پرش‌های بلندتر این الگوریتم نیازمند شناسایی این بن‌بست‌ها است تا برای رسیدن به جواب مسئله از این بن‌بست‌ها دوری کند. در واقع پرش‌های امن ایندکس‌گذاری شده‌اند و پسوندهایی که از نقاط کور متمایز شده‌اند.

Dead-ends-1.svg Dead-ends-1a.svg Dead-ends-2.svg Dead-ends-3.svg
در این مثال، پس از اینکه الگوریتم تمامی مقادیر محتمل را مورد بررسی قرار داد، به خانه xk+1 بازمیگردد چرا که موفق به شناسایی 3 نقطه نا مرتبی شده که روی آنها ضربدری کشیده شده‌است. نقطه دوم به صورت نامناسب باقی میماند حتی اگر مقادیر xk-1 وxk در لیست کاندیدهای برسی موجود باشند.توجه داشته باشید که مقادیر یک متغیر در بچه‌های قرار دارد. حتی بدون xk-2 وxk و xk-1 باقی نقاط همانطور نامناسب شناخته شده‌اند. الگوریتم میتواند به خانهxk-2، برگردد زیرا این خانه دارای کمترین متغیر نا مناسب میباشد. مقدار جدیدی برای xk-2 مورد آزمون قرار خواهد گرفت.

به عبارت دیگر زمانیکه همه مقادیر xk+1 مورد آزمون قرار گرفت، الگوریتم توانایی پس‌پرش به متغیری همچون xi را دارد به شرط آنکه ارزیابی سری xk+1,xk+2,… در برگهایی که بچه‌های گره xk+1 هستند نامناسب باشد. سری حرا همچنان x1,…,xi در نظر بگیرید.

ساده‌سازی‌ها[ویرایش]

در حالی که به دنبال یک پس‌پرش برای xk+1 هستیم، گره‌ها در منطقه سایه می‌توانند نادیده گرفته شوند.

به منظور ساده سازی حجم عظیمی از گره‌هایی که در زیر درخت 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 نامناسب ناخته شده‌اند، ایندکسهایی که کوچکتر یا مساوی k که در محدوده xi هست میتواند به عنوان محلی برای پیدا کردن پرش امن از آنها استفاده نمود. به صورت دقیقتر، زمانیکه تمامی مقادیر برای xk+1 مورد بررسی قرار گرفت مجموعه‌ای از ایندکسهای متغیرهایی که باعث بوجود آمدن راه حل نهایی نمیشود شناسایی شده و بنابراین این نتیجه گرفته میشود که از ملاقات زیر درخت xk+1 هیچ راه حل قابل توجهی بدست نخواهد آمد. در این مواقع الگوریتم میتواند پرش به عقب به باارزشترین ایندکس موجود در مجموعه را انجام دهد.

از طریق الگوریتم زیر میتوان به طور کامل زمان استفاده از پس‌پرش از گره‌هایی که بازدید نکردیم و این گره‌ها را کنار گذاشته‌ایم را بطور کامل متوجه شوید: زمانیکه از یک گره به عقب بازمیگردیم مجموعه‌ای از متغیرها که درمحدودیت خود این گره و فرزندان آن وجود دارند و حتی والد والدین گره میتوانند به عنوان کاندیدهای گره مقصد برای پرش مطرح شوند. در هر گره داخلی، مجموعه‌ای از متغیرها حفظ شده‌است. هر زمان که مجموعه‌ای از متغیرها از یکی از فرزندان و یا نوادگان دریافت شد، این اطلاعات به مجموعه والد برای نگهداری بازگردانده میشود. زمانیکه نیاز به پس‌پرش و یا پس‌گرد از گره‌ای نیاز بود، متغیرهای آن گره از لیست این مجموعه حذف میشوند و این اطلاعات به گره مقصدی که به آن حرکت میکنیم تحویل داده میشود. الگوریتم این رفتار را انجام میدهد برای اینکه مجموعه‌ای را که در گره وجود دارد حاوی متغیرهایی است که در طول بررسی آن گره جمع آوری شده‌است و این اطلاعات حاوی نتایج با ارزشی در مورد گره‌های زیر دست است. یه این خاطر است که تنها زمانیکه پرش به عقب اتفاق میافتد مجموعه متغیرها ارسال میشوند به گره مقصد، از این رو است که اطلاعات مربوط به گره‌ای که از آن پرش شده قابل چشم‌پوشی است.

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

همچنین یک روش بهینه شده در این الگوریتم وجود دارد که بعضی وقتها میتواند به پرشهای بسیار بلندتری دست یابد. این کار تنها با برسی دو متغیر پیش رو در محدوده انجام نمیشود بلکه با برسی اینکه آیا مانعی باعث نامناسب شناخته شدن یک گره شده‌است یا خیر نیز قابل انجام است. این الگوریتم یک عامل بن بست در گره را شناسایی میکند. در هر گره بزرگترین ایندکس یک متغیر که در یکی از نقاط برگها شناسایی شده باشد به عنوان گره امن پرش محسوب میشود.

خانه‌های نامناسب شناسایی شده در هر برگ امنیت نتیجه پرش را بسیار بالا میبرند، از همین رو انتخاب کردن مناسبترین ایندکس، احتمال پرش‌های بلنتر را بشدت افزایش میدهد. به همین خاطر است که در این روش پرش به عقب، ترتیب خانه‌های نامناسب و دارای ارزش پایین تر هرگز بر خانه‌های دارای درجه و اهمیت بالاتر ترجیح داده نمیشود.

بعبارت دیگر، خانه C یک گراف نسبت به خانه D ترجیح داده میشود اگر بزرگترین ایندکس متغیر C پایین تر باشد از بزرگترین ایندکس متغیر D. درواقع به هنگام مواجه با متغیرهای مشترک، آن خانه از گراف انتخاب میشود که از ایندکسهای کوچکتری نسبت به سایرین برخوردار باشد.

الگوریتم در گره‌های برگ، کوچکترین ایندکس مثل i را با آخرین ایندکس مورد ارزیابی قرارمیدهد تا از این راه خانه نامناسب را شناسایی کند. ازبین خانه‌های با ارزش شناسایی شده شروع به مقایسه ایندکسهای مجموعهxk+1 برای انتخاب بهترین خانه میکند. به این ترتیب، زمانیکه الگوریتم مجددا بازمیگردد به متغیر xk+1، کمترین ایندکس جمع آوری شده بیانگر پرش امن است.

در عمل این الگوریتم بوسیله جمع آوری تمام ایندکسها ساده در یک مجموعه واحد ودر واقع به جای تولید کردن لیستهای مجزابرای هر k سازی میشود به صورت خاص تر این الگوریتم در هر گره به جمع آوری همه مجموعه‌هایی که از فرزندانش به هنگام پرش به عقب جمع آوری کرده‌است میپردازد. زمان پرش به عقب از این گره، این مجموعه حذف میشود و تمامی اطلاعاتی که تا به حال جمع آوری کرده به هنگام پرش به عقب یا بازگشت به عقب را به خانه مقصد تحویل میدهد.

این روش پرش به عقب توسط پتریک پراسر (Patrick Prosser) در سال ۱۹۹۳ برای مطلوب‌سازی مشکلات زمان بن بست ارائه شده‌است.

جستارهای وابسته[ویرایش]

  • آموزش محدودیت

منابع[ویرایش]