یک الگوریتم فراابتکاری جدید برای رنگ آمیزی گراف بر پایه الگوریتم نیروی گرانشی
Publish place: The first national conference on meta-heuristic algorithms and their applications in science and engineering
Publish Year: 1393
نوع سند: مقاله کنفرانسی
زبان: Persian
View: 1,027
This Paper With 10 Page And PDF Format Ready To Download
- Certificate
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
MHAA01_051
تاریخ نمایه سازی: 17 اسفند 1393
Abstract:
رنگ آمیزی گراف کاربردهای زیادی در زمینههای عملی و تئوری گوناگون دارد. علاوه بر مسالههای کلاسیک تعریف شده در این زمینه، با در نظر گرفتن محدودیتهای مختلفی روی انواع گرافها، روش رنگ آمیزی و حتی تعداد و رنگ عناصر گراف مسالههایمتنوعی با کاربردهای وسیع در صنعت و علوم تعریف و حل میشود. هدف از مساله رنگ آمیزی گراف این است که به هر کدام از گرههای گراف یک رنگ اختصاص یابد به طوری که هیچ دو گره مجاوری دارای رنگ یکسان نبوده و از حداقل تعداد رنگها برایرنگ آمیزی استفاده شود. رنگ آمیزی گراف با استفاده از کمترین تعداد رنگ ممکن به دلیل وجود حالات متعدد دارای فضای جستجوی بزرگ و در زمره مسائل NP کامل به شمار میرود و یافتن پاسخ بهینه آن با استفاده از روشهای قطعی بسیار مشکل ویا غیرممکن است. در این پایان نامه یک الگوریتم ابتکاری جدید برای حل مساله رنگ آمیزی گراف بر پایه الگوریتم جستجوی تقلید نیروی گرانشی ارائه شد تا در مقایسه با دیگر روشها کارائی بیشتری داشته باشد. هدف از این الگوریتم یافتن کمترین تعدادرنگ برای گرههای گراف مورد نظر در کمترین زمان ممکن است بطوری که هیچ دو گره مجاوری هم - رنگ نباشند. الگوریتم پیشنهادی بر روی نمونههای پیشنهاد شده در استاندارد DIMACS تست شده و نتایج تجربی نشان میدهد الگوریتم پیشنهادی از کارایی بالایی برای حل مساله زمانبندی کار در گرید محاسباتی برخوردار است
Keywords:
Authors
سارا ناظمی
دانشجوی کارشناسی ارشد، گروه کامپیوتر، دانشگاه آزاد اسلامی واحد علوم و تحقیقات آیت الله آملی، آمل
حمید جزایری
استادیار، گروه کامپیوتر، دانشگاه صنعتی نوشیروانی، بابل
مراجع و منابع این Paper:
لیست زیر مراجع و منابع استفاده شده در این Paper را نمایش می دهد. این مراجع به صورت کاملا ماشینی و بر اساس هوش مصنوعی استخراج شده اند و لذا ممکن است دارای اشکالاتی باشند که به مرور زمان دقت استخراج این محتوا افزایش می یابد. مراجعی که مقالات مربوط به آنها در سیویلیکا نمایه شده و پیدا شده اند، به خود Paper لینک شده اند :