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

مسئله پوشش بیشینه (به انگلیسی: maximum coverage problem)، یک سؤال کلاسیک در علوم رایانه و نظریه پیچیدگی محاسباتی است. این مسئله به طور گسترده در الگوریتم‌های تقریبی آموزش داده می‌شود.
برای ورودی تعدادی مجموعه و یک عدد  داده می‌شود. مجموعه‌ها می‌توانند عضو مشترک داشته باشند. شما باید به تعداد حداکثر  تا از این مجموعه‌ها را انتخاب کنید به طوری که حداکثر تعداد اعضا پوشش داده شود؛ برای مثال اجتماع مجموعه‌های انتخاب شده، بیشینه تعداد اعضا را دارد.
به عبارت دیگر، پوشش بیشینه (بدون وزن)
نمونه: عدد  و مجموعه‌ای از مجموعه‌ها .
هدف: یافتن یک زیرمجموعهٔ  ، به طوری که  و تعداد اعضای پوشانده شده     حداکثر باشد.
مسئله پوشش بیشینه یک ان‌پی سخت (به انگلیسی: NP-hard) و نمی‌تواند تحت مفروضات استاندارد با    تقریب زده شود. این نتیجه در اصل با نسبت تقریبی الگوریتم حریصانه عمومی که برای بیشینه‌سازی توابع زیرپیمان‌های با محدودیت کاردینالیتی (به انگلیسی: maximization of submodular functions with a cardinality constraint) به کار می‌رود، مطابقت دارد.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

 صورتبندی به شکل برنامه خطی عدد صحیح 
مسئله پوشش بیشینه می‌تواند به شکل زیر در قالب برنامه‌ریزی خطی عدد صحیح (به انگلیسی: Integer Linear Program) فرمول‌بندی شود.
بیشینه‌سازی . (بیشینه‌سازی مجموع اعضای پوشش داده شده).
با توجه به اینکه ؛ (تعداد مجموعه‌های انتخاب شده بیشتر از نیست).
؛ (اگر  آنگاه حداقل یک مجموعهٔ  انتخاب شده است).
؛ (اگر آنگاه    پوشش داده شده است)
  (اگر   آنگاه   برای پوشش دادن انتخاب شده است).

 الگوریتم حریصانه 
الگوریتم حریصانه برای پوشش بیشینه، مجموعه‌ها را بر اساس یک قاعده انتخاب می‌کند:
در هر مرحله، مجموعه‌ای را انتخاب کن که شامل بیشترین تعداد اعضای پوشش داده نشده باشد. می‌توان نشان داد که این الگوریتم به نسبت تقریب    می‌رسد.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. نتایج نشان می‌دهد که الگوریتم حریصانه، بهترین الگوریتم تقریب زمانی چند جمله‌ای ممکن برای پوشش بیشینه است.Feige, U. , "A threshold of ln n for approximating set cover", J. ACM 45, 634-652.

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

 حالت وزن دار 
در مدل وزن دار هر عضو   وزنی برابر   دارد. هدف یافتن یک پوشش بیشینه است به طوری که بیشترین وزن را داشته باشد. حالت پایه، حالت خاصی است که همه وزن‌ها برابر   است.
بیشینه‌سازی . (بیشینه‌سازی مجموع وزندار اعضای پوشش داده شده).
با توجه به اینکه ؛ (تعداد مجموعه‌های انتخاب شده بیشتر از   نیست).
 ؛ (اگر   آنگاه حداقل یک مجموعهٔ    انتخاب شده است).
 ؛ (اگر   آنگاه   پوشش داده شده است).
  (اگر   آنگاه   برای پوشش دادن انتخاب شده است).
الگوریتم حریصانه برای پوشش بیشینه وزندار در هر مرحله مجموعه‌ای را انتخاب می‌کند که دارای بیشترین وزن اعضای پوشش داده نشده باشد. این الگوریتم به نسبت تقریب  می‌رسد.

 پوشش بیشینه بودجه‌ای 
در حالت پوشش بیشینه بودجه‌ای (به انگلیسی: Budgeted maximum coverage)، نه تنها هر عضو   وزنی برابر   دارد، بلکه هر مجموعه   قیمتی برابر   دارد. به جای   که تعداد مجموعه‌ها در پوشش را محدود می‌کند، بودجهٔ  داده می‌شود. بودجهی   وزن پوششی که می‌تواند انتخاب شود را محدود می‌کند.
بیشینه کردن  . (بیشینه کردن مجموع وزندار اعضای پوشش داده شده).
با توجه به اینکه  ؛ (هزینه مجموعه‌های انتخاب شده از بیشتر نیست).
 ؛ (اگر   آنگاه حداقل یک مجموعهٔ   انتخاب شده است).
 ؛ (اگر   آنگاه   پوشش داده شده است).
   (اگر   آنگاه   برای پوشش دادن انتخاب شده است).
الگوریتم حریصانه دیگر راه حل‌هایی با تضمین کارایی ارائه نخواهد کرد. یعنی ممکن است رفتار این الگوریتم در بدترین حالت با راه حل بهینه بسیار متفاوت باشد. الگوریتم تقریب به روش زیر بدست می‌آید. ابتدا، پس از یافتن راه حلی که از الگوریتم حریصانه استفاده می‌کند، راه حل بهتر الگوریتم حریصانه و مجموعه با بیشترین وزن را بازمی‌گردانیم. این روش را، الگوریتم حریصانه اصلاح شده می‌نامیم. در مرحله دوم، با شروع از همهٔ خانواده‌های ممکن مجموعه‌های اندازه‌ها از یک تا (حداقل) سه، این راه حل‌ها را با الگوریتم حریصانه اصلاح شده تقویت می‌کنیم. در مرحله سوم، بهترین راه حل تقویت شده را بازمی‌گردانیم. این الگوریتم به نسبت تقریب  می‌رسد. این بهترین نسبت تقریب ممکن است مگر .Khuller, S. , Moss, A. , and Naor, J. 1999. The budgeted maximum coverage problem. Inf. Process. Lett. 70, 1 (Apr. 1999), 39-45.

 پوشش بیشینه تعمیم یافته 
در تعمیم یافتهٔ پوشش بیشینه هر مجموعهٔ   قیمت   دارد، عضو   دارای وزنی متفاوت و هزینه‌ای بسته به مجموعه‌ای که آن را پوشش می‌دهد، دارد. یعنی اگر   توسط مجموعهٔ   پوشش داده شده باشد، وزن   برابر  و هزینهٔ آن برابر   خواهد بود. بودجه  برای هزینهٔ کل راه حل داده شده است.
بیشینه کردن  . (بیشینه کردن مجموع وزندار اعضای پوشش داده شده در مجموعه‌هایی که پوشش داده شده‌اند).
با توجه به اینکه  ؛ (هزینهٔ مجموعه‌های انتخاب شده نباید بیشتر از   باشد).
 ؛ (عضو   می‌تواند حداکثر با یک مجموعه پوشش داده شود).
 ؛ (اگر   آنگاه حداقل یک مجموعهٔ   انتخاب شده است).
 ؛ (اگر   آنگاه   توسط مجموعه‌ی''''   پوشش داده شده است).
  (اگر   آنگاه  برای پوشش دادن انتخاب شده است).

 الگوریتم پوشش بیشینه تعمیم یافته 
این الگوریتم از مفهوم باقیماندهٔ وزن/هزینه استفاده می‌کند. باقیماندهٔ وزن/هزینه در مقابل یک راه حل آزمایشی اندازه‌گیری می‌شود و این تفاوت بین وزن/هزینه و وزن/هزینه بدست آمده با یک راه حل آزمایشی است.
این الگوریتم چندین مرحله دارد. اول، یافتن راه حلی که از الگوریتم حریصانه استفاده می‌کند. در هر تکرار الگوریتم حریصانه، راه حل آزمایشی مجموعه‌ای را که شامل بیشترین مقدار وزن اعضای باقیمانده تقسیم بر هزینهٔ این اعضا همراه با هزینه اعضای باقیمانده دارد، اضافه می‌کند. دوم، مقایسهٔ راه حل بدست آمده در قدم اول با راه حل بهینه که از تعداد کمی از مجموعه‌ها استفاده می‌کند. سوم، بازگرداندن بهترین راه حل از بین راه حل‌های بررسی شده. این الگوریتم به نسبت تقریب   می‌رسد.Cohen, R. and Katzir, L. 2008. The Generalized Maximum Coverage Problem. Inf. Process. Lett. 108, 1 (Sep. 2008), 15-22.

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

 منابع 


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

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