حل مسئله کلیک بیشینه با استفاده از جستجوی محلی بهبود یافته همراه با جریمه

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

Keywords:

مسئله کلیک بیشینه , مسئله کلیک بیشینه وزندار , الگوریتم جستجوی محلی , هیوریستیک.