پوشش مجموعه

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

مسئله

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

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

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

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

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

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

الگوریتم تقریب حریصانه

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

$Greedy-Set-Cover$

$A\ \leftarrow \varnothing$

$while\ U\ \neq \varnothing$

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

$U\ \leftarrow U-S$

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

$retrunA$

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

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

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

منابع

• مشارکت‌کنندگان ویکی‌پدیا. «CLRS». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۲۶ دسامبر ۲۰۲۳.
• معرفی بر الگوریتم‌ها ترجمه: جعفرنژاد قمی
• Algorithmic construction of sets for k-restrictions author: Noga Alon
• A Threshold of ln $n$ for Approximating Set Cover author: Uriel Feige
• On the hardness of approximating minimization problems author: Carsten Lund