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

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

ویرایش