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

مسئله رنگ آمیزی گراف یک مسئله مشهور ان پی سخت است، که به یافتن تعداد کمینه k رنگبرای رنگ آمیزی رأس های یک گراف اشاره دارد، بطوریکه هر دو رأس متصل شده بوسیله یکیال رنگ های مختلفی داشته باشند. در این مقاله از اتوماتای یادگیر سلولی نامنظم و منطق فازیجهت یافتن عدد رنگی استفاده شده است. الگوریتم تقریبی پیشنهادی با الگوریتم های تقریبی بلام،کارگر، هالپرین و اتوماتای یادگیر سلولی مقایسه شده است . طبق آزمایش های انجام گرفتهالگوریتم پیشنهادی نتایج بهتری را در مقایسه با الگوریتم های فوق تولید می کند، بطوریکه عددرنگی گراف تولید شده با استفاده از این الگوریتم نسبت به دیگر الگوریتم ها کمتر است، که نشان ازکارآمدی روش پیشنهادی دارد.

کلیدواژه ها:

اتوماتای یادگیر سلولی ، رنگ آمیزی گراف ، منطق فازی ، سیستم استنتاج فازی