المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


آموزش:الگوریتم:پس‌گرد

روش پس‌گرد

تعریف

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

ویژگی های روش

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

این روش مجموعه‌ی کاندید های ناتمام ، که در عمل قابلیت کامل شدن به جواب هایی از مسئله را دارند را پیمایش می‌کند. معملا این پیمایش به صورت کامل کردن جواب به ترتیب صعودی قسمت اضافه شده انجام می‌شود.

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

الگوریتم با شروع از ریشه درخت به ترتیب عمق اول درخت بالا را می پیماید. در هر مرحله $3$ عمل زیر را انجام می دهد:

1. درصورتی که کاندید $c$ قابلیت کامل شدن به جوابی از مسئله را نداشته باشد، از جستوجوی کل زیردرخت $c$ صرف نظر می‌شود( به عبارت دیگر شاخه‌ی $c$ را هرس می‌کند).

2. در صورتی که $c$ جوابی از مسئله باشد آن را گزارش می‌کند.

3. به صورت بازگشتی زیردرخت های $c$ را پیمایش می‌کند.

پیچیدگی‌ الگوریتم

الگوریتم های پس‌گرد معمولا پیچیدگی نمایی دارند .

کابردها

مثال: صورت مسئله اینجا می‌آید.

پاسخ

پاسخ مسئله اینجا می‌آید

مسائل نمونه

مراجع


ابزار صفحه