برنامه برای مساله پوشش مجموعه

[root88]

با سلام
من باید یه برنامه برای مساله پوشش مجموعه یا set cover بنویسم الگوریتم حریصانه اش تو کتاب الگوریتم هست اما نمی دونم از کجا باید شروع کنم .اگه دوستان تو این زمینه اطلاعی دارن لطفا منو راهنمایی کن
1. به چه تعداد باید زیرمجموعه تولید کنم؟ 2 به توان n؟
2. تعداد عناصر زیرمجموعه رو باید تصادفی انتخاب کنم؟

[root88]

دوستان تا حالا کسی با این مسئله برخورد نکرده؟

[qwerty11]

سلام

تا جایی که میدونستم مسئله ی set cover یک مسئله ی NP-complete (http://en.wikipedia.org/wiki/NP-complete) هستش ! راه حل حریصانه هم تقریبی از جواب رو میده نه جواب بهینه رو.

پس اگر میخوای جواب بهینه رو بدست بیاری باید تمام زیر مجموعه های set ها رو بدست بیاری و اونی که کمترین تعداد set ها رو انتخاب میکنه جواب مسئله هستش.

راه حل حریصانه هم که تو هر مرحله اون set ای رو انتخاب میکنه که بیشترین تعداد cover نشده رو داشته باشه.

1. به چه تعداد باید زیرمجموعه تولید کنم؟ 2 به توان n؟2 به توان تعداد set ها.

2. تعداد عناصر زیرمجموعه رو باید تصادفی انتخاب کنم؟ تصادفی !؟ نه دیگه از یک شروع میکنی میری جلو. هر کجا زیرمجموعه ای جواب داد همون جواب مسئله هستش.

[root88]

ممنون اما اجازه بدید سوالمو یه جور دیگه بپرسم. مثلا من مجموعه مرجع 1و2و3و4 رو دارم و زیر مجموعه های S1,S2,S3,S4 که به ترتیب شامل عناصر 1و2، 2و3 ، 1و2و3 ، و 4 است. سوال من اینه که تعدا عناصر این مجموعه ها رو چطوری باید تعیین کنم مثلا یکی یه عنصر داره یکی سه تا؟

http://www.irupload.ir/images/xpgj7vt5wcwvonzf1cv.jpg