سیدمحسن موسوی - بروجرد، دانشگاه آزاد اسلامی دانشکده تحصیلات تکمیلی، گروه مهندسی کامپیوتر
سیدرسول موسوی - تهران، خیابان حافظ، دانشگاه صنعتی امیرکبیر، گروه مهندسی کامپیوتر
مجتبی ظاهری - تهران، خیابان حافظ، دانشگاه صنعتی امیرکبیر، گروه مهندسی کامپیوتر

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

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