چکیده مقاله
مسئله کلیک بیشینه، یکی از مسائل بنیادی در نظریه گراف است که در کاربردهای مختلف مهندسی مورد استفاده قرار میگیرد و برای حل آن الگوریتمهای متعددی توسط محققین ارائه شده است مسئله کلیک وزندار بیشینه، تعمیمی بر مسئله کلیک بیشینه است، به طوریکه مقادیر صحیح و مثبتی ممکن است به رئوس/یالها اختصاص پیدا کند در این حالت، مسئله، پیدا کردن کلیکی با بیشترین مجموع وزن رئوس/یالها در گراف است هردو مسئله کلیک بیشینه و کلیک وزندار بیشینه جز مسائل NPسخت محسوب میشوند هدف از این مقاله، در ابتدا معرفی کارهای انجام شده برای مسئله کلیک بیشینه، سپس ارائه یک الگوریتم جستجوی محلی بهبود یافته برای پیدا کردن کلیک بیشینه است که از دانش ساختاری مسئله بهره برده و در آن از جریمه نیز برای هدایت الگوریتم استفاده شده است در نهایت، الگوریتم پیشنهادی براساس تعدادی از مسائل بنچ مارک مورد مقایسه و ارزیابی قرار گرفته است
کلیدواژه‌ها
نویسندگان
سپینود رضوانیان
کارشناسی ارشد مهندسی صنایع و بهینهسازی سیستمها، دانشگاه تربیت مدرس
علیرضا رضوانیان
استادیار گروه مهندسی کامپیوتر، دانشگاه علم و فرهنگ تهران
شیوه ارجاع
�ضوانیان، سپینود و رضوانیان، علیرضا،1399،حل مسئله کلیک بیشینه با استفاده از جستجوی محلی بهبود یافته همراه با جریمه،ششمین کنفرانس بین المللی مهندسی صنایع و سیستمها (ICISE ۲۰۲۰)،مشهد
ارائه‌شده در
مجموعه مقالات ششمین کنفرانس بین المللی مهندسی صنایع و سیستمها (ICISE ۲۰۲۰)19 شهریور 1399 · مشهد