بررسی کارآمدترین الگوریتم های حل مسئله ارضاپذیری بیشینه بولی
Publish Year: 1394
نوع سند: مقاله کنفرانسی
زبان: Persian
View: 674
This Paper With 16 Page And PDF Format Ready To Download
- Certificate
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
ITCC01_252
تاریخ نمایه سازی: 9 فروردین 1395
Abstract:
مسئله ارضاپذیری بولی اولین مسئله ای است که اثبات شده در کلاس مسائل (NP-Complete (NPC قرار دارد.ورودی این مسئله، یک عبارت منطقی متشکل از متغیرهای بولی است که به آن فرمول گفته می شود و معمولا در فرمنرمال عطفی ارائه می شود. در این الگو، تعداد n متغیر بولی در تعداد m جمله، به صورت لیترال های مثبت یا نقیض آن،ظاهر می شوند. هر جمله حداقل دارای یک لیترال است. متغیرها می توانند در جمله های متعدد ظاهر شوند. هدف در اینمسئله آنست که متغیرها را طوری مقداردهی کنیم که ارزش کل فرمول برابر True شود. با توجه به فرم نرمال عطفیفرمول، برای اینکه ارزش کل فرمول برابر با درست شود، باید ارزش همه جمله ها برابر با درست شود و برای اینکه ارزشیک جمله، برابر با درست باشد، باید حداقل یکی از لیترالهای آن درست شود. به مقداردهی متغیرها، انتساب می گوییم.اگر چنین انتسابی یافت شود، فرمول ارضاشدنی و در غیر این صورت ارضانشدنی است. مسئله دیگری به نام مسئلهارضاپذیری بیشینه بولی وجود دارد که در واقع حالت کلی مسئله فوق است که در آن هدف، یافتن انتسابی است کهبیشترین تعداد ممکن از جمله ها (و نه همه جمله ها) را ارضا کند. این مسئله کاربردهای فراوانی دارد و بسیاری از مسائلدنیای مهندسی و علوم برای حل، ابتدا به مسئله ارضاپذیری بیشینه بولی، مدل شده و سپس با الگوریتم های حل این مسئله،حل می شوند. این مسئله در دسته مسائل NP-Hard و نیز در دسته مسائل بهینه سازی قرار دارد. لذا از جنبه های نظری وکاربردی، مورد توجه محققین بوده و الگوریتم های فراوانی برای حل آن، ارائه شده است. این الگوریتم ها به دو دستهکلی الگوریتم های دقیق و الگوریتم های غیردقیق دسته بندی می شوند. در این مقاله ضمن تشریح منطق و رویکرد هر دودسته، تکنیک های موفق مورد استفاده هر دو خانواده مورد بررسی قرار گرفته و پس از ارائه پیش زمینه های لازم،کاراترین الگوریتم های فعلی در دنیا ، به تفکیک هر خانواده تشریح شده است.
Keywords:
Authors
سیدمحسن موسوی
بروجرد، دانشگاه آزاد اسلامی دانشکده تحصیلات تکمیلی، گروه مهندسی کامپیوتر
سیدرسول موسوی
تهران، دانشگاه صنعتی امیرکبیر، گروه مهندسی کامپیوتر
مراجع و منابع این Paper:
لیست زیر مراجع و منابع استفاده شده در این Paper را نمایش می دهد. این مراجع به صورت کاملا ماشینی و بر اساس هوش مصنوعی استخراج شده اند و لذا ممکن است دارای اشکالاتی باشند که به مرور زمان دقت استخراج این محتوا افزایش می یابد. مراجعی که مقالات مربوط به آنها در سیویلیکا نمایه شده و پیدا شده اند، به خود Paper لینک شده اند :