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