المپدیا

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

ابزار کاربر

ابزار سایت


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

افراز $k$-تایی

$n$ نقطه‌ی $p_n,…,p_2,p_1$ در فضای ۳ بعدی داده شده است. یک افراز $k$-تایی، تقسیم‌بندی این نقاط به $k$ دسته $A_k,…,A_2,A_1$ است، به طوری که هر نقطه دقیقا در یکی از $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$ بیش‌تر نیست.


ابزار صفحه