برای اطلاع از آخرین مقالات علمی و اخبار کرونا(COVID-19) کلیک کنید

مشخصات مقاله

عنوان: 

چند رنگ آميزي پهناي باند در گراف مبتني بر اتاماتاي يادگير سلولي

نوع ارائه: مقاله
نویسنده: انعامي عراقي عليرضا,اكبري تركستاني جواد,ميبدي محمدرضا
 
 
 
عنوان همایش: كنفرانس ملي سالانه انجمن كامپيوتر ايران
نوع همایش:  انجمن هاي علمي
حامی:  انجمن کامپیوتر ایران، دانشگاه صنعتی امیرکبیر
زمان:  1387دوره 14
 
 
چکیده: 

در اين مقاله، الگوريتمي مبتني بر اتاماتاي يادگير سلولي نامنظم براي حل مسايل رنگ آميزي پهناي باند گراف و چند رنگ آميزي پهناي باند گراف پيشنهاد مي گردد. در الگوريتم پيشنهادي ابتدا گراف ورودي تبديل به گراف پايه مي گردد و سپس به هر يك از رئوس گراف، يك سلول متناظر مي شود و همچنين به هر سلول، يك اتاماتاي يادگير اختصاص مي يابد. هر يك از اتاماتاي يادگير، يك عمل از مجموعه اعمال خود را با توجه به بردار احتمال مربوطه انتخاب مي كند. اگر قدر مطلق تفاضل عمل انتخابي يك سلول نسبت به تمامي همسايگانش بزرگتر يا مساوي وزن يال مرتبط بين آن دو باشد، در اين صورت به عمل انتخابي اين سلول پاداش داده مي شود و در غير اين صورت سلول جريمه مي شود. الگوريتم تا زماني ادامه مي يابد كه تمام سلول ها پاداش بگيرند. الگوريتم پيشنهادي، با الگوريتم موجود همچون ليم، پرستويچ و مالاگوتي مقايسه شده و طبق نتايج بدست آمده بر روي گراف هاي نمونه نشان داده مي شود كه الگوريتم پيشنهادي نتايج به مراتب بهتري را توليد مي كند.

 
کلید واژه: مساله چند رنگ آميري گراف، مساله رنگ آميزي پهناي باند گراف، اتاماتاي يادگير سلولي
 
مقالات نشریه ای مرتبط: 
 
مقالات همایشی مرتبط: 
 
 
بازدید یکساله 80   pdf-file
 
آخرین های بلاگ
ورود به بلاگ مرکز اطلاعات علمی