پس‌گردی و شاخه و حد

پس‌گردی (Backtracking) و شاخه و حد (Branch and Bound) الگوهای جستجوی سیستماتیک هستند که فضای راه‌حل‌های کاندید را به صورت یک درخت کاوش می‌کنند و زیردرخت‌هایی را که نمی‌توانند به یک راه‌حل معتبر یا بهینه منجر شوند، هرس می‌کنند تا جستجوهای نمایی را در عمل قابل مدیریت سازند.

Definition

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

Scope

این موضوع تکنیک‌های جستجوی جامع را که حول یک درخت جستجو سازماندهی شده‌اند، پوشش می‌دهد: پس‌گردی، که کاندیداهای جزئی را به محض نقض یک محدودیت کنار می‌گذارد، و شاخه و حد، که از حدود (bounds) بر روی بهترین هدف قابل دستیابی برای هرس زیردرخت‌ها در بهینه‌سازی استفاده می‌کند. این شامل مثال‌های ارضای محدودیت (مسئله N وزیر، رنگ‌آمیزی گراف، سودوکو) و مثال‌های بهینه‌سازی ترکیبیاتی (مسئله فروشنده دوره‌گرد، برنامه‌ریزی عدد صحیح) می‌شود و بحث می‌کند که چرا این روش‌ها با وجود هزینه نمایی در بدترین حالت، برای مسائل NP-hard ارزشمند باقی می‌مانند.

Core questions

• فضای راه‌حل یک مسئله چگونه به عنوان یک درخت جستجو از انتساب‌های جزئی مدل‌سازی می‌شود؟
• کدام بررسی‌های محدودیت به پس‌گردی اجازه می‌دهند تا شاخه‌های غیرممکن را زودتر هرس کند؟
• حدود پایین و بالا چگونه برای هرس شاخه‌ها در بهینه‌سازی محاسبه می‌شوند؟
• ترتیب شاخه‌بندی و محدود کردن چگونه بر عملکرد عملی تأثیر می‌گذارد؟
• چرا این روش‌ها با وجود بدترین حالت‌های نمایی، برای مسائل NP-hard استفاده می‌شوند؟

Key concepts

• درخت جستجو
• کاوش عمق اول
• انتشار محدودیت
• هرس
• توابع محدودکننده
• راه‌حل فعلی
• مسئله N وزیر
• آرام‌سازی برنامه‌ریزی عدد صحیح

Key theories

هرس درخت جستجو

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

توابع محدودکننده در شاخه و حد

شاخه و حد بهترین راه‌حل یافت شده تا کنون و یک حد (مانند آرام‌سازی برنامه‌ریزی خطی) بر روی بهترین مقدار قابل دستیابی در هر زیردرخت را حفظ می‌کند؛ یک زیردرخت زمانی کنار گذاشته می‌شود که حد آن نتواند راه‌حل فعلی را بهبود بخشد.

Clinical relevance

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

History

پس‌گردی به عنوان یک تکنیک عمومی در دهه‌های ۱۹۵۰ و ۱۹۶۰ سیستماتیک شد، به ویژه توسط گولومب و باومرت توصیف شد. شاخه و حد توسط آیلسا لند و آلیسون دویگ در سال ۱۹۶۰ برای برنامه‌ریزی خطی عدد صحیح معرفی شد و از آن زمان به بعد در بهینه‌سازی ترکیبیاتی محوری شده و حل‌کننده‌های مدرن برنامه‌ریزی عدد صحیح مختلط را تقویت می‌کند.

Key figures

• Ailsa Land
• Alison Doig
• Solomon Golomb
• Robert Bixby

Seminal works

• landdoig1960
• cormen2009

Frequently asked questions

تفاوت بین پس‌گردی و شاخه و حد چیست؟

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

اگر این روش‌ها در بدترین حالت نمایی هستند، چرا از آنها استفاده می‌شود؟

برای مسائل NP-hard هیچ الگوریتم دقیق چندجمله‌ای شناخته شده نیست، اما هرس مؤثر اغلب بخش عمده‌ای از درخت جستجو را در نمونه‌های واقعی حذف می‌کند، بنابراین حل‌کننده‌های شاخه و حد و پس‌گردی به طور منظم راه‌حل‌های بهینه اثبات‌شده را بسیار سریع‌تر از آنچه حدود بدترین حالت آنها نشان می‌دهد، پیدا می‌کنند.