الگوریتم حریصانه: تفاوت میان نسخهها
محتوای حذفشده محتوای افزودهشده
Haniyeh120 (بحث | مشارکتها) |
Haniyeh120 (بحث | مشارکتها) |
||
خط ۱۳۰:
==== '''[[رنگآمیزی گراف|مسئلهٔ رنگآمیزی رأسهای گراف:]]''' ====
[[پرونده:Petersen graph 3-coloring.svg|بندانگشتی|چپ|یک رنگآمیزی [[گراف پترسن]] به کمک ۳ رنگ (کمترین تعداد رنگ ممکن).]]
با تعداد m رنگ داده شده، [[رأس (نظریه گراف)|رأس]]<nowiki/>های [[گراف]] باید به گونهای رنگ شوند که هیچ دو رأس مجاوری دارای رنگ مشابه نباشند. هدف رنگ کردن رأسها به شیوهای است که هیچ دو رأس مجاوری دارای رنگ مشابه نباشند. هیچ الگوریتم کارآمدی برای رنگآمیزی گراف با حداقل رنگهای ممکن وجود ندارد و این مسئله از جمله مسائل «انپی کامل» [[انپی_سخت|(NP Complete)]] محسوب میشود. «الگوریتمهای تقریبی» [[الگوریتم_تقریبی|(Approximate Algorithms)]] گوناگونی برای حل این مسئله وجود دارند، که[[رنگ_آمیزی_آزمند| رنگآمیزی حریصانه]] از جمله آنهاست. رنگآمیزی حریصانه به این صورت است که رأس اول را با رنگ اول رنگ میکنیم و همه رأسهای بعدی را با اولین رنگی که در رأسهای مجاور آن وجود نداشت رنگ میکنیم. اگر چنین رنگی وجود نداشت، رنگ جدیدی اضافه میکنیم. <ref>{{پک| K Erciyes|2018|ک=Guide to Graph Algorithms: Sequential, Parallel and Distributed|ص=362}}</ref>
سطر ۱۶۲ ⟵ ۱۶۵:
</source>
====[[مسئله تولیدکننده-مصرفکننده|مسئلهٔ برنامهریزی چندین فعالیت همزمان]]: ====
|