Question

greedy

ישנן nn תמונות בתערוכה, המפוזרות לאורך מסדרון (חד ממדי). התמונות מפוזרות בנקודות x1<x2<<xnx_1 < x_2 < \dots < x_n.

אנו מעוניינים להציב שומרים בתערוכה. כל שומר מכסה רדיוס של 1 סביבו (כלומר אם הוא ניצב בנקודה yRy \in \mathbb{R}, אז הוא משגיח על התמונות בקטע [y1,y+1][y - 1, y + 1]). ניתן להציב שומרים רק בנקודות בהן תלויות תמונות.

הציעו אלגוריתם חמדן הרץ בזמן O(n)O(n) ומחשב את מספר השומרים המינימלי שיש להציב כך שלכל תמונה יהיה לפחות שומר אחד שמשגיח עליה.

1

Answers

אלגוריתם: נציב שומר בנקודה הכי ימנית שמכסה את x1x_1 ונפתור רקורסיבית על אוסף התמונות שלא מכוסות.

נכונות: נוכיח באינדוקציה כי לכל ii קיים פתרון אופטימלי שמזדהה עם הפתרון המוצע על ii הנקודות הראשונות.

בסיס: עבור i=0i = 0 הטענה מתקיימת.

צעד: נניח שהטענה מתקיימת עבור ii הנקודות הראשונות ונסתכל על הנקודה הבאה בפתרון האופטימלי. אם היא זהה לנקודה של האלגוריתם סיימנו, אחרת היא חייבת להיות משמאל לנקודה של האלגוריתם ולכן ניתן להזיז אותה ימינה לנקודה שבחר האלגוריתם ולקבל פתרון חוקי שמסכים על הנקודה ה-i+1i + 1.

0
Feedback