ارائه روشی مبتنیبر جستجوی محلی جهت کاهش زمان اجرای الگوریتمهای دقیق حل مسئله Maximum Boolean Satisfiability
- سال انتشار: 1394
- محل انتشار: کنفرانس بین المللی یافته های نوین پژوهشی درمهندسی برق و علوم کامپیوتر
- کد COI اختصاصی: COMCONF01_767
- زبان مقاله: فارسی
- تعداد مشاهده: 1626
نویسندگان
بروجرد، دانشگاه آزاد اسلامی دانشکده تحصیلات تکمیلی، گروه مهندسی کامپیوتر
تهران، خیابان حافظ، دانشگاه صنعتی امیرکبیر، گروه مهندسی کامپیوتر
تهران، خیابان حافظ، دانشگاه صنعتی امیرکبیر، گروه مهندسی کامپیوتر
چکیده
یکی ازمعروفترین مسائل محاسباتی درعلم کامپیوتر که اولین مسئله شناخته شده NP-Complete (NPC) نیز هست مسئله Satisfiability یابه اختصارSAT می باشد اهمیت این مسئله انقدر است که هرساله یک کنفرانس مخصوص این مسئله برگزار شده و تئوری و کاربردهای آن مورد بررسی قرارمیگیرد همچنین رقابت ها و ارزیابی ها درخصوص الگوریتم های حل آن و نیز دیگر مسائل مشتق شده ازآن صورت میپذیرد مسئله SAT دارای مشتقاتی است که درمهمترین مسئله Maximum satisfiability max-sat است که ورودی آن تعدادی جمله ازانوع CNF است وهدف مقداردهی متغیرها به گونه ای است که تعدادجمله های TRUE شده بیشینه گردد به عبارت دیگر مسئله Max-SAT یک نسخه بهینه سازی ازمسئله تصمیم گیری CNF-SAT و درنتیجه متعلق به کلاس NP-hardاست خیلی ازمسائل محاسباتی دشوار درحوزه های مختلف علوم و مهندسی شامل مهندسی کامپیوتر و علوم محاسباتی شیمی فیزیک و بیولوژی برای حل ابتدا به این مسئله Max-SAT تبدیل و سپس باالگوریتم های حل این مسئله حل میشوند لذا الگوریتمی بهبود یافته برای حل مساله Max-SAT میتواند موردعلاقه دراین حوزه ها باشد باتوجه به اینکه تکانون الگوریتمی ازمرتبه چندجمله ای برای حل این مسئله ارایه نشده است محققان متعددی درطول سالهای متمادی سعی کرده اند که الگوریتمی بهبود یافته برای حل این مسئله ارایه کنند که گرچه ازمرتبه نمایی باشد اما زمان اجرای کمتری نسبت به الگوریتم های موجوددیگر داشته باشدکلیدواژه ها
الگوریتم شاخه و حد ، NP-Hard ، ارضاپذیری بیشینه بولی ، جستجوی محلی ، هیوریستیکمقالات مرتبط جدید
- ارزیابی اقتصادی و زیست محیطی سناریوهای ترکیب انرژی تجدیدپذیر در برنامه ریزی تولید برق ایران تا افق ۱۴۱۰
- بررسی فناوریها و استراتژیها برای بهینه سازی مصرف انرژی و افزایش کارایی در شبکه های توزیع
- فناوری اطلاعات و ارتباطات سبز
- Hoo Controller Design for a Quadruple-Tank Multivariable System: Robust Performance via Weighted Sensitivity Shaping
- تاثیر حیاتی همبستگیهای آماری ضعیف بادبار بر قابلیت اطمینان سیستمهای قدرت: دیدگاهی فراتر از مدلهای سنتی
اطلاعات بیشتر در مورد COI
COI مخفف عبارت CIVILICA Object Identifier به معنی شناسه سیویلیکا برای اسناد است. COI کدی است که مطابق محل انتشار، به مقالات کنفرانسها و ژورنالهای داخل کشور به هنگام نمایه سازی بر روی پایگاه استنادی سیویلیکا اختصاص می یابد.
کد COI به مفهوم کد ملی اسناد نمایه شده در سیویلیکا است و کدی یکتا و ثابت است و به همین دلیل همواره قابلیت استناد و پیگیری دارد.