***2
تفاوتها و شباهتهای دو روش بازگشت به عقب و انشعاب و تحدید
.Iروش پیمایش درخت (گراف)
اصولا دو روش جستجوی اصلی برای پیمایش گرافها در حالت کلی وجود دارد :
جستجو در پهنا با جستجوی ردیفی ( سطحی )(Breadth First Search)
جستجو در عمق یا جستجوی عمقی (Depth First Search)
الگوی جستجو برای روش بازگشت به عقب ( عقبگرد ) به صورت جستجو در عمق می باشد. اما در روش انشعاب و تحدید یکی از روشهای جستجوی درخت ، جستجو به ترتیب پهنا ( سطحی ) می باشد .
به روش جستجو به روش سطحی اصطلاحا جستجوی FIFO ( اولین ورودی - اولین خروجی ) نیز گویند . در این الگوریتم از یک صف استفاده می شود ، هر نودی که پیمایش می شود ، در صورت دارا بودن شرایط مورد نظر ، به انتهای صف افزوده می شود .
***5
تفاوتها و شباهتهای دو روش بازگشت به عقب و انشعاب و تحدید
.IIهرس کردن شاخه ها
در هر دوروش سعی می شود شاخه هایی از درخت هرس شود .در اینصورت تعداد حالات ایجاد شده کاهش یافته و در نتیجه زمان لازم برای اجرای الگوریتم کاهش می یابد .
گرچه این کار مرتبه زمانی را به حد قابل قبولی کاهش نمی دهد ، اما برای تعداد داده های کم زمان اجرا را به حد قابل قبولی کاهش می دهد .
در روش بازگشت به عقب امکان تغییر ترتیب بررسی گره ها پیش بینی نشده است ، اما در روش انشعاب و تحدید این امکان وجود دارد .
در برخی مسائل ، با انجام محاسبات اضافی می توان میزان امید برای رسیدن به جواب را در هر شاخه برآورد کرد .
مساله ای که به روش بازگشت به عقب حل می گردد می تواند بیش از یک جواب داشته باشد و هیچ جواب بر دیگری امتیازی ندارد. اما در اغلب مسائلی که به روش انشعاب و تحدید حل می شوند مهم یافتن جواب بهینه است .
همانندالگوریتم عقبگرد ، زمان الگوریتمهای انشعاب و تحدید نیز معمولا در بدترین حالت زمانی نمایی (یا بدتر) می باشد
***6
حل مسئله فروشنده دوره گرد با استفاده از روش انشعاب و تحدید
هدف : یافتن یک دور کامل به گونه ای که از یکی از گره ها پیمایش آغاز کرده و هر گره را تنها یک بار ملاقات کنیم و به گره اولیه بر گردیم .
فرض کنید می خواهیم مسیری روی گراف داده شده G پیدا کنیم که ماتریس وزن گراف G به صورت زیر باشد :
üچون مسیر باید کامل باشد، باید همه گره ها را در برگیرد ، پس میتوان هریک از گره ها را به عنوان نقطه شروع عملیات انتخاب کرد .