به کارگیری الگوریتم جستجو کوانتومی کراورو الگوریتم کلاسیکی اسچونینگ در یافتن مجموعه چیرگی کراف

از انجلایی که مجموعه چیرگی در زمینه های گوناگون کاربرد دارد اهمیت ارائه راهکارهای بهینه را برای ان رابالا می برد. پیدا کردن مجموعه چیرگی در نظریه پیچیدگی محاسباتی در کلاس NP کامل قرار دارد و تاکنون روشی که در مرتبه زماین خطی و بهینه بتواند آن را حل کند ارائه نشده است. و اما روش هایی که تاکنون پیشنهاد شده اند توانسته اند در درجه نمایی شدن مسئله کاهش ایجاد کنند. در این مقاله نیز روشی برای حل این مسئله پیشنهاد شده است. دراین روش برای اولین بار از یک الگوریتم کوانتومی برای حل استفاده شده است. الگوریتم به کار رفته با نام الگوریتم جستجو گراور شناخته می شود که روشی برای جستجو در پایگاه داده های ساختار نیافته ارائه می دهد. متناسب با این نوع مسئله تغییراتی در ساختار این الگوریتم صورت گرفته است در کنار این تغییرات از ایده الگوریتم کلاسیکی اسچنینگ نیز در این روش جهت افزایش کارایی استفاده شده است. تمامی این موارد در کنار هم توانسته اند روش کارآمد تری در مقایسه با راهکارها کلاسیکی که تاکنون پیشنهاد شده ایجاد کنند. برای ارزیابی ادعای این روش بستری ایجاد شده است که بتوان در آن اجرای الگوریتم های کوانتومی را شبیه سازی و نتایج را تحلیل نمود که طی ارزیابی نمونه های مختلف توسط آن می توان کارایی این روش را مورد تایید قرار داد.

Keywords:

مجموعه چیرگی گراف , الگوریتم کوانتومی گراور , الگوریتم اسچونینگ , مسائل صدق پذیر , کامپویترهای کوانتومی