حل تقریبی مساله دسته ماکزیمالMaximal Clique) با استفاده از آتاماتای یادگیرتوزیع شده

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

Keywords:

دسته ماکزیمال , آتاماتای یادگیر , آتاماتای یادگیر توزیع شده