Backtracking چیست؟

Backtracking: کاوش سیستماتیک همه راه‌حل‌ها با انتخاب، کاوش و برگشت — الگوی سه‌گامی و هرس شاخه‌ها

ایده اصلی

Backtracking (بازگشت به عقب) یعنی: همه گزینه‌ها را سیستماتیک امتحان کن؛ هر جا راه بن‌بست شد، به عقب برگرد و گزینه بعدی را امتحان کن. مثل حل ماز با دست: تا ته می‌روی، بن‌بست که شد برمی‌گردی و راه دیگر!

الگوی سه‌گامی

def backtrack(مسیر, انتخاب‌ها):
    if شرط_پایان:
        ثبت جواب
        return

    for انتخاب in انتخاب‌های_معتبر:
        ۱) انتخاب را اعمال کن (به مسیر اضافه)
        ۲) backtrack(مسیر جدید, انتخاب‌های جدید)
        ۳) انتخاب را برگردان (Undo)!

مرحله ۳ (Undo) قلب Backtracking است — بدون آن، مسیرها آلوده می‌شوند!

درخت تصمیم

Backtracking = پیمایش درخت تصمیم: هر سطح یک انتخاب، هر مسیر یک راه‌حل کاندید. برگشت = بالا رفتن از شاخه بن‌بست.

هرس (Pruning) — کلید کارایی

به‌جای کاوش کامل درخت، شاخه‌های بی‌آینده را زود حذف کن:

هرس خوب، زمان نمایی را در عمل قابل تحمل می‌کند.

مسائل کلاسیک

مسئلهانتخاب‌هاهرس
N-Queenستون هر ردیفتقاطع با قبلی‌ها
جایگشت‌هاکاراکتر استفاده‌نشده—
مجموع زیرمجموعه‌هاگرفتن/نگرفتنعبور از هدف
مسیر در ماز۴ جهتدیوار + بازدید‌شده
Sudokuارقام ۱-۹قواعد سطر/ستون/جعبه

پیچیدگی

بدون هرس معمولاً نمایی (O(2ⁿ) یا O(n!)) — طبیعت «همه حالت‌ها» همین است. هرس، ثابت‌ها را به‌شدت کم می‌کند؛ و برای مسائل خاص (مثل N-Queen با هرس خوب) تا n=۲۵-۳۰ عملی است.

نکته: اگر مسئله «همه راه‌حل‌ها» یا «هر راه‌حل معتبر» یا «بهترین از همه حالت‌ها» بخواهد و ساختار انتخاب-به-انتخاب داشته باشد ← Backtracking. اگر زیرمسئله‌های همپوشان دارد ← DP (گاهی هر دو رویکرد ممکن‌اند!).

جمع‌بندی

این مبحث بخشی از دوره آموزش کامل الگوریتم‌ها است.

ابزارهای مرتبط