المپدیا

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

ابزار کاربر

ابزار سایت


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

افراز k-تایی

$n$ نقطه‌ی $p_1$، $p_2$، …، $p_n$ در فضای ۳ بعدی داده شده است. یک افراز $k$-تایی، تقسیم‌بندی این نقاط به $k$ دسته $A_1$، $A_2$، …، $A_k$ است، به طوری که هر نقطه دقیقا در یکی از $A_i$ ها آمده باشد.

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

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

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

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


ابزار صفحه