Question

winter_16-17_a

dynamic_programming

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

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

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

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

Answers

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

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

כאשר

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

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

נגדיר

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

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

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

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

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