Question

shortest_path
dynamic_programming

יהא G=(V,E)G = (V,E) גרף לא מכוון. יהא ss צומת מקור ו-tt צומת יעד. תהא w:EN{0}w:E \to \mathbb{N} \cup \{0\} פונקציית משקל על הקשתות, ו-c:ENc:E \to \mathbb{N} פונקציית מחיר על הקשתות. בנוסף, נתון לנו תקציב BNB \in \mathbb{N}.

בעיית המסלול הקל ביותר תחת אילוצי תקציב, היא למצוא ב-GG מסלול s=v1,,vk=ts = v_1, \ldots, v_k = t בעל משקל כולל i=1k1w(vivi+1)\sum_{i = 1}^{k -1} w(v_iv_{i+1}) מינימלי, תוך עמידה באילוצי התקציב, דהיינו - i=1k1c(vivi+1)B\sum_{i = 1}^{k - 1}c(v_iv_{i+1}) \leq B.

הציעו אלגוריתם לבעיית המסלול הקל ביותר תחת אילוצי תקציב הרץ בסיבוכיות זמן של O(V2B)O(|V|^2B). האם זמן הריצה פולינומיאלי באורך הקלט?

1

Answers

נסמן ב-f(u,v,B)f(u, v, B) את משקל מסלול קל ביותר מ-uu ל-vv תחת אילוץ תקציב BB ונשים לב שמתקיים

f(u,v,B)=minuuEw(uu)+f(u,u,Bc(uu)) f(u, v, B) = \min_{uu' \in E} w(uu') + f(u, u', B - c(uu'))

כאשר f(u,u,B0)=0f(u, u, B \geq 0) = 0 ו-f(u,v,B<0)=f(u, v, B < 0) = \infty.

את ff אפשר לחשב בטבלה בגודל B×VB \times V כאשר חישוב ערך של תא בודד לוקח O(V)O(V) וסך הכל חישוב הטבלה לוקח O(V2B)O(V^2B).

נשים לב שמכיוון ש-cc חיוביות ממש אז ניתן לחשב את ערכי הטבלה לפי השורות (מתקציב 0 לתקציב B).

את המסלול עצמו ניתן לשחזר על ידי שמירת מצביעים לצומת שממזער את הערך של ff.

זהו אלגוריתם פסאודו-פולינומי ובמקרה הגרוע הוא אקספוננציאלי באורך הקלט.

1
Feedback