حل مساله رنگ آمیزی گراف با استفاده از آتوماتای یادگیر

رنگ آمیزی گراف یکی از مسائلNp-Completeبه شمار میرود .یکی از کاربردهای این مسئله رنگ آمیزی نقشه ها است .دراین مقاله یک الگوریتم جدید برای رنگ آمیزی گراف با استفاده از آتوماتای یادگیر پیشنهاد میشود .فرآیند یادگیری با تعدادی ازآتوماتاهای تصادفی شروع میشود .هر آتوماتا به تنهایی نمایش دهنده یک رنگ آمیزی تصادفی میباشد .با تکرار فرآیند یادگیری رنگ آمیزی بهبود می یابد. هدف مسئله پیدا کردن حداقل رنگ برای گراف راسی می باشد اما این مسئله جزء یکی از مسائلسمبلیک دنیای کامپیوتر می باشد و به دنبال راه حل هایی برای مسائل دارای محدودیت می باشد. از طرفی می توان به این مسئله از بعدی دیگر نگریست و آن این ست که یک گراف مانندGرا آیا می توان باKرنگ ، رنگ آمیزی کرد و در این مقاله به راه حل های پیشنهادی برای حل مساله رنگ امیزی با اتوماتا یادگیر می پردازیم

کلیدواژه ها:

آتوماتای یادگیر ، رنگ آمیزی گراف ، پاداش و جریمه ، مسائلNP