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

مسئله ارضاپذیری بولی اولین مسئله ای است که اثبات شده در کلاس مسائل (NP-Complete (NPC قرار دارد.ورودی این مسئله، یک عبارت منطقی متشکل از متغیرهای بولی است که به آن فرمول گفته می شود و معمولا در فرمنرمال عطفی ارائه می شود. در این الگو، تعداد n متغیر بولی در تعداد m جمله، به صورت لیترال های مثبت یا نقیض آن،ظاهر می شوند. هر جمله حداقل دارای یک لیترال است. متغیرها می توانند در جمله های متعدد ظاهر شوند. هدف در اینمسئله آنست که متغیرها را طوری مقداردهی کنیم که ارزش کل فرمول برابر True شود. با توجه به فرم نرمال عطفیفرمول، برای اینکه ارزش کل فرمول برابر با درست شود، باید ارزش همه جمله ها برابر با درست شود و برای اینکه ارزشیک جمله، برابر با درست باشد، باید حداقل یکی از لیترالهای آن درست شود. به مقداردهی متغیرها، انتساب می گوییم.اگر چنین انتسابی یافت شود، فرمول ارضاشدنی و در غیر این صورت ارضانشدنی است. مسئله دیگری به نام مسئلهارضاپذیری بیشینه بولی وجود دارد که در واقع حالت کلی مسئله فوق است که در آن هدف، یافتن انتسابی است کهبیشترین تعداد ممکن از جمله ها (و نه همه جمله ها) را ارضا کند. این مسئله کاربردهای فراوانی دارد و بسیاری از مسائلدنیای مهندسی و علوم برای حل، ابتدا به مسئله ارضاپذیری بیشینه بولی، مدل شده و سپس با الگوریتم های حل این مسئله،حل می شوند. این مسئله در دسته مسائل NP-Hard و نیز در دسته مسائل بهینه سازی قرار دارد. لذا از جنبه های نظری وکاربردی، مورد توجه محققین بوده و الگوریتم های فراوانی برای حل آن، ارائه شده است. این الگوریتم ها به دو دستهکلی الگوریتم های دقیق و الگوریتم های غیردقیق دسته بندی می شوند. در این مقاله ضمن تشریح منطق و رویکرد هر دودسته، تکنیک های موفق مورد استفاده هر دو خانواده مورد بررسی قرار گرفته و پس از ارائه پیش زمینه های لازم،کاراترین الگوریتم های فعلی در دنیا ، به تفکیک هر خانواده تشریح شده است.

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