انشعاب و حد

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

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

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

اگر بخواهیم الگوریتمی ارائه دهیم که تابع $f$ را کمینه کند و تابع $g$ کران پایینی برای مقدار $f$ در راس‌های یک زیر درخت از فضای حالات باشد. ساختار کلی این روش به شکل زیر خواهد بود:

1. ابتدا یک جواب دلخواه $x$ پیدا می‌کنیم و مقدار $B$ را برابر با $f(x)$ قرار می‌دهیم ، از این پس مقدار $B$ نشان دهنده‌ی بهترین جواب یافته شده تا این نقطه جستجو خواهد بود.
2. یک صف از راس‌های فضای حالات در نظر گرفته و ریشه‌ی درخت فضای حالات را به آن اضافه می‌کنیم.
3. مراحل بعد را تا وقتی که صف خالی شود تکرار می‌کنیم.
   1. یک راس از داخل صف بیرون کشیده
   2. در صورتی که این راس نشان دهنده‌ی جوابی خاص از مسئله مثلا $x$ باشد و $f(x) < B$ ، این جواب بهترین جواب یافته شده تا کنون است در نتیجه مقدار $f(x)$ را درون $B$ قرار می‌دهیم.
   3. در غیر این صورت به ازای همه‌ی انشعابات این راس مثلا $N_i$
   4. اگر $g(N_i) < B$:
      1. این انشعاب ممکن است به جواب بهینه‌تری برسد پس $N_i$ را به لیست اضافه می‌کنیم.
      2. در غیر این صورت این انشعاب ارزشی نداشته چون کران پایین جواب‌های آن از کران بالای جواب مسئله بزرگ تر است.
   5. به دستور 3 بازگرد.

از این روش برای حل بعضی از مسائل NP-Hard استفاده می‌شود. رنگ آمیزی‌ گراف‌، Integer programming و مسئله‌ی فروشنده‌ی دوره گرد از جمله مسائلی هستند که با این روش حل می‌شوند.

ویکی پدیا