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

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

کلیدواژه ها:

رنگ آمیزی گراف ، الگوریتم جستجوی جاذبه گرانشی