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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

مسئله پوشش بیشینه (به انگلیسی: 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) می‌رسد. [۶]


مسائل مرتبط[ویرایش]

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

منابع[ویرایش]

  1. G. L. Nemhauser, L. A. Wolsey and M. L. Fisher. An analysis of approximations for maximizing submodular set functions I, Mathematical Programming 14 (1978), 265–294
  2. Hochbaum, D. S. (1997), "Approximating covering and packing problems: Set cover, vertex cover, independent set, and related problems", in Approximation algorithms for NP-hard problems, PWS Publishing Company, Boston, 94-143.
  3. Feige, U., "A threshold of ln n for approximating set cover", J. ACM 45, 634-652.
  4. Hochbaum, D. S. (1997), "Approximating covering and packing problems: Set cover, vertex cover, independent set, and related problems", in Approximation algorithms for NP-hard problems, PWS Publishing Company, Boston, 94-143.
  5. Khuller, S., Moss, A., and Naor, J. 1999. The budgeted maximum coverage problem. Inf. Process. Lett. 70, 1 (Apr. 1999), 39-45.
  6. Cohen, R. and Katzir, L. 2008. The Generalized Maximum Coverage Problem. Inf. Process. Lett. 108, 1 (Sep. 2008), 15-22.