پوشش مجموعه

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

نمونهٔ ${\displaystyle (X,F)}$ از مسئلهٔ پوشش مجموعه، شامل مجموعهٔ متناهی X و خانوادهٔ F از زیرمجموعه‌های X است . به‌طوری‌که هر عنصر X متعلق به حداقل یک زیرمجموعه در F است:( اگر ${\displaystyle S\ \in F}$ را برابر با p بگیریم)

${\displaystyle X\ =\ \bigcup _{p}S}$

می گوییم زیرمجموعه${\displaystyle S\in F}$، عناصرش را می پوشاند. مسئله، یافتن می نیمم اندازهٔ ${\displaystyle A\ \subseteq F}$است که اعضای آن، تمام X را می پوشاند: (اگر ${\displaystyle S\ \in A}$ را برابر با q بگیریم)

معادله ۱ ${\displaystyle X\ =\ \bigcup _{q}S}$

می گوییم هر A که در معادله ۱ صدق می‌کند، X را می پوشاند. شکل ۱ مسئلهٔ پوشش مجموعه را شرح می‌دهد. اندازهA به صورت تعداد مجموعه‌های موجود در آن تعریف شد، نه تعداد عناصر موجود در این مجموعه ها. در شکل ۱، اندازه پوشش مجموعه می نیمم، ۳ است.

مسئله پوشش مجموعه، انتزاع بسیاری از مسئله‌های ترکیبی است. به عنوان مثال ساده، فرض کنید X مجموعه‌ای از مهارت‌های مورد نیاز برای حل یک مسئله است و مجموعه‌ای از افراد برای کار کردن بر بروی این مسئله وجود دارد. می خواهیم کمیته‌ای تشکیل دهیم که شامل کمترین تعداد ممکن از افراد باشد، به‌طوری‌که برای هر مهارت مورد نیاز در X، عضوی از کمیته دارای آن مهارت باشد. در نسخهٔ تصمیم‌گیری مسئلهٔ پوشش مجموعه، می پرسیم که آیا پوششی با اندازه K وجود دارد یا خیر؟ k پارامتر دیگری است که در نمونه مسئله مشخص شده‌است. نسخه تصمیم‌گیری این مسئله، NP کامل است.

روش حریصانه، در هر مرحله، مجموعهٔ S را انتخاب می‌کند که بزرگ‌ترین تعداد عناصر باقی مانده‌ای را که پوشش داده نشدند، پوشش می‌دهد:

${\displaystyle Greedy-Set-Cover}$

${\displaystyle A\ \leftarrow \varnothing }$

${\displaystyle while\ U\ \neq \varnothing }$

${\displaystyle do\ Select\ an\ S\ \in F\ that\ maximizes\ \left|S\ \bigcap U\ \right\vert }$

${\displaystyle U\ \leftarrow U-S}$

${\displaystyle A\ \leftarrow A\ \bigcup \left\{S\right\}}$

${\displaystyle retrunA}$

در مثال شکل ۱، Greedy-Set-Cover، مجموعه‌های ${\displaystyle S_{1}}$ ، ${\displaystyle S_{4}}$ ، ${\displaystyle S_{5}}$ ، ${\displaystyle S_{3}}$ (را به همین ترتیب) به A اضافه می‌کند.

این الگوریتم به صورت زیر کار می‌کند. مجموعه U در هر مرحله شامل مجموعهٔ عناصر باقی ماندهٔ پوشش نداده است. مجموعهٔ A شامل پوشش در حال ساخت است. خط ۴، مرحله تصمیم‌گیری حریصانه است. یک زیرمجموعه S انتخاب شد که بیشترین عناصر ممکن پوشش داده نشده را پوشش می‌دهد (به‌طوری‌که گره‌ها به دلخواه شکسته شدند). پس از انتخاب S، عناصر آن از U، و S در A قرار می‌گیرد. وقتی الگوریتم خاتمه می یابد، مجموعه A حاوی زیرخانواده‌ای از F است که X را می پوشاند.

الگوریتم Greedy-Set-Cover می‌تواند به آسانی پیاده‌سازی شود تا در زمان چندجمله‌ای بر حسب ${\displaystyle t\ =\ \left|X\right\vert }$و ${\displaystyle w\ =\ \left|F\right\vert }$اجرا گردد. چون تعداد تکرارهای حلقه در خطوط ۳ تا ۶ از بالا توسط می نیمم ${\displaystyle m\ =\min(t,f)}$ محدود می‌شود، و بدنهٔ حلقه می‌تواند طوری پیاده‌سازی شود که در زمان${\displaystyle O(tw)}$اجرا گردد، پیاده‌سازی وجود دارد که در زمان${\displaystyle O(twm)}$ اجرا می گردد. البته می‌توان نشان داد که الگوریتم حریصانه، پوشش مجموعه‌ای را برمی گرداند که چندان بزرگتر از پوشش مجموعه بهینه نیست.

• معرفی بر الگوریتم‌ها
• معرفی بر الگوریتم‌ها ترجمه : جعفرنژادقمی
• Algorithmic construction of sets for k-restrictions author: Noga Alon
• A Threshold of ln ${\displaystyle n}$ for Approximating Set Cover author: Uriel Feige
• On the hardness of approximating minimization problems author: Carsten Lund