مسئله پوشش بیشینه

**مسئله پوشش بیشینه** (به انگلیسی: maximum coverage problem)، یک سؤال کلاسیک در علوم رایانه و نظریه پیچیدگی محاسباتی است. این مسئله به طور گسترده در الگوریتم‌های تقریبی آموزش داده می‌شود.
برای ورودی تعدادی مجموعه و یک عدد k داده می‌شود. مجموعه‌ها می‌توانند عضو مشترک داشته باشند. شما باید به تعداد حداکثر k تا از این مجموعه‌ها را انتخاب کنید به طوری که حداکثر تعداد اعضا پوشش داده شود؛ برای مثال اجتماع مجموعه‌های انتخاب شده، بیشینه تعداد اعضا را دارد.
به عبارت دیگر، پوشش بیشینه (بدون وزن)
نمونه: عدد k و مجموعه‌ای از مجموعه‌ها  S = S_1, S_2, \ldots, S_m .
هدف: یافتن یک زیرمجموعهٔ  S^{'} \subseteq S ، به طوری که  \left| S^{'} \right| \leq k و تعداد اعضای پوشانده شده     \left| \bigcup_{S_i \in S^{'}}{S_i} \right|  حداکثر باشد.
مسئله پوشش بیشینه یک ان‌پی سخت (به انگلیسی: NP-hard) و نمی‌تواند تحت مفروضات استاندارد با  1 - \frac{1}{e} + o(1) \approx 0.632  تقریب زده شود. این نتیجه در اصل با نسبت تقریبی الگوریتم حریصانه عمومی که برای بیشینه‌سازی توابع زیرپیمان‌های با محدودیت کاردینالیتی (به انگلیسی: maximization of submodular functions with a cardinality constraint) به کار می‌رود، مطابقت دارد.

## صورتبندی به شکل برنامه خطی عدد صحیح
مسئله پوشش بیشینه می‌تواند به شکل زیر در قالب برنامه‌ریزی خطی عدد صحیح (به انگلیسی: Integer Linear Program) فرمول‌بندی شود.
:بیشینه‌سازی \sum_{e_j \in E} y_j. (بیشینه‌سازی مجموع اعضای پوشش داده شده).
:با توجه به اینکه  \sum{x_i}  \leq k ؛ (تعداد مجموعه‌های انتخاب شده بیشتر از نیست).
:: \sum_{\, e_j \in S_i} x_i \geq y_j ؛ (اگر y_j \geq 0  آنگاه حداقل یک مجموعهٔ e_j \in S_i انتخاب شده است).
::0 \leq y_j \leq 1؛ (اگرy_j=1 آنگاه  e_j  پوشش داده شده است)
::x_i \in \{0,1\}  (اگر x_i=1  آنگاه S_i  برای پوشش دادن انتخاب شده است).

## الگوریتم حریصانه
الگوریتم حریصانه برای پوشش بیشینه، مجموعه‌ها را بر اساس یک قاعده انتخاب می‌کند:
در هر مرحله، مجموعه‌ای را انتخاب کن که شامل بیشترین تعداد اعضای پوشش داده نشده باشد. می‌توان نشان داد که این الگوریتم به نسبت تقریب   1 - \frac{1}{e} می‌رسد. نتایج نشان می‌دهد که الگوریتم حریصانه، بهترین الگوریتم تقریب زمانی چند جمله‌ای ممکن برای پوشش بیشینه است.

## تعمیم‌های شناخته شده
نتایج غیرتقریبی به همهٔ تعمیم‌های مسئله پوشش بیشینه اعمال می‌شود زیرا آنها مسئله پوشش بیشینه را به عنوان یک حالت خاص دارند.

## حالت وزن دار
در مدل وزن دار هر عضو   e_j  وزنی برابر  w(e_j) دارد. هدف یافتن یک پوشش بیشینه است به طوری که بیشترین وزن را داشته باشد. حالت پایه، حالت خاصی است که همه وزن‌ها برابر 1  است.
:بیشینه‌سازی \sum_{e \in E} w(e_j) \cdot y_j . (بیشینه‌سازی مجموع وزندار اعضای پوشش داده شده).
:با توجه به اینکه \sum{x_i}  \leq k  ؛ (تعداد مجموعه‌های انتخاب شده بیشتر از  k نیست).
:: \sum_{e_j \in S_i} x_i \geq y_j  ؛ (اگر y_j \geq 0   آنگاه حداقل یک مجموعهٔ  e_j \in S_i  انتخاب شده است).
::0 \leq y_j \leq 1 ؛ (اگر  y_j=1 آنگاه e_j  پوشش داده شده است).
::x_i \in \{0,1\}  (اگر x_i=1  آنگاه S_i  برای پوشش دادن انتخاب شده است).
الگوریتم حریصانه برای پوشش بیشینه وزندار در هر مرحله مجموعه‌ای را انتخاب می‌کند که دارای بیشترین وزن اعضای پوشش داده نشده باشد. این الگوریتم به نسبت تقریب 1 - \frac{1}{e} می‌رسد.

## پوشش بیشینه بودجه‌ای
در حالت پوشش بیشینه بودجه‌ای (به انگلیسی: Budgeted maximum coverage)، نه تنها هر عضو  e_j   وزنی برابر w(e_j)  دارد، بلکه هر مجموعه S_i  قیمتی برابر c(S_i)  دارد. به جای k  که تعداد مجموعه‌ها در پوشش را محدود می‌کند، بودجهٔ B داده می‌شود. بودجهی B  وزن پوششی که می‌تواند انتخاب شود را محدود می‌کند.
:بیشینه کردن \sum_{e \in E} w(e_j) \cdot y_j  . (بیشینه کردن مجموع وزندار اعضای پوشش داده شده).
:با توجه به اینکه  \sum{c(S_i) \cdot x_i}  \leq B  ؛ (هزینه مجموعه‌های انتخاب شده از بیشتر نیست).
:: \sum_{e_j \in S_i} x_i \geq y_j  ؛ (اگر  y_j \geq 0  آنگاه حداقل یک مجموعهٔ  e_j \in S_i انتخاب شده است).
::0 \leq y_j \leq 1 ؛ (اگر  y_j=1 آنگاه e_j  پوشش داده شده است).
::x_i \in \{0,1\}   (اگر x_i=1  آنگاه S_i  برای پوشش دادن انتخاب شده است).
الگوریتم حریصانه دیگر راه حل‌هایی با تضمین کارایی ارائه نخواهد کرد. یعنی ممکن است رفتار این الگوریتم در بدترین حالت با راه حل بهینه بسیار متفاوت باشد. الگوریتم تقریب به روش زیر بدست می‌آید. ابتدا، پس از یافتن راه حلی که از الگوریتم حریصانه استفاده می‌کند، راه حل بهتر الگوریتم حریصانه و مجموعه با بیشترین وزن را بازمی‌گردانیم. این روش را، الگوریتم حریصانه اصلاح شده می‌نامیم. در مرحله دوم، با شروع از همهٔ خانواده‌های ممکن مجموعه‌های اندازه‌ها از یک تا (حداقل) سه، این راه حل‌ها را با الگوریتم حریصانه اصلاح شده تقویت می‌کنیم. در مرحله سوم، بهترین راه حل تقویت شده را بازمی‌گردانیم. این الگوریتم به نسبت تقریب 1- 1/e می‌رسد. این بهترین نسبت تقریب ممکن است مگر NP \subseteq DTIME(n^{O(\log\log n)}).

## پوشش بیشینه تعمیم یافته
در تعمیم یافتهٔ پوشش بیشینه هر مجموعهٔ S_i  قیمت  c(S_i) دارد، عضو  e_j   دارای وزنی متفاوت و هزینه‌ای بسته به مجموعه‌ای که آن را پوشش می‌دهد، دارد. یعنی اگر  e_j   توسط مجموعهٔ S_i  پوشش داده شده باشد، وزن   e_j  برابر w_i(e_j) و هزینهٔ آن برابر c_i(e_j)  خواهد بود. بودجه  B  برای هزینهٔ کل راه حل داده شده است.
:بیشینه کردن \sum_{e \in E, S_i} w_i(e_j) \cdot y_{ij}  . (بیشینه کردن مجموع وزندار اعضای پوشش داده شده در مجموعه‌هایی که پوشش داده شده‌اند).
:با توجه به اینکه  \sum{c_i(e_j) \cdot y_{ij}} + \sum{c(S_i) \cdot x_i}  \leq B  ؛ (هزینهٔ مجموعه‌های انتخاب شده نباید بیشتر از B  باشد).
:: \sum_{i} y_{ij} \leq 1  ؛ (عضو e_j=1  می‌تواند حداکثر با یک مجموعه پوشش داده شود).
:: \sum_{S_i} x_i \geq y_{ij}  ؛ (اگر y_j \geq 0   آنگاه حداقل یک مجموعهٔ  e_j \in S_i انتخاب شده است).
::y_{ij} \in \{0,1\}  ؛ (اگر y_{ij}=1  آنگاه e_j  توسط مجموعه‌ی**** S_i  پوشش داده شده است).
::x_i \in \{0,1\}  (اگر  x_i=1 آنگاه S_i برای پوشش دادن انتخاب شده است).

## الگوریتم پوشش بیشینه تعمیم یافته
این الگوریتم از مفهوم باقیماندهٔ وزن/هزینه استفاده می‌کند. باقیماندهٔ وزن/هزینه در مقابل یک راه حل آزمایشی اندازه‌گیری می‌شود و این تفاوت بین وزن/هزینه و وزن/هزینه بدست آمده با یک راه حل آزمایشی است.
این الگوریتم چندین مرحله دارد. اول، یافتن راه حلی که از الگوریتم حریصانه استفاده می‌کند. در هر تکرار الگوریتم حریصانه، راه حل آزمایشی مجموعه‌ای را که شامل بیشترین مقدار وزن اعضای باقیمانده تقسیم بر هزینهٔ این اعضا همراه با هزینه اعضای باقیمانده دارد، اضافه می‌کند. دوم، مقایسهٔ راه حل بدست آمده در قدم اول با راه حل بهینه که از تعداد کمی از مجموعه‌ها استفاده می‌کند. سوم، بازگرداندن بهترین راه حل از بین راه حل‌های بررسی شده. این الگوریتم به نسبت تقریب 1-1/e - o(1)  می‌رسد.

## مسائل مرتبط
* مسئله پوشش مجموعه مسئله‌ای برای پوشش همه عناصر با کمترین مجموعه‌های ممکن است.

## منابع

* 
* Uriel Feige, *A Threshold of ln <math>n</math> for Approximating Set Cover*, Journal of the ACM (JACM), v.45 n.4, p. 634 - 652, July 1998.

رده:خانواده مجموعه‌ها
رده:مسئله‌های ان‌پی کامل