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