الگوریتم‌های حریصانه: انتخاب فعالیت، اصول اصلی، و کدهای هافمن

چه چیزی یک الگوریتم را "حریصانه" می‌کند

یک Greedy Algorithm (الگوریتم حریصانه) یک راه‌حل را قطعه‌به‌قطعه می‌سازد، و همیشه گزینه‌ای که در لحظه فعلی بهترین به‌نظر می‌رسد را انتخاب می‌کند، بدون هرگز بازبینی آن انتخاب بعداً. این استراتژی بسیار ساده‌تر و معمولاً سریع‌تری نسبت به برنامه‌نویسی پویا، که پیش‌تر در این مجموعه بحث شد، است، که به‌طور سیستماتیک همه ترکیب‌های زیرمسئله را کاوش می‌کند. مشکل این است که انتخاب‌های حریصانه همیشه بهینه سراسری نیستند — اما برای یک دسته خاص از مسائل، به‌طور اثبات‌پذیر هستند، و تشخیص این دسته مهارت مرکزی است که این مقاله توسعه می‌دهد.

مسئله انتخاب فعالیت

با داشتن مجموعه‌ای از n فعالیت، هرکدام با یک زمان شروع sᵢ و زمان پایان fᵢ، هدف انتخاب حداکثر-اندازه زیرمجموعه از فعالیت‌های سازگار متقابل — فعالیت‌هایی که بازه‌های زمانی‌شان هم‌پوشانی ندارند — است که همگی می‌توانند با استفاده از یک منبع واحد، مانند یک سالن سخنرانی، زمان‌بندی شوند.

مثال فعالیت‌ها (مرتب‌شده بر اساس زمان پایان):
i:   1  2  3  4  5  6  7  8  9  10 11
sᵢ:  1  3  0  5  3  5  6  8  8  2  12
fᵢ:  4  5  6  7  8  9  10 11 12 13 14

رویکرد ساده برنامه‌نویسی پویا

این مسئله زیرساختار بهینه دارد، که پیش‌تر در این مجموعه بحث شد، و می‌تواند با برنامه‌نویسی پویا حل شود: تعریف S_{ij} به‌عنوان مجموعه فعالیت‌هایی که پس از پایان فعالیت i شروع می‌شوند و پیش از شروع فعالیت j پایان می‌یابند، و به‌طور بازگشتی هر فعالیت ممکن k در آن مجموعه را به‌عنوان یک شمول بالقوه در نظر بگیریم، مشابه از نظر روحی با رابطه‌های بازگشتی زنجیره ماتریس و BST بهینه که پیش‌تر در این مجموعه پوشش داده شد. این رویکرد کار می‌کند، اما با هزینه زمان Θ(n³) — کار بیشتر از نیاز، همان‌طور که بخش بعدی آشکار می‌کند.

بینش حریصانه: همیشه زودترین زمان پایان را انتخاب کن

بینش کلیدی‌ای که یک راه‌حل بسیار ساده‌تر و سریع‌تر را باز می‌کند این است: در میان همه فعالیت‌ها، آنی که زودترین پایان می‌یابد همیشه باید در برخی راه‌حل بهینه گنجانده شود. از نظر شهودی، انتخاب فعالیتی که زودترین پایان می‌یابد حداکثر زمان باقی‌مانده ممکن برای زمان‌بندی فعالیت‌های اضافی بعداً را باقی می‌گذارد.

GREEDY-ACTIVITY-SELECTOR(s, f, n):
  فعالیت‌ها را بر اساس زمان پایان f مرتب کن (صعودی)
  A = {فعالیت 1}       // اولین فعالیتی که پایان می‌یابد
  k = 1
  برای m = 2 تا n:
      اگر s[m] ≥ f[k]:    // این فعالیت پس از پایان آخرین انتخاب‌شده شروع می‌شود
          A = A ∪ {فعالیت m}
          k = m
  A را برگردان

به‌کارگیری این روی مثال بالا: مرتب‌سازی بر اساس زمان پایان (از قبل مرتب)، انتخاب فعالیت ۱ (پایان در ۴)، سپس اسکن به جلو برای فعالیت بعدی که زمان شروعش حداقل ۴ باشد — فعالیت ۴ (شروع در ۵، پایان در ۷) واجد شرایط است، سپس فعالیت ۸ (شروع در ۸، پایان در ۱۱)، سپس فعالیت ۱۱ (شروع در ۱۲، پایان در ۱۴). این یک انتخاب از ۴ فعالیت تولید می‌کند، که می‌تواند تأیید شود بهینه است.

از آنجا که فعالیت‌ها فقط یک‌بار نیاز به مرتب‌سازی دارند، که زمان Θ(n log n) می‌گیرد، به‌دنبال آن یک عبور خطی واحد از میان لیست مرتب‌شده، زمان اجرای کل Θ(n log n) است — بهبود چشمگیری نسبت به رویکرد برنامه‌نویسی پویای Θ(n³).

چرا انتخاب حریصانه در اینجا به‌طور اثبات‌پذیر درست است

درستی این استراتژی حریصانه بر اثبات دو ویژگی استوار است، که با هم توجیه می‌کنند جایگزینی کاوش کامل برنامه‌نویسی پویا با یک عبور حریصانه واحد را.

ویژگی انتخاب-حریصانه

یک مسئله Greedy-Choice Property (ویژگی انتخاب-حریصانه) نشان می‌دهد اگر یک راه‌حل بهینه سراسری همیشه بتواند با انجام یک انتخاب محلی-بهینه (حریصانه) اول، بدون نیاز به کاوش گزینه‌های دیگر در آن گام، به دست آید. برای انتخاب فعالیت، این با یک "استدلال تبادلی" اثبات می‌شود: با داشتن هر راه‌حل بهینه، اگر از قبل شامل فعالیتی با زودترین زمان پایان نباشد، آن فعالیت همیشه می‌تواند جایگزین هر فعالیتی که در حال حاضر اولین اسلات را اشغال می‌کند شود، بدون کاهش تعداد کل فعالیت‌های انتخاب‌شده، چون فعالیت زودترین-پایان‌یابنده حداقل به‌همان‌اندازه فضا برای انتخاب‌های بعدی باقی می‌گذارد.

زیرساختار بهینه (بازبینی‌شده)

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

با هم، این دو ویژگی یک ساختار الگوریتمی بسیار ساده‌تر از برنامه‌نویسی پویا را توجیه می‌کنند: به‌جای حل هر زیرمسئله و ترکیب نتایج، یک الگوریتم حریصانه یک انتخاب انجام می‌دهد، سپس به‌طور بازگشتی (یا تکراری) تنها زیرمسئله باقی‌مانده را حل می‌کند، بدون اینکه هرگز نیاز به بازبینی یا برگشت به انتخاب اولیه داشته باشد.

کدگذاری هافمن: یک الگوریتم حریصانه برای فشرده‌سازی بهینه

Huffman Coding (کدگذاری هافمن) مسئله کدگذاری یک مجموعه از کاراکترها به رشته‌های باینری را به‌گونه‌ای حل می‌کند که طول کلی کدگذاری‌شده یک سند، با فرکانس هر کاراکتر داده‌شده، کمینه شود. ایده کلیدی آن یک Variable-Length Prefix Code (کد پیشوند با طول متغیر) است: کاراکترهایی که مکرر‌تر ظاهر می‌شوند کدهای باینری کوتاه‌تری می‌گیرند، و هیچ کدی پیشوند دیگری نیست، که رمزگشایی بدون‌ابهام را بدون هیچ جداکننده‌ای بین کاراکترها امکان‌پذیر می‌کند.

مثال فرکانس کاراکترها:
a: 45   b: 13   c: 12   d: 16   e: 9   f: 5

یک کد با طول ثابت به 3 بیت به‌ازای هر کاراکتر نیاز دارد
(چون 6 کاراکتر وجود دارد)، برای مجموع:
45·3 + 13·3 + 12·3 + 16·3 + 9·3 + 5·3 = 300 بیت

یک کد هافمن بهینه تولید می‌کند:
a: 0        (1 بیت)
b: 101      (3 بیت)
c: 100      (3 بیت)
d: 111      (3 بیت)
e: 1101     (4 بیت)
f: 1100     (4 بیت)

مجموع: 45·1 + 13·3 + 12·3 + 16·3 + 9·4 + 5·4 = 224 بیت

این یک کاهش قابل‌توجه، تقریباً ۲۵٪ کوچک‌تر، را نشان می‌دهد، که صرفاً با اختصاص کدهای کوتاه‌تر به کاراکترهای مکرر‌تر به دست می‌آید.

ساخت درخت هافمن به‌طور حریصانه

الگوریتم یک کد پیشوند بهینه را با ترکیب مکرر دو آیتم باقی‌مانده کم‌فرکانس‌ترین در یک گره ترکیبی جدید می‌سازد، با استفاده از یک صف اولویت min، که پیش‌تر در این مجموعه درباره هیپ‌ها بحث شد، برای همیشه بازیابی کارآمد دو فرکانس کوچک‌ترین.

HUFFMAN(C, n):
  یک صف اولویت min به نام Q از کاراکترهای C بساز
  برای i = 1 تا n - 1:
      یک گره جدید z تخصیص بده
      z.left = x = EXTRACT-MIN(Q)
      z.right = y = EXTRACT-MIN(Q)
      z.freq = x.freq + y.freq
      INSERT(Q, z)
  EXTRACT-MIN(Q) را برگردان   // ریشه درخت هافمن

در هر گام، انتخاب حریصانه ادغام دو گره فعلاً کم‌فرکانس‌ترین است، چون این افزایش طول کلی کدگذاری‌شده ناشی از دادن یک بیت اضافی به هر دو آیتم ادغام‌شده در کد نهایی‌شان را کمینه می‌کند. این انتخاب حریصانه می‌تواند بهینه اثبات شود با استفاده از یک استدلال تبادلی مشابه از نظر ساختار با آنی که برای انتخاب فعالیت استفاده شد: هر درخت بهینه‌ای می‌تواند بازآرایی شود طوری‌که دو کاراکتر کم‌فرکانس‌ترین در عمیق‌ترین سطح خواهر-برادر باشند، بدون افزایش هزینه کلی.

با استفاده از یک min-heap برای صف اولویت، هرکدام از n-1 تکرار دو عملیات EXTRACT-MIN و یک INSERT انجام می‌دهد، هرکدام هزینه O(log n)، که زمان اجرای کل O(n log n) می‌دهد.

چرا الگوریتم‌های حریصانه وقتی اعمال می‌شوند ارزشمندند

هر دو مثال در این مقاله به زمان‌های اجرای به‌طور چشمگیری بهتر از آنچه یک رویکرد کامل برنامه‌نویسی پویا نیاز داشت دست می‌یابند — Θ(n log n) به‌جای Θ(n³) برای انتخاب فعالیت — دقیقاً چون ویژگی انتخاب-حریصانه نیاز به کاوش چند گزینه در هر نقطه تصمیم را حذف می‌کند. این مبادله مرکزی در طراحی الگوریتم است: الگوریتم‌های حریصانه ساده‌تر و سریع‌تر از برنامه‌نویسی پویا هستند هروقت ویژگی انتخاب-حریصانه بتواند اثبات شود، اما اعمال یک استراتژی حریصانه روی مسئله‌ای که این ویژگی را ندارد، بدون اثبات اینکه ابتدا برقرار است، می‌تواند بی‌سروصدا یک نتیجه نادرست و غیربهینه تولید کند. تکنیک اثبات استدلال-تبادلی نشان‌داده‌شده در این مقاله برای هم انتخاب فعالیت و هم کدگذاری هافمن، ابزار استاندارد برای ایجاد اینکه یک استراتژی حریصانه واقعاً درست است پیش از اعتماد به آن است.