Question

dynamic_programming
spring_18_b

נתונים nn אינטרוולים, A={a1,,an}A = \{a_1, \ldots, a_n\}, ופונקציית משקל w:AR+w:A \to \mathbb{R}^+. נסמן ב-s(a)s(a) ו-e(a)e(a) את נקודת ההתחלה והסוף של האינטרוול aa בהתאמה (לכל אינטרוול, aa, מתקיים ש-s(a)<e(a)s(a) < e(a)).

אינטרוולים aa ו-bb חופפים אמ"מ אחד התנאים הבאים מתקיים:

  • s(a)s(b)e(a)s(a) \leq s(b) \leq e(a)
  • s(b)s(a)e(b)s(b) \leq s(a) \leq e(b)

תת קבוצה של אינטרוולים היא בלתי תלויה אם היא לא מכילה שני אינטרוולים חופפים.

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

נתונה תת קבוצה של אינטרוולים צהובים YAY \subseteq A. רוצים למצוא תת קבוצה בלתי תלויה שמכילה kk אינטרוולים צהובים לכל היותר במשקל מקסימלי.

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

tikz

ב. הציעו אלגוריתם שבהינתן קבוצת אינטרוולים, AA, פונקציית משקל, ww, תת קבוצה של אינטרוולים צהובים YAY \subseteq A, ופרמטר kk מוצא קבוצה בלתי תלויה של אינטרוולים שמכילה לכל היותר kk אינטרוולים צהובים במשקל מקסימלי.

1

Answers

א. קבוצת האינטרוולים הכחולים.

tikz

ב. נסתכל על האינטרוולים ממוינים על פי נקודת ההתחלה שלהם a1,,ana_1, \dots, a_n.

נסמן ב-nxt(i)=min{j:j>is(aj)>e(ai)}\text{nxt}(i) = \min\{j : j > i \land s(a_j) > e(a_i)\}, ונגדיר nxt(n)=n+1\text{nxt}(n) = n + 1.

נסמן ב-f(i,κ)f(i, \kappa) את המשקל המקסימלי של תת קבוצת אינטרוולים של ai,,ana_i, \dots, a_n שמכילה κ\kappa אינטרוולים צהובים לכל היותר. נשים לב שמתקיימת נוסחת הנסיגה הבאה:

f(i,κ)={max{f(i+1,κ),w(ai)+f(nxt(i),κ)}ai/Ymax{f(i+1,κ),w(ai)+f(nxt(i),κ1)}aiY f(i, \kappa) = \begin{cases} \max \{f(i + 1, \kappa), w(a_i) + f(\text{nxt}(i), \kappa)\} & a_i \notin Y \\ \max \{f(i + 1, \kappa), w(a_i) + f(\text{nxt}(i), \kappa - 1)\} & a_i \in Y \end{cases}

בנוסף מתקיים ש-f(n+1,κ)=0f(n + 1, \kappa) = 0, f(i,κ<0)=f(i, \kappa < 0) = -\infty.

אנחנו מעוניינים למצוא את f(1,k)f(1, k) וניתן לעשות זאת על ידי חישוב ערכי ff לכל i[n],κ[k]i \in [n], \kappa \in [k] בטבלה בגודל n×kn \times k (למשל בסדר יורד של השורות).

סיבוכיות: מיון האינטרוולים לוקח O(nlogn)O(n \log n) חישוב n(i)n(i) בודד ניתן לעשות ב-O(logn)O(\log n) ובסך הכל ב-O(nlogn)O(n \log n).

חישוב ערך אחד בטבלה ניתן לעשות ב-O(1)O(1) וחישוב הטבלה כולה ב-O(kn)O(kn).

סך הכל O(n(k+logn))O(n(k + \log n)).

1
Feedback