موضوع مقاله: روش پس‌گرد | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # روش پس‌گرد | مقدمه: این شیوه، تمام ترکیب‌های ممکن را بررسی می‌کند تا یک جواب پیدا کند یا تمام جواب‌های ممکن را شمارش کند. | ## بخش 1: روش پس‌گرد | تنها مزیت روش پسگرد در این است که می‌توان حالت‌هایی را بدون آنکه صریحاً بررسی شوند، با در نظر گرفتن ویژگی‌های مسئله، کنار گذاشت. در بسیاری از مسائل می‌توان بدون نیاز به بررسی تمام ترکیبات، از اینکه جواب مسئله توسط چه ترکیبی از مقادیر قابل تحقق نیست اطمینان بدست آورد و بدین ترتیب بخش‌های بزرگی از فضای جستجو را کنار گذاشت. اگر حل مسئله با انتساب مقادیر به n متغیر محقق شود، در بسیار مسائل با توجه به ویژگی‌های مسئله، می‌توان پیش از کامل شدن انتساب مقادیر، از اینکه انتساب جزئی برای رسیدن به جواب، «امیدبخش» نیست اطمینان بدست آورد و از این طریق از بررسی حالت‌هایی که از توسعه این انتساب به دست می‌آیند صرفنظر کرد. روش پس‌گرد شیوه‌ای در حل مسائل است که از علامت‌های خاصی برای بیان اینکه راه حل کاندیدی به حل مسئله می‌انجامد یا خیر استفاده می‌کند. این رویکرد برای حل مسائل درخت فضای آن مسئله را ایجاد کرده و تعیین می‌کند کدام گره امید بخش است. الگوریتم‌های عقب‌گردی از تابلوها یا علامت‌هایی برای بیان اینکه یک راه حل کاندید به حل مسئله نمی‌انجامد استفاده می‌کند. عقبگرد، حالت اصلاح شدهٔ جستجوی عمقی یک درخت می‌باشد.مقدمه‌ای بر طراحی الگوریتم‌ها، توماس کورمن مثال اول در روش پس‌گرد مسئله قفل رمزی می‌باشد. یک قفل رمزی شامل n کلید دیجیتالی است که هر کلید فقط دو حالت بسته(۱) یا حالت باز (۰) دارد. | ## بخش 2: روش پس‌گرد | می‌دانیم که n کلید دیجیتالی تعداد 2nحالت مختلف را پدیدمی‌آورند و این قفل تنها با یک حالت که همان رمز است باز می‌شود. هدف این مسئله چیدن n وزیر در یک صفحه شطرنج n*n است به گونه‌ای که هیچ دو وزیری یکدیگر را تهدید نکنند. در این مسئله می‌خواهیم تمام راه‌های ممکن جهت رنگ آمیزی گره‌های یک گراف بدون جهت را با استفاده از حداکثر m رنگ متفاوت پیدا کنیم، به گونه‌ای که هیچ دو رأس مجاوری هم رنگ نباشند. هدف پیدا کردن تمامی زیر مجموعه‌هایی از این اعداد صحیح می‌باشد که حاصل جمع آن‌ها بربر w است. پیاده‌سازی پسگرد همه حالت‌های ممکن را برای جواب بررسی می‌کند تا حالت درست را بیابد. هنگام جستجو اگر راهی که طی می‌شود نتیجه نداد (به جواب نرسید) به نقطهٔ قبلی بازمی‌گردد و راه بعدی را امتحان می‌کند. به این صورت که در هر بار فراخوانی تابع، با اضافه شدن یک متغیر به‌طور متناوب همهٔ مقادیر ممکن را به آن نسبت می‌دهد و آن مقداری که با فراخوانی‌های بازگشتی بعدی سازگار است را ذخیره می‌کند. کاربردها یکی از استفاده‌های رایج از این الگوریتم، پیاده‌سازی عبارات باقاعده است. | ## بخش 3: روش پس‌گرد | برای مثال الگوی سادهٔ "a*a" بدون استفاده از روش پسگرد با عبارت "aa" سازگار دیده نمی‌شود (چون a دوم با * از بین می‌رود و چیزی برای تطابق با a آخر وجود ندارد) یکی دیگر از موارد استفاده از پس‌گرد، الگوریتم‌های مسیریاب است که با رفت و برگشت بر روی راس‌های یک گراف، کم هزینه‌ترین مسیر را پیدا می‌کند. همچنین استراتژی پسگرد در پیاده‌سازی زبان‌های برنامه‌نویسی و چیزهای دیگر مانند تجزیه متن‌ها کاربرد دارد. توضیح روش الگوریتم پیمایش وارونه مجموعه‌ای از زیر مسئله‌ها را می‌شمارد که می‌توانند از طریق راه‌های مختلف کامل شوند و همهٔ راه حل‌های مسئله داده شده را بدهند. الگوریتم پیمایش وارونه این درخت را به صورت بازگشتی با شروع از ریشه به صورت جستجوی اول عمق جستجو می‌کند. در هر گره c این الگوریتم امتحان می‌کند که آیا c می‌تواند به صورت یک جواب معتبر کامل شود. شبه کد برای بکار بردن پیمایش وارونه برای دستهٔ خاصی از مسئله‌ها.P را برابر یک نمونه از مسئله که باید حل بشود در نظر می‌گیریم. | ## جمع‌بندی | در عین حال کارایی پیمایش وارونه به درست برگرداندن reject برای زیر مسئله‌های نزدیک ریشه بستگی دارد.