Question

dynamic_programming

יהא G=(V,E)G = (V,E) גרף מכוון ללא מעגלים עם משקלות על הקשתות.

  1. הציעו אלגוריתם אשר בהינתן צומת ss, מוצא את משקל מסלול קל ביותר מ-ss לשאר צמתי הגרף. על האלגוריתם לרוץ בסיבוכיות זמן של O(V+E)O(|V| + |E|).
  2. הציעו אלגוריתם אשר בהינתן זוג צמתים s,ts,t בגרף, מוצא את משקל מסלול קל ביותר מ-ss ל-tt המכיל לפחות 3 קשתות, או קובע שלא קיים כזה. סיבוכיות הזמן הנדרשת היא O(V+E)O(|V| + |E|).
  3. נתונים nn מספרים ממשיים a1,ana_1, \ldots a_n. ברצוננו למצוא 1i<jn1 \leq i < j \leq n כך ש-k=ijak\sum_{k = i}^j a_k הוא מינימלי. הציעו פתרון לבעיה המבוסס על רדוקציה לסעיף 2.
1

Answers

1. נסמן ב-d(v)d(v) את המרחק של הצומת vv מ-ss ונשים לב שמתקיים

d(v)=minuvEd(u)+w(uv) d(v) = \min_{uv \in E} d(u) + w(uv)

כדי לחשב את הנוסחה בזמן לינארי עבור כל צומת נבצע מיון טופולוגי של הגרף ונחשב את הערכים לפי סדר המיון הטופולוגי כאשר מאתחלים את d(s)0d(s) \leftarrow 0 ו-d(v)d(v) \leftarrow \infty לכל v̸=sv \neq s.

2. כדי לוודא שבמסלול יש לפחות 3 קשתות "נשכפל" את הגרף 4 פעמים, פורמלית:

G=({v1,v2,v3,v:vV},{u1v2,u2v3,u3v,uv:uvE})G' = (\{v_1, v_2, v_3, v : v \in V\}, \{u_1v_2, u_2v_3, u_3v, uv : uv \in E\})

אפשר להשתכנע שמסלול ב-GG מ-s1s_1 ל-tt הוא מסלול עם שלוש קשתות לפחות מ-ss ל-tt ב-GG.

ניתן להשתמש באלגוריתם של סעיף א' כדי לחשב/לקבוע שלא קיים משקל מסלול קל ביותר ב-GG'.

3. נבנה את הגרף הבא:

נשים לב (ללא צורך בסעיף 2) שמשקל של כל מסלול מ-ss ל-tt בגרף שתיארנו בציור הוא ערך הסדרה המתאימה וההפך (הסדרה המתאימה היא המספרים שמתאימים לצמתים הפנימיים במסלול) ולכן זאת אכן רדוקציה. גודל הגרף לינארי באורך הסדרה.

1
Feedback