عنوان : ( یک حد بالا برای حداقل تعداد تطابقات درست در مسئله تطابق گراف با روشهای مبتنی بر جستجوی تصادفی )
نویسندگان: هاشم عزتی , محمود امین طوسی , سیدهاشم طبسی ,
Full Textچکیده
تطابق گراف از جمله معروفترین مسائل گراف و ترکیبیات میباشد که به لحاظ ماهیت سخت آن، تحقیقات متعددی را به خود معطوف نموده است. گرچه الگوریتمهای فراابتکاری عملکرد خوبی در بسیاری از مسائل NP-Hard و \\\\lr{NP-Complete} داشتهاند، اما برای این مسئله نتایج معتبری از حل آن توسط این الگوریتمها گزارش نشده است. تاکنون علت عدم کارایی این الگوریتمها در مواجهه با این مسئله موردبررسی قرار نگرفته است. در این مقاله نشان داده میشود یک روش مبتنی بر جستجوی تصادفی با احتمال بسیار زیادی به جواب بهینه نزدیک نیز نخواهد شد. به عنوان نمونه نشان داده شده است در یک گراف با $n$ رأس، احتمال آنکه به صورت تصادفی جایگشتی انتخاب شود و حداکثر سه تطابق درست حاصل شود، $0.02$ درصد خواهد بود.
کلمات کلیدی
, تطابق گراف, الگوریتمهای فراابتکاری, جایگشت
@inproceedings{paperid:1106453,
author = {هاشم عزتی and امین طوسی, محمود and طبسی, سیدهاشم},
title = {یک حد بالا برای حداقل تعداد تطابقات درست در مسئله تطابق گراف با روشهای مبتنی بر جستجوی تصادفی},
booktitle = {چهل و هشتمین کنفرانس ریاضی ایران},
year = {2017},
location = {همدان, ايران},
keywords = {تطابق گراف، الگوریتمهای فراابتکاری، جایگشت},
}
%0 Conference Proceedings
%T یک حد بالا برای حداقل تعداد تطابقات درست در مسئله تطابق گراف با روشهای مبتنی بر جستجوی تصادفی
%A هاشم عزتی
%A امین طوسی, محمود
%A طبسی, سیدهاشم
%J چهل و هشتمین کنفرانس ریاضی ایران
%D 2017
