الگوی پس‌گشت (Backtracking) الگویی است که بسیاری از افراد در درک آن مشکل دارند، اما در واقعیت، این الگو صرفاً گسترشی از جستجوی عمق اول (DFS) است.
در اینجا توضیحی عمیق درباره این الگو و نحوه تمایز آن از DFS استاندارد ارائه شده است:
۱. پس‌گشت به عنوان گسترش DFS
DFS (جستجوی عمق اول) و Backtracking هر دو بر اساس پیمایش عمیق در یک ساختار کار می‌کنند، اما در نحوه ایجاد ساختار تفاوت‌هایی وجود دارد:
- DFS استاندارد: در DFS، معمولاً ساختاری از پیش ساخته شده (مانند یک درخت یا گراف) را پیمایش می‌کنیم که گره‌ها و اتصالات آن‌ها از قبل تعریف شده‌اند.
- پس‌گشت: در الگوی پس‌گشت، شما اغلب مجبورید درخت راه‌حل (Solution Tree) را خودتان بسازید و آن را همزمان با کاوش ایجاد کنید. این امر به ویژه در مسائل ترکیبی (combinatorial problems) صادق است، جایی که ساختار درخت به طور صریح داده نشده است، بلکه به صورت پویا و با اتخاذ تصمیمات مختلف تولید می‌شود.
۲. مکانیسم عملکرد پس‌گشت
در یک مسئله پس‌گشت، شما با اتخاذ یک سری تصمیمات، تمام راه‌حل‌های ممکن را کاوش می‌کنید.
- درخت تصمیم: هر تصمیمی که گرفته می‌شود، یک گره در درخت راه‌حل را نشان می‌دهد و هر تصمیم بالقوه، یک شاخه را تشکیل می‌دهد.
- رسیدن به بن‌بست: با کاوش یک تصمیم، یا به یک راه‌حل معتبر دست می‌یابید، یا به یک بن‌بست (dead end) می‌رسید.
- بازگشت: هنگامی که یک تصمیم منجر به بن‌بست می‌شود، شما به تصمیم قبلی باز می‌گردید (backtrack)، آن را لغو می‌کنید و یک مسیر دیگر را امتحان می‌نمایید.
۳. مثال کاربردی: ترکیب حروف شماره تلفن
مسئله‌ای رایج در LeetCode که از پس‌گشت استفاده می‌کند، ترکیب حروف شماره تلفن (Letter Combinations of a Phone Number) است.
- هدف مسئله: به شما یک رشته از ارقام (معمولاً ۲ تا ۹) داده می‌شود و باید تمام ترکیب‌های ممکن حروفی را که این ارقام می‌توانند نشان دهند، با استفاده از نگاشت‌های صفحه کلید تلفن، برگردانید.
- مثال: اگر ارقام ورودی ۲۳ باشد، ۲ به ‘a’, ‘b’, ‘c’ و ۳ به ‘d’, ‘e’, ‘f’ نگاشت می‌شود. هدف تولید تمام ترکیب‌های ممکن مانند ad، ae، af، bd و غیره است.
نحوه حل با پس‌گشت:
- رویکرد بهینه: پس‌گشت رویکرد بهینه برای حل این مسئله است، زیرا به ما امکان می‌دهد تا هر حرف ممکن را یکی یکی کاوش کنیم، در حالی که پیکربندی‌های نامعتبر را به سرعت حذف نماییم (pruning invalid configurations).
- ساخت راه‌حل: پس‌گشت به ما اجازه می‌دهد تا راه‌حل را حرف به حرف بسازیم و مسیرهای ناقصی را که دیگر منطقی نیستند، دور بیندازیم.
- تابع کمکی بازگشتی (DFS): از یک تابع کمکی بازگشتی به نام
DFSاستفاده می‌شود. این تابع موقعیت فعلی در رشته ارقام را ردیابی کرده و ترکیب‌ها را گام به گام با افزودن حروف به یک لیست موقتی (path) می‌سازد. - شرط پایه: اگر
start indexبه طول ارقام برسد، مسیر فعلی یک ترکیب کامل است و به عنوان یک رشته به لیست نتایج (ANS) اضافه می‌شود. - کاوش و پس‌گشت: برای هر رقم، تابع روی حروف ممکن آن تکرار می‌شود، هر حرف به مسیر اضافه می‌شود و سپس به صورت بازگشتی
DFSرا برای رقم بعدی فراخوانی می‌کند. پس از کاوش یک حرف، با حذف آخرین حرف از لیستpathپس‌گشت انجام می‌شود تا امکان کاوش احتمالات بعدی فراهم شود.
پیچیدگی زمانی: پیچیدگی زمانی کلی این رویکرد $O(4^n)$ است، که در آن $n$ طول ارقام ورودی است، زیرا هر رقم می‌تواند حداکثر به چهار حرف نگاشت شود. این روش با کارایی تمام ترکیب‌های ممکن را کاوش می‌کند و تضمین می‌کند که پس‌گشت پس از تشکیل هر ترکیب انجام می‌شود تا مسیر بعدی کاوش گردد.
الگوی پس‌گشت مانند یک تیمی از کارآگاهان است که در حال بررسی تمام مسیرهای خروجی از یک خانه درختی هستند. هر تیم (تصمیم) تا جایی که می‌تواند در یک مسیر خاص پیش می‌رود. اگر مسیر به یک بن‌بست برسد (مثلاً به در بسته خورند)، تیم به خانه درختی اصلی برمی‌گردد و مسیر بعدی را انتخاب می‌کند، و این روند تا پیدا کردن تمام خروجی‌های ممکن ادامه می‌یابد.