Question

shortest_path

נתונה רשת תקשורת המורכבת מ-nn מחשבים ו-mm ערוצים (כל ערוץ מחבר בין שני מחשבים והינו דו-כיווני), כך שלכל ערוץ ee נתונה הסתברות p(e)p(e) שיקרוס. ההסתברויות בלתי תלויות.

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

1

Answers

נגדיר פונקציה f(e)=log(1p(e))f(e) = -\log(1 - p(e)) ונשים לב שמשקל מסלול PP ברשת הנתונה ביחס לפונקציה ff הוא:

ePlog(1p(e))=log(eP(1p(e))) -\sum_{e \in P}\log(1 - p(e)) = -\log\left(\prod_{e \in P}(1 - p(e))\right)

בנוסף הסיכוי שמסלול PP לא יקרוס הוא:

eP(1p(e)) \prod_{e \in P}(1 - p(e))

כלומר משקל מסלול קל ביותר ביחס ל-ff ממקסם את הסיכוי שמסלול לא יקרוס. נשים לב ש-ff היא אי שלילית ולכן ניתן למצוא מסלול כזה באמצעות דיקסטרה למשל בסיבוכיות זמן של O(mlogn)O(m\log n).

1
Feedback