حل مسئله کلیک بیشینه با استفاده از جستجوی محلی بهبود یافته همراه با جریمه
سال انتشار: 1399
نوع سند: مقاله کنفرانسی
زبان: فارسی
مشاهده: 916
فایل این مقاله در 7 صفحه با فرمت PDF و WORD قابل دریافت می باشد
- صدور گواهی نمایه سازی
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
ICISE06_071
تاریخ نمایه سازی: 27 شهریور 1399
چکیده مقاله:
مسئله کلیک بیشینه، یکی از مسائل بنیادی در نظریه گراف است که در کاربردهای مختلف مهندسی مورد استفاده قرار میگیرد و برای حل آن الگوریتمهای متعددی توسط محققین ارائه شده است. مسئله کلیک وزندار بیشینه، تعمیمی بر مسئله کلیک بیشینه است، به طوریکه مقادیر صحیح و مثبتی ممکن است به رئوس/یالها اختصاص پیدا کند. در این حالت، مسئله، پیدا کردن کلیکی با بیشترین مجموع وزن رئوس/یالها در گراف است. هردو مسئله کلیک بیشینه و کلیک وزندار بیشینه جز مسائل -NPسخت محسوب میشوند. هدف از این مقاله، در ابتدا معرفی کارهای انجام شده برای مسئله کلیک بیشینه، سپس ارائه یک الگوریتم جستجوی محلی بهبود یافته برای پیدا کردن کلیک بیشینه است که از دانش ساختاری مسئله بهره برده و در آن از جریمه نیز برای هدایت الگوریتم استفاده شده است. در نهایت، الگوریتم پیشنهادی براساس تعدادی از مسائل بنچ مارک مورد مقایسه و ارزیابی قرار گرفته است.
کلیدواژه ها:
نویسندگان
سپینود رضوانیان
کارشناسی ارشد مهندسی صنایع و بهینهسازی سیستمها، دانشگاه تربیت مدرس
علیرضا رضوانیان
استادیار گروه مهندسی کامپیوتر، دانشگاه علم و فرهنگ تهران