الگوریتم شاخه و حد

الگوریتم شاخه و حد

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