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

این روش کاربردهای عمومی نیز دارد. به طور مثال زمانی که در مقابل خرید از یک فروشگاه یک اسکناس تحویل فروشنده داده می‌شود، وی با یک حساب سرانگشتی سعی می‌کند با حداقل اسکناس‌ها و سکه‌های ممکن باقیماندهٔ پول را تولید کرده و به خریدار تحویل دهد. این حساب سرانگشتی ممکن است روش حریصانه باشد.

 

 

== تاریخچه ==

==== '''[[رنگ‌آمیزی گراف|مسئلهٔ رنگ‌آمیزی رأس‌های گراف:]]''' ====

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

 

 

 

روش‌های [[الگوریتم پریم|پریم]] و [[الگوریتم کراسکال|کروسکال]] دو روش مشهور تولید درخت پوشای کمینه از یک [[گراف وزن‌دار]] هستند که از روش حریصانه بهره می‌برند. منظور از درخت پوشای کمینه، [[درخت پوشا]]<nowiki/>یی از گراف است که مجموع وزن یال‌های آن کمتر یا مساوی مجموع وزن یال‌های سایر درخت‌های پوشای آن گراف است.<ref>{{پک|ابراهیم علایی فرادنبه - محمدرضا علایی|۱۳۹۲|ک=طراحی الگوریتم ایران|ص=265}}</ref>