پوشش مجموعه

محتویات

۱ تعریف
۲ مسأله
۳ الگوریتم تقریب حریصانه
۴ منبع

تعریف [ویرایش]

مسأله پوشش مجموعه، یک مسأله بهینه سازی است که بسیاری از مسأله های انتخاب منابع را مدل سازی می کند. مسأله تصمیم گیری متناظر آن، مسأله 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 \}$

$retrun A$

در مثال شکل ۱، 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)$ اجرا می گردد. البته می توان نشان داد که الگوریتم حریصانه، پوشش مجموعه ای را برمی گرداند که چندان بزرگتر از پوشش مجموعه بهینه نیست.