Question

spring_15_b
shortest_path

שי אגסי נוסע לחופשה באילת בתום תקופת הבחינות. המכונית שלו מונעת על ידי סוללה. כאשר הסוללה טעונה במלואה היא מאפשרת נסיעה למרחק XX קלימוטרים. את הסוללה ניתן להחליף בסוללה טעונה התחנה המיועדת לכך. לשי יש מפה של כבישים ותחנות החלפת סוללה. המפה נתונה כגרף מכוון עם משקלים על הקשתות. הקשתות מייצגות את הכבישים והמשקלים את המרחקים. הצמתים בגרף מייצגים צמתי דרכים ובחלקם ישנן תחנות החלפת סוללה.

הגרף הבא מייצג מפה כאשר צמתי הדרכים עם תחנת החלפת הסוללה מסומנים בריבוע.

tikz

א. עבור הגרף הנתון, מצאו את המסלול הקל ביותר מ-ss ל-tt כאשר =200= 200 XX.

רשמו את המסלול ואת אורכו (אין צורך להוכיח/לנמק).

ב. עבור הגרף הנתון, מצאו את המסלול הקל ביותר מ-ss ל-tt כאשר =30= 30 XX.

רשמו את המסלול ואת אורכו (אין צורך להוכיח/לנמק).

ג. הציעו אלגוריתם יעיל שבהינתן מפה, נקודת יציאה ונקודת יעד, מוצא את המסלול הקל ביותר תחת האילוץ של קיבול הסוללה, הניחו שמתחילים את הנסיעה עם סוללה מלאה, ושאפשר לסיים את הנסיעה עם סוללה ריקה. על האלגוריתם להודיע במקרה ולא קיים מסלול כזה.

1

Answers

א. המסלול הקל ביותר הוא s,a,c,d,ts,a,c,d,t ומשקלו הוא 5151.

ב. המסלול הקל ביותר הוא s,b,c,e,ts,b,c,e,t ומשקלו הוא 6060.

ג. נשים לב שבכל מסלול חוקי קל ביותר המרחקים בין התחנות ההם XX לכל היותר והמסלול מתחנה לתחנה הוא המסלול הקל ביותר האפשרי בין שתי התחנות. הטענה נכונה גם עבור המסלולים מנקודת היציאה לתחנה הראשונה ומהתחנה האחרונה במסלול לנקודת סיום.

נסמן ב-G=(VS,E)G = (V \cup S, E) את הגרף המתאים למפה כאשר VV צמתים רגילים ו-SS תחנות החלפה.

עבור XX נתון נבנה את הגרף GX=({s,t}S,EX)G_X = (\{s, t\} \cup S, E_X) כאשר עבור צמתים u,vSu,v \in S:

EX={sv:d(s,v)X}{uv:d(u,v)X}{vt:d(v,t)X}E_X = \{sv : d(s, v) \leq X\} \cup \{uv : d(u,v) \leq X\} \cup \{vt : d(v,t) \leq X\}

עבור קשת uvEXuv \in E_X נגדיר את המשקל שלה להיות d(u,v)d(u,v) ונתאים לה מסלול קל ביותר ב-GG בעל משקל כזה.

האלגוריתם:

  • אם קיים מסלול קל ביותר מ-ss ל-tt במשקל קטן או שווה ל-XX החזר אותו.
  • בנה את הגרף כמתואר לעיל וחשב עליו מסלול קל ביותר מ-ss ל-tt.
  • החזר את המסלול המתאים ב-GG.

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

סיבוכיות: כדי לבנות את הגרף החדש יש צורך לדעת את המרחקים בין כל זוג צמתים וזאת ניתן לחשב בזמן O(V3)O(V^3). שאר הפעולות נבלעות בסיבוכיות הנ"ל.

1
Feedback