پوشاندن نقاط

[احسان]

به نظر من لازم نیست همش درباره ی الگوریتم های معروف حرف بزنیم! من یه سری سوال الگوریتمی می ذارم! (امیدوارم بقیه هم استقبال کنن و اگه سوال قشنگی دارن بذارن!)

n نقطه روی صفحه داریم که باید با دایره هایی به شعاع r پوشونده بشن. (هر نقطه که درون یا روی یک دایره قرار بگیره پوشونده شده!) احسان(!!) تونسته بفهمه که کمترین تعداد دایره ی لازم k هست. ولی چون الگوریتمی برای پوشوندن نقاط با k دایره سراغ نداره یه الگوریتم حریصانه اجرا می کنه! یعنی هربار یک دایره رو به گونه ای روی صفحه قرار می ده که بیش ترین تعداد نقطه (از بین نقاط پوشونده نشده) رو بپوشونه! ثابت کنید الگوریتم احسان حد اکثر k * [logn] + 1 دایره استفاده می کنه!

این سوال یه کمی سخته! خودم به مرور چند تا لم می ذارم که با اونا سوال راحت حل می شه! (در واقع این لم ها به عنوان راهنمایی توی متن سوال بوده!!) لطفاً هر کس روی سوال فکر کرد نتایجشو بگه!

 

[احسان]

پاسخ : پوشاندن نقاط

توضیح : الگوریتم حریصانه یا greedy : یک الگوریتم حریصانه در هر مرحله بهترین کاری را که می تونه انجام می ده و اصلاً به آینده فکر نمی کنه! مثلاً الگوریتمی که احسان برای پوشوندن نقاط استفاده می کنه یک الگوریتم حریصانه هست!!

الگوریتم های حریصانه معمولاً راحت به ذهن می رسند! ولی همیشه درست کار نمی کنند! درواقع همیشه جواب نهایی که از الگوریتم حریصانه به دست می آد، بهترین جواب نیست! مثلاً توی همین سوال پوشوندن نقاط!!

 

[احسان]

پاسخ : پوشاندن نقاط

n نقطه روی صفحه داریم که باید با دایره هایی به شعاع r پوشونده بشن. (هر نقطه که درون یا روی یک دایره قرار بگیره پوشونده شده!) احسان(!!) تونسته بفهمه که کمترین تعداد دایره ی لازم k هست. ولی چون الگوریتمی برای پوشوندن نقاط با k دایره سراغ نداره یه الگوریتم حریصانه اجرا می کنه! یعنی هربار یک دایره رو به گونه ای روی صفحه قرار می ده که بیش ترین تعداد نقطه (از بین نقاط پوشونده نشده) رو بپوشونه! ثابت کنید الگوریتم احسان حد اکثر k * [logn] + 1 دایره استفاده می کنه!

راهنمایی 1 : فرض کنید در الگوریتم احسان تعداد نقاطی که تا قبل از قرار دادن دایره ی i ام هنوز پوشونده نشدن برابر Ai باشه! ( مثلاً A1 = n ) ثابت کنید در مرحله ی i ام الگوریتم (قرار دادن دایره ی i ام) حداقل Ai / x نقطه ی پوشونده نشده، پوشیده می شن!

توجه کنید که احسان توی هر مرحله دایره ای قرار می ده که بیش ترین تعداد از نقاط پوشونده نشده رو بپوشونه! پس اگه Bi رو برابر تعداد نقاط جدیدی در نظر بگیریم که در مرحله ی i ام پوشونده می شن، دنباله ی Bi نزولی هست!

 

[احسان]

پاسخ : پوشاندن نقاط

n نقطه روی صفحه داریم که باید با دایره هایی به شعاع r پوشونده بشن. (هر نقطه که درون یا روی یک دایره قرار بگیره پوشونده شده!) احسان(!!) تونسته بفهمه که کمترین تعداد دایره ی لازم k هست. ولی چون الگوریتمی برای پوشوندن نقاط با k دایره سراغ نداره یه الگوریتم حریصانه اجرا می کنه! یعنی هربار یک دایره رو به گونه ای روی صفحه قرار می ده که بیش ترین تعداد نقطه (از بین نقاط پوشونده نشده) رو بپوشونه! ثابت کنید الگوریتم احسان حد اکثر k * [logn] + 1 دایره استفاده می کنه!

راهنمایی 2 : ثابت کنید اگه این الگوریتم حریصانه k مرحله اجرا بشه، حداقل n/2 نقطه ها پوشونده می شن!

ادامه ی اثبات هم که سخت نیست! (چه استقبالی شد از سوال!!)

 

[amiraliakbari@gmail.com]

پاسخ : پوشاندن نقاط

خیلی خیلی عالی بود

ندیده بودم هیچ جا این قدر پله به پله یک سوال خیلی خوب مطرح بشه