ارائه روشی مبتنیبر جستجوی محلی جهت کاهش زمان اجرای الگوریتمهای دقیق حل مسئله Maximum Boolean Satisfiability

یکی ازمعروفترین مسائل محاسباتی درعلم کامپیوتر که اولین مسئله شناخته شده NP-Complete (NPC) نیز هست مسئله Satisfiability یابه اختصارSAT می باشد اهمیت این مسئله انقدر است که هرساله یک کنفرانس مخصوص این مسئله برگزار شده و تئوری و کاربردهای آن مورد بررسی قرارمیگیرد همچنین رقابت ها و ارزیابی ها درخصوص الگوریتم های حل آن و نیز دیگر مسائل مشتق شده ازآن صورت میپذیرد مسئله SAT دارای مشتقاتی است که درمهمترین مسئله Maximum satisfiability max-sat است که ورودی آن تعدادی جمله ازانوع CNF است وهدف مقداردهی متغیرها به گونه ای است که تعدادجمله های TRUE شده بیشینه گردد به عبارت دیگر مسئله Max-SAT یک نسخه بهینه سازی ازمسئله تصمیم گیری CNF-SAT و درنتیجه متعلق به کلاس NP-hardاست خیلی ازمسائل محاسباتی دشوار درحوزه های مختلف علوم و مهندسی شامل مهندسی کامپیوتر و علوم محاسباتی شیمی فیزیک و بیولوژی برای حل ابتدا به این مسئله Max-SAT تبدیل و سپس باالگوریتم های حل این مسئله حل میشوند لذا الگوریتمی بهبود یافته برای حل مساله Max-SAT میتواند موردعلاقه دراین حوزه ها باشد باتوجه به اینکه تکانون الگوریتمی ازمرتبه چندجمله ای برای حل این مسئله ارایه نشده است محققان متعددی درطول سالهای متمادی سعی کرده اند که الگوریتمی بهبود یافته برای حل این مسئله ارایه کنند که گرچه ازمرتبه نمایی باشد اما زمان اجرای کمتری نسبت به الگوریتم های موجوددیگر داشته باشد

کلیدواژه ها:

الگوریتم شاخه و حد ، NP-Hard ، ارضاپذیری بیشینه بولی ، جستجوی محلی ، هیوریستیک