الگوریتم حریصانه: تفاوت میان نسخه‌ها

 

با تعداد m رنگ داده شده، [[رأس (نظریه گراف)|رأس‌]]<nowiki/>های [[گراف]] باید به گونه‌ای رنگ شوند که هیچ دو رأس مجاوری دارای رنگ مشابه نباشند. هدف رنگ کردن رأس‌ها به شیوه‌ای است که هیچ دو رأس مجاوری دارای رنگ مشابه نباشند. هیچ الگوریتم کارآمدی برای رنگ‌آمیزی گراف با حداقل رنگ‌های ممکن وجود ندارد و این مسئله از جمله مسائل «ان‌پی کامل» [[ان‌پی_سخت|(NP Complete)]] محسوب می‌شود. «الگوریتم‌های تقریبی» [[الگوریتم_تقریبی|(Approximate Algorithms)]] گوناگونی برای حل این مسئله وجود دارند، که[[رنگ_آمیزی_آزمند| رنگ‌آمیزی حریصانه]] از جمله آنهاست. رنگ‌آمیزی حریصانه به این صورت است که رأس اول را با رنگ اول رنگ می‌کنیم و همه رأس‌های بعدی را با اولین رنگی که در رأس‌های مجاور آن وجود نداشت رنگ می‌کنیم. اگر چنین رنگی وجود نداشت، رنگ جدیدی اضافه می‌کنیم. <ref>{{پک| K Erciyes|2018|ک=Guide to Graph Algorithms: Sequential, Parallel and Distributed|ص=362}}</ref>

 

<source lang="cpp">

</source>

 

مسئلهٔ برنامه‌ریزی چندین فعالیت که همزمان انجام می‌پذیرند نیاز به استفادهٔ همزمان از یک منبع مشترک با هدف انتخاب مجموعه‌ای با ماکزیمم اندازه از فعالیت‌هایی که با هم [[:en:Overlap|هم‌پوشانی]] ندارند، دارند.