مقاله ﻣﺴﺄﻟﻪ رﻧﮓآﻣﯿﺰي ﮔﺮاف ﺑﺎ اﺳﺘﻔﺎده از اﺗﺎﻣﺎﺗﺎي ﯾﺎدﮔﯿﺮ ﺳﻠﻮﻟﯽ
مسئله رنگ آمیزی رئوس گراف یک مسئله بهینه سازی ترکیبی در تئوری گراف شناخته شده است. رنگ آمیزی اصلی رئوس گراف G=(V,E)، که در اینجا V(G) مجموعه رئوس و E(G) مجموعه یال است که شامل یال است، C f: V یک نگاشت از رئوس گراف G به مجموعه رنگ C={c1,c2,…,cp} که در آن f(u) f(v) برای همه ی یالهای (u,v)E. یک رنگ آمیزی مجاز رئوس گراف G، انتساب یک رنگ از p رنگ متمایز به هر یک از رئوس گراف بصورتی که که هیچ دو سر یالی دارای رنگ های مشابه نباشد.
به عبارت دیگر، مسئله رنگ آمیزی رئوس گراف میتواند به عنوان یک مسئله بهینه سازی یا به عنوان یک مسئله تصمیم گیری مطرح شود. نسخه بهینه مسئله رنگ آمیزی رئوس گراف برای پیدا کردن کمترین تعداد رنگ ها بصورتیکه گراف رنگ آمیزی شده مجاز باشد و هدف مسئله تصمیم گیری، در تصمیم گیری برای P با توجه به اینکه آیا گراف با P رنگ قابل رنگ آمیزی است یا نه، و مسئله P- coloring نامیده می شود.
رنگ آمیزی رئوس گراف که به عنوان یک مسئله NP-hard شناخته شده است (رجوع کنید به گری و جانسون [1] ) دارای کاربردهایی در زمینه های رشته های مهندسی، مسائل زمانبندی[2]، جدول زمانی[3]، تخصیص ثبات[4]، تخصیص فرکانس[5] و شبکه های ارتباطی[6]. یک نمودار g وقتی به صورت p رنگپذیر است که اجازه رنگ شدن را با اکثر رنگهای گروه p داشته باشد.
تعداد رنگهای X(G) حداقل تعداد رنگهای لازم برای رنگ آمیزی گراف است و گراف G پی کرومیک گفته می شود اگر X(G)=p. حداقل رنگ آمیزی G، رنگ آمیزی قانونی است که در آن کوچکترین تعداد رنگ (به عنوان مثال، تعداد رنگی) باید به رئوس اختصاص داده است.
در [14] اکبری ترکستانی و میبدی چهار الگوریتم تقریبی برای حل مسئله رنگ آمیزی گراف بر اساس آتاماتای یادگیری مطرح میکنند زمانی که عمل هر ماشین به روز رسانی می شود، بردار احتمال از طرح تقویت LR-1 استفاده می کند. در این مقاله، یک الگوریتم مبتنی بر آتاماتای یادگیری سلولی نامنظم برای حل این مشکل پیشنهاد می کنیم.
الگوریتم پیشنهادی با الگوریتم های کارامیا [11]، ﻓﺎﻧﺎﺑﯿﮑﯽ [12] و مالاگوتی [13] مقایسه شده است. نتایج این محاسبات نشان می دهد که الگوریتم پیشنهادی، نتایج بهتری از اندازه رنگ مجموعه بدست میدهد اما در زمان حال اجرا،الگوریتم های ذکر شده در بالا، عملکرد بهتری دارند.
بقیه این مقاله به شرح زیر است: در بخش 2، بررسی مختصری از آتاماتاهای یادگیر سلولی نامنظم داده شده است. در بخش 3 اﻟﮕﻮرﯾﺘﻢ ﭘﯿﺸﻨﻬﺎدي ﻣﺒﺘﻨﯽ ﺑﺮ اﺗﺎﻣﺎﺗﺎي ﯾﺎدﮔﯿﺮ ﺳﻠﻮﻟﯽ ﻧﺎﻣﻨﻈﻢ ﺷﺮح داده ﻣﯽﺷﻮد و عملکرد الگوریتم پیشنهادی از طریق آزمایش های شبیه سازی در بخش 4 بررسی قرار میگیرد. بخش 5 نتیجه گیری است.
نقد و بررسی‌ها
هیچ دیدگاهی برای این محصول نوشته نشده است.