الگوریتم پسگرد
 |
پیشنهاد شدهاست که این مقاله یا بخش با عقبگرد (الگوریتم) ادغام گردد. |
روش پسگرد نوعی الگوریتم برای پیدا کردن جواب برخی از مسائل است. پسگرد می کوشد تا با آزمایش همهٔ ترکیبهای ممکن، یک جواب پیدا کند. در پسگرد تعدادی از حالات بدون انکه صریحاَ آزمایش شوند، با در نظر گرفتن ویژگیهای مسئله، نادیده گرفته میشوند. واژهٔ BackTrack به وسیلهٔ یک ریاضی دان آمریکایی به نام D.H. lehmer در سال 1950 ابداع شد.
محتویات |
توضیح [ویرایش]
نقطه قوت این الگوریتم آن است که در بسیاری ازپیاده سازیها نیاز به آزمایش همه ترکیبات ندارند و این موجب سریع بودن الگوریتم میشود.
پیاده سازی [ویرایش]
پسگرد همه احتمالات را آزمایش میکند تا حالت درست را بیابد. این یک جستجوی عمق اول بین جوابهای ممکن است. هنگام جستجو اگر راهی که طی میشود نتیجه نداد ( به جواب نرسید ) به نقطهٔ قبلی بازمی گردد و راه بعدی را امتحان میکند . اگر همه راهها را امتحان کرد و به جواب نرسید، جستجو نا موفق بوده است. این الگوریتم معمولاَ با توابع بازگشتی پیاده سازی میشود. به این صورت که در هر بار فراخوانی تابع، با اضافه شدن یک متغیر به طور متناوب همهٔ مقادیر ممکن را به آن نسبت میدهد و آن مقداری که با فراخوانیهای بازگشتی بعدی سازگار است را ذخیره میکند. پسگرد مانند جست و جوی عمق-اول است با این تفاوت که فضای کمتری اشغال میکند.
کاربردها [ویرایش]
یکی از استفادههای رایج از این الگوریتم، پیاده سازی عبارات باقاعده است . برای مثال الگوی سادهٔ "a*a" بدون استفاده از روش پسگرد با عبارت "aa" سازگار دیده نمیشود ( چون a دوم با * از بین میرود و چیزی برای تطابق با a آخر وجود ندارد.) یکی دیگر از موارد استفاده از پسگرد، الگوریتمهای مسیریاب است که با رفت و برگشت بر روی راسهای یک گراف، کم هزینهترین مسیر را پیدا میکند. همچنین استراتژی پسگرد در پیاده سازی زبانهای برنامه نویسی و چیزهای دیگر مانند تجزیه متنها کاربرد دارد.
