Question

winter_16-17_a
dynamic_programming

נתון גרף מכוון G=(V,E)G = (V, E), צביעה של הקשתות בצהוב ושחור, c:E{B,Y}c:E \to \{B, Y\} וזוג צמתים s,tVs,t \in V.

א. נניח ש-GG חסר מעגלים. הציעו אלגוריתם הרץ בזמן O(V+E)O(|V| + |E|) המחשב מסלול מ-ss ל-tt המכיל מספר מקסימלי של קשתות צהובות.

ב. בהינתן זוג צמתים s,tVs,t \in V, הציעו אלגוריתם הרץ בזמן O(V+E)O(|V| + |E|) המחשב מסלול "קצר ביותר צהוב ביותר", כלומר מסלול בעל מספר מרבי של קשתות צהובות מתוך כל המסלולים הקצרים ביותר. אין צורך להוכיח נכונות.

שימו לב: הגרף בסעיף זה אינו בהכרח חסר מעגלים.

1

Answers

א. נסמן ב-f(v)f(v) להיות מספר הקשתות הצהובות במסלול צהוב ביותר מ-ss ל-vv וב-p(v)p(v) את האבא של vv במסלול כזה. קל לראות ש-

f(v)=minuvEI(uv)+f(u) f(v) = \min_{uv \in E} I(uv) + f(u)

כאשר

I(uv)={1c(uv)=Y0otherwise I(uv) = \begin{cases} 1 & c(uv) = Y \\ 0 & \text{otherwise} \end{cases}

בנוסף, אם לצומת v vsv \neq s אין הורים אז f(v)=f(v) = -\infty, ו-f(s)=0f(s) = 0. ניתן לחשב את ff לפי סדר מיון טופולוגי של GG.

נגדיר

p(v)=argminuvEI(uv)+f(u) p(v) = \arg\min_{uv \in E} I(uv) + f(u)

את המסלול עצמו ניתן לשחזר על ידי p(t)p(t).

ב. נגדיר את גרף המרחקים הקצרים ביותר להיות הגרף המכווןD=(V,A)D = (V, A) כאשר

A={uvE:d(s,v)=d(s,u)+1}A = \{uv \in E: d(s,v) = d(s,u) + 1 \}. נשים לב שזהו גרף חסר מעגלים ושאפשר לחשב אותו על ידי ריצה אחת של BFS. כמו כן, מסלול sts \rightsquigarrow t הוא קצר ביותר ב-GG אמ"מ הוא מסלול ב-DD.

נשתמש בסעיף הקודם על מנת למצוא מסלול צהוב ביותר.

1
Feedback