Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۳:الگوریتم ها:سوال ۴

افراز k-تایی

n نقطه‌ی pn,,p2,p1 در فضای ۳ بعدی داده شده است. یک افراز k-تایی، تقسیم‌بندی این نقاط به k دسته Ak,,A2,A1 است، به طوری که هر نقطه دقیقا در یکی از Aiها آمده باشد.

قطر یک دسته برابر بیش‌ترین فاصله‌ی دو نقطه در آن دسته می‌باشد. اندازه‌ی یک افراز نیز برابر بیشینه‌ی قطر دسته‌هایش تعریف می‌شود. OPT مقدار کمینه‌ی اندازه‌ی یک افراز است.

الگوریتم زیر را در نظر بگیرید:

  1. S={{p1},{p2},.,{pk}} و i=k
  2. i=i+1
  3. S=S{{pi}}
  4. از هر یک از k+1 مجموعه‌ی درون مجموعه‌ی درون S یک نقطه به عنوان نماینده انتخاب کن و دو نماینده‌ای که فاصله‌شان از فاصله‌ی هر دو نماینده‌ای کم‌تر مساوی است را در نظر بگیر. مجموعه‌های مربوط به این دو نماینده را با هم ادغام کن.( پس اکنون k مجموعه درون S وجود دارد.)
  5. اگر i<n بود به ۲ برو وگرنه تمام.

در پایان الگوریتم k مجموعه از نقاط خواهیم داشت که در واقع یک افراز k-تایی است. ثابت کنید اندازه‌ی این افراز از (2k1)×OPT بیش‌تر نیست.


ابزار صفحه