Question

dynamic_programming
spring_18_a

נתון קטע [s,e][s, e] ונתונים nn אינטרוולים A={a1,,an}A = \{a_1, \ldots, a_n\}. עבור אינטרוול aa נסמן ב-s(a)s(a) ו-e(a)e(a) את נקודת ההתחלה ונקודת הסיום שלו בהתאמה.

תת קבוצה של אינטרוולים, BAB \subseteq A,מכסה את הקטע [s,e][s,e] אם לכל נקודה p[s,e]p \in [s, e] קיים אינטרוול aBa \in B כך ש-s(a)pe(a)s(a) \leq p \leq e(a).

נתונה בנוסף פונקציית משקל אי-שליליתw:AR+w:A \to \mathbb{R}^+.

ברצוננו למצוא קבוצה קלה ביותר של אינטרוולים שמכסה את הישר (משקל הקבוצה הוא סכום משקלי האינטרוולים שבקבוצה).

הערות:

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

א. עבור הקלט הבא, מצאו קבוצה קלה ביותר של אינטרוולים שמכסה את הקטע [0,10][0, 10] (הקיפו בעיגול את האינטרוולים שבקבוצה).

tikz

ב. הוצע האלגוריתם החמדן הבא:

  • אתחל CC \leftarrow \emptyset.
  • כל עוד CC אינה מכסה את הקטע [s,e][s,e] בחר את האינטרוול הכי קל מ-ACA \setminus C הוסף אותו ל-CC והסר מ-AA את כל האינטרוולים שמכוסים על ידי CC.
  • החזר את CC.

הראו שהאלגוריתם הנ"ל אינו מחזיר בהכרח קבוצה קלה ביותר של אינטרוולים שמכסה את הישר.

tikz

ג. הציעו אלגוריתם שבהינתן קטע [s,e][s, e] וקבוצת אינטרוולים A={a1,,an}A = \{a_1, \ldots, a_n\}. מוצא קבוצה קלה ביותר של אינטרוולים שמכסה את הקטע. יש לנתח סיבוכיות, אין צורך להוכיח נכונות.

1

Answers

א.

tikz

ב. למשל עבור הקלט הבא:

tikz

האלגוריתם יבחר את כל האינטרוולים בעוד שניתן להסתפק בשניים.

ג. נסמן ב-α1,,αm\alpha_1, \dots, \alpha_m את כל נקודות ההתחלה והסיום של האינטרוולים ממוינות בסדר לא יורד. נסמן ב-f(αi)f(\alpha_i) את משקל הקבוצה הקלה ביותר שמכסה את הקטע [s,αi][s,\alpha_i] ונסמן ב-C(αi)C(\alpha_i) את קבוצת האינטרוולים שמכסים את הנקודה αi\alpha_i.

נשים לב שמתקיימת נוסחת הנסיגה הבאה:

f(αi)=minaC(αi)w(a)+f(s(a)) f(\alpha_i) = \min_{a \in C(\alpha_i)} w(a) + f(s(a))

כאשר f(s)=minaC(s)w(a)f(s) = \displaystyle{\min_{a \in C(s)} w(a)} והערך המבוקש הוא f(e)f(e).

את הערכים הנ"ל אפשר לחשב בעזרת תכנון דינאמי במערך בגודל 2n2n בסדר לא יורד של הנקודות.

סיבוכיות: אנחנו צריכים לחשב 2n2n ערכים, כאשר במקרה הגרוע עבור ערך בודד אנחנו צריכים לעבור על כל האינטרוולים ולכן, סך הסיבוכיות היא O(n2)O(n^2) כאשר מיון הנקודות נבלע בתוך הערך הנ"ל.

1
Feedback