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

روش اثبات به این صورت است که دنبالهٔ تصمیمات اتخاذ شده در هر مرحله را در نظر گرفته، دنباله‌ای بهینه پیدا می‌کنیم که با دنبالهٔ ساخته شده یکسان باشد (منظور از دنبالهٔ بهینه، دنباله‌ای از کار‌ها می‌باشد که جواب بهینه را به ما می‌دهد). برای پیدا کردن دنباله، ابتدا یک دنباله بهینه را درنظر می‌گیریم و در هر مرحله یک دنباله شبیه‌تر به دنباله خودمان پیدا می‌کنیم که بهینه باشد و سرانجام دنباله‌ای که پیدا کردیم با دنبالهٔ ما یکسان می‌شود.

 

 

درواقع شباهت دو دنباله، بزرگ‌ترین عددی مثل <math>\mathit{x}</math> است که <math>\mathit{x}</math> عضو اول ابتدای هر دو دنباله با هم یکسان باشد.[https://quera.ir/college/land/3016/%D8%A2%D9%85%D9%88%D8%B2%D8%B4-%D9%85%D8%B3%D8%A6%D9%84%D9%87-%D9%85%D8%AD%D9%88%D8%B1-%D8%AA%D9%81%DA%A9%D8%B1-%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85%DB%8C-%D9%BE%DB%8C%D8%B4%D8%B1%D9%81%D8%AA%D9%87-%D9%88-%D8%B3%D8%A7%D8%AE%D8%AA%D9%85%D8%A7%D9%86%E2%80%8C%D8%AF%D8%A7%D8%AF%D9%87%E2%80%8C%D9%87%D8%A7]

== کاربردها ==

 

 

[[پرونده:Knapsack.svg|بندانگشتی|250px|نمونه‌ای از مسئلهٔ کوله‌پشتی یک بعدی: چه جعبه‌هایی باید انتخاب شوند تا مقدار پول بیشینه شود اما وزن جعبه‌های مذکور بیشتر از ۱۵ کیلوگرم نشود؟ یک مسئله چند محدودیتی، می‌تواند هم وزن و هم حجم جعبه‌ها را در نظر بگیرد. مدل‌سازی اندازه و شکل جعبه‌ها، یک مسئله بسته‌بندی است.{{سخ}}(راه حل: اگر هر تعداد دلخواهی از جعبه‌ها در دسترس باشد، ۳ جعبهٔ زرد و ۳ جعبهٔ خاکستری پاسخ‌اند. اما اگر مانند شکل باشد یعنی از هر جعبه فقط یکی داشته باشیم، همه جعبه‌ها به جز جعبهٔ سبز را انتخاب می‌کنیم)]]

 

 

<u>مسئله</u>: خریداری از یک فروشگاه یک جنس 64 تومانی می‌خرد و 100 تومان به فروشنده می‌دهد و فروشنده باید 36 تومان به او برگرداند. اگر فروشنده سکه‌های 50 ,25 ,10 ,5 ,1 تومانی (از هر کدام حداقل یک نمونه) داشته باشد، چگونه می‌توان بقیه پول خریدار را برگرداند به نحوی که تعداد سکه‌ها (در کل) کمترین مقدار ممکن باشد؟

 

 

 

<u>مسئله (کولهٔ پشتی صفر و یک)</u>: مثالی از این مسئله مربوط به دزدی می‌شود که با کولهٔ پشتی وارد یک جواهر فروشی می‌شود. اگر وزن قطعات از یک حد بیشینه W فراتر رود، کولهٔ پشتی پاره خواهد شد. هر قطعه دارای ارزش و وزن معینی خواهد بود. مسئله‌ای که دزد با آن مواجه است، تعیین حداکثر ارزش قطعات است در حالی که وزن کل آن‌ها از حد معین W فراتر نرود. این مسئله را کولهٔ پشتی صفر و یک می‌گویند.

 

[[پرونده: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>

 

 

 

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

 

 

 

هر [[کسر]] مثبتی را می‌توان به صورت مجموع چند کسر واحد متفاوت نوشت. (کسر واحد به کسری گفته می‌شود که صورت آن یک و مخرجش یک عدد طبیعی است.)

 

 

 

 

 

[[پرونده:Huffman tree 2.svg|left|thumb|350px|درخت هافمن، ایجاد شده از تعداد تکرار حرف‌های جملهٔ «this is an example of a ‌Huffman tree». تعداد تکرارها و کد هر حرف، به همراه همان حرف در جدول زیر آمده‌است. رمز کردن این جمله به کمک این کد، به 135 بیت نیاز دارد.]]

 

کدگذاری هافمن یک الگوریتم [[مقایسه داده‌ها|مقایسهٔ داده]] است که از الگوریتم حریصانه برای پیاده‌سازی استفاده می‌کند و بر اساس تعداد تکرارهای یک [[نویسه (رایانه)|کاراکتر]] در یک [[پرونده (رایانه)|فایل]] است. این کدگذاری در فشرده‌سازی اطلاعات به کار می‌رود و با کدگذاری مجدد کاراکترهای موجود در اطلاعات بر اساس میزان استفاده‌ی آن‌ها، سعی در کم کردن حجم فایل می‌کند. بر اساس این روش، کاراکتری با استفاده‌ی بالا با کد کوتاهتر و کاراکتری با استفاده‌ی کم با کد طولانی‌تر جایگزین می‌شود. <ref>{{پک|Richard E. Neapolitan, Kumarss Naimipour|2004|ک=Foundations of Algorithms Using Java Pseudocode|ص=169}}</ref>

 

 

 

این الگوریتم در سال 1956 توسط [[ادسخر_دیکسترا|ادسخر دکسترا]] (Edsger Dijkstra) اثبات شد؛ که جزو الگوریتم‌های [[پیمایش گراف|جستجوی گراف]] است، و سؤالاتی چون [[مسئله یافتن کوتاه‌ترین مسیر|کوتاه‌ترین مسیر از یک رأس]] در [[گراف وزن‌دار|گراف‌های بدون وزن منفی]] را حل می‌کند. همچنین در [[مسیریابی (شبکه)|مسیریابی]] (routing) و به عنوان یک [[رویه (علوم رایانه)|زیرروال]] (subroutine) در الگوریتم‌های دیگر [[گراف (ریاضی)|گراف]] استفاده می‌شود. <ref>{{پک| Jesse Russell- Ronald Cohn|2012|ک=Dijkstra's Algorithm}}</ref><syntaxhighlight lang="python" line="1">

def dijkstra(Adj, w, s):