انشعاب و حد

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

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

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

اگر بخواهیم الگوریتمی ارائه دهیم که تابع $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 و مسئله‌ی فروشنده‌ی دوره گرد از جمله مسائلی هستند که با این روش حل می شوند.

ویکی پدیا