روش پس‌گرد

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

روش پس‌گرد نوعی الگوریتم برای پیدا کردن جواب برخی از مسائل است. پسگرد می‌کوشد تا با آزمایش همهٔ ترکیب‌های ممکن، یک جواب پیدا کند. در پسگرد تعدادی از حالات بدون انکه صریحاً آزمایش شوند، با در نظر گرفتن ویژگی‌های مسئله، نادیده گرفته می‌شوند. واژهٔ BackTrack به وسیلهٔ یک ریاضی دان آمریکایی به نام D.H. lehmer در سال ۱۹۵۰ ابداع شد.

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

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

  1. (root(P:زیر مسئله ریشه را بر می‌گرداند.
  2. (reject(P,c:اگر c به جواب نرسد درست بر می‌گرداند.
  3. (accept(P,c:اگر c جوابی برای P باشد درست برمی گرداند.
  4. (first(P,c: سریع‌تر از روش جستجوی کامل است زیرا می‌تواند تعداد زیادی از زیر مسأله‌ها را با یک امتحان حذف کند.

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

پسگرد همه احتمالات را آزمایش می‌کند تا حالت درست را بیابد. این یک جستجوی عمق اول بین جواب‌های ممکن است. هنگام جستجو اگر راهی که طی می‌شود نتیجه نداد (به جواب نرسید) به نقطهٔ قبلی بازمی گردد و راه بعدی را امتحان می‌کند. اگر همه راه‌ها را امتحان کرد و به جواب نرسید، جستجو نا موفق بوده است. این الگوریتم معمولاً با توابع بازگشتی پیاده سازی می‌شود. به این صورت که در هر بار فراخوانی تابع، با اضافه شدن یک متغیر به طور متناوب همهٔ مقادیر ممکن را به آن نسبت می‌دهد و آن مقداری که با فراخوانی‌های بازگشتی بعدی سازگار است را ذخیره می‌کند. پسگرد مانند جستجوی عمق-اول است با این تفاوت که فضای کمتری اشغال می‌کند.

کاربردها[ویرایش]

یکی از استفاده‌های رایج از این الگوریتم، پیاده سازی عبارات باقاعده است. برای مثال الگوی سادهٔ "a*a" بدون استفاده از روش پسگرد با عبارت "aa" سازگار دیده نمی‌شود (چون a دوم با * از بین می‌رود و چیزی برای تطابق با a آخر وجود ندارد.) یکی دیگر از موارد استفاده از پسگرد، الگوریتم‌های مسیریاب است که با رفت و برگشت بر روی راس‌های یک گراف، کم هزینه‌ترین مسیر را پیدا می‌کند. همچنین استراتژی پسگرد در پیاده سازی زبان‌های برنامه نویسی و چیزهای دیگر مانند تجزیه متن‌ها کاربرد دارد.

توضیح روش[ویرایش]

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

شبه کد[ویرایش]

برای بکار بردن پیمایش وارونه برای دستهٔ خاصی از مسئله‌ها.P را برابر یک نمونه از مسئله که باید حل بشود در نظر می‌گیریم. و ۶ تابع که p را به صورت یک پارامتر می‌گیرنداولین فرزند c را بر می‌گرداند.

  1. (next(P,s:برادر بعدی s را بر می‌گرداند.
  2. (output(P,c:این تابع c را که جوابی برای P است چاپ می‌کند.

ابتدا ((bt(root(P را صدا می‌زنیم.

procedure bt(c)

   if reject(P,c) then return
   if accept(P,c) then output(P,c)
   sfirst(P,c)
   while s ≠ Λ do
     bt(s)
     snext(P,s)

تحلیل[ویرایش]

تابع reject باید boolean باشد و زمانی درست برگرداند که مطمئن باشد c به جواب نمی‌رسد. یک درست دادن اشتباه ممکن است باعث شود که bt به برخی از جواب‌ها نرسد. در عین حال کارایی پیمایش وارونه به درست برگرداندن reject برای زیر مسئله‌های نزدیک ریشه بستگی دارد. اگر همواره غلط برگرداند الگوریتم تبدیل به جست‌جوی کامل می‌شود. توابع first و next فرزندان زیرمسئله c را پیمایش می‌کند. اگر فرزند مورد نظر نبود این دو تابع باید null برگردانند.

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

  • Gilles Brassard, Paul Bratley. Fundamentals of Algorithmics. Prentice-Hall, 1995. 

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