پوشش مجموعه
تعریف
مسئله پوشش مجموعه، یک مسئله بهینهسازی است که بسیاری از مسئلههای انتخاب منابع را مدلسازی میکند. مسئله تصمیمگیری متناظر آن، مسئله NP کامل پوشش مجموعه را تعمیم میدهد و در نتیجه NP سخت است. الگوریتم تقریبی که برای اداره کردن مسئله پوشش راس ارائه شد، در این جا به کار نمیرود. و در نتیجه باید روش دیگری را به کار گیریم. روش اکتشافی حریصانهای را با نسبت تقریب لگاریتمی بررسی می کنیم. یعنی هر چه اندازه نمونه بزرگتر میشود، اندازه جواب تقریبی ممکن است نسبت به اندازه جواب بهینه رشد کند. چون، تابع لگاریتمی، خیلی کند رشد میکند، این الگوریتم تقریب ممکن است نتایج مفیدی ارائه ندهد.
مسئله
نمونهٔ
می گوییم زیرمجموعه
معادله ۱
می گوییم هر A که در معادله ۱ صدق میکند، X را می پوشاند. شکل ۱ مسئلهٔ پوشش مجموعه را شرح میدهد. اندازهA به صورت تعداد مجموعههای موجود در آن تعریف شد، نه تعداد عناصر موجود در این مجموعه ها. در شکل ۱، اندازه پوشش مجموعه می نیمم، ۳ است.
مسئله پوشش مجموعه، انتزاع بسیاری از مسئلههای ترکیبی است. به عنوان مثال ساده، فرض کنید X مجموعهای از مهارتهای مورد نیاز برای حل یک مسئله است و مجموعهای از افراد برای کار کردن بر بروی این مسئله وجود دارد. می خواهیم کمیتهای تشکیل دهیم که شامل کمترین تعداد ممکن از افراد باشد، بهطوریکه برای هر مهارت مورد نیاز در X، عضوی از کمیته دارای آن مهارت باشد. در نسخهٔ تصمیمگیری مسئلهٔ پوشش مجموعه، می پرسیم که آیا پوششی با اندازه K وجود دارد یا خیر؟ k پارامتر دیگری است که در نمونه مسئله مشخص شدهاست. نسخه تصمیمگیری این مسئله، NP کامل است.
الگوریتم تقریب حریصانه
روش حریصانه، در هر مرحله، مجموعهٔ S را انتخاب میکند که بزرگترین تعداد عناصر باقی ماندهای را که پوشش داده نشدند، پوشش میدهد:
در مثال شکل ۱، Greedy-Set-Cover، مجموعههای
این الگوریتم به صورت زیر کار میکند. مجموعه U در هر مرحله شامل مجموعهٔ عناصر باقی ماندهٔ پوشش نداده است. مجموعهٔ A شامل پوشش در حال ساخت است. خط ۴، مرحله تصمیمگیری حریصانه است. یک زیرمجموعه S انتخاب شد که بیشترین عناصر ممکن پوشش داده نشده را پوشش میدهد (بهطوریکه گرهها به دلخواه شکسته شدند). پس از انتخاب S، عناصر آن از U، و S در A قرار میگیرد. وقتی الگوریتم خاتمه می یابد، مجموعه A حاوی زیرخانوادهای از F است که X را می پوشاند.
الگوریتم Greedy-Set-Cover میتواند به آسانی پیادهسازی شود تا در زمان چندجملهای بر حسب
منابع
- معرفی بر الگوریتمها [۱]
- معرفی بر الگوریتمها ترجمه : جعفرنژادقمی
- Algorithmic construction of sets for k-restrictions author: Noga Alon
- A Threshold of ln for Approximating Set Cover author: Uriel Feige
- On the hardness of approximating minimization problems author: Carsten Lund