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

سال انتشار: 1401
نوع سند: مقاله کنفرانسی
زبان: فارسی
مشاهده: 289

فایل این مقاله در 12 صفحه با فرمت PDF قابل دریافت می باشد

استخراج به نرم افزارهای پژوهشی:

لینک ثابت به این مقاله:

شناسه ملی سند علمی:

STCONF05_317

تاریخ نمایه سازی: 24 مهر 1401

چکیده مقاله:

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

نویسندگان

فاطمه سادات لاجوردی قمصری

کارشناسی مهندسی کامپیوتر دانشگاه کاشان

جواد سلیمی سرتختی

استادیار گروه مهندسی کامپیوتردانشگاه کاشان