|
|
صفحة: 318
שאלה 5 . 32 רשת תקשורת כלשהי מתוארת על-ידי גרף מכוון , שבו כל קשת מייצגת ערוץ תקשורת , ולכל קשת ( u , v ) יש "משקל" r ( u , v ) שהוא מספר בין 0 , 1-ל המבטא את אמינותו ( reliability ) של הערוץ ( ולמעשה זו ההסתברות שהוא יעבוד . ( בהנחה שמתקיימת אי-תלות הסתברותית בין האמינות של קשתות שונות , אזי האמינות של מסלול כלשהו היא מכפלת ההסתברויות על קשתותיו . עליכם למצוא אלגוריתם יעיל שמקבל גרף כזה וזוג קדקודים * 1 x 11 ומוצא מסלול אמין ביותר s-a . ? -ל ( הערה כדאי להפריד בין הצגת האלגוריתם להוכחה שלו . הצגת האלגוריתם הוא פשוטה יחסית , גם אס ההוכחה שלו דורשת מאמץ מסוים . ( שאלה 5 . 33 הגרף G מוגדר על-ידי , G = { V , E ) כאשר ' ' ז מבטא קבוצות צמתים בגרף , £ -ו מבטא קבוצת קשתות בגרף . rwnip פונקציית המשקל 1 Dt > n ) ^^^^ W = E ^> R + ) . G ^^^^ n \ yp ^^^ לפניכם רשת a מצאו את המסלולים הקצרים ביותר מן הצומת A לכל אחד מן הצמתים האחרים ברשת הנתונה . תארו את המסלולים האלה בצורת עץ , באופן סכמתי . ב . כל קשת בגרף G צבועה בכחול או באדום . X וז > 4 הם צמתים בגרף . ( Y e F- ) X £ ) V כתבו אלגוריתם מילולי , קצר ויעיל , בעברית מבנית , למציאת אורך המסלול הקצר ביותר wtr x-a כאשר חלקו הראשון של המסלול יהיה מורכב מקשתות אדומות בלבד וחלקו השני יהיה מורכב מקשתות כחולות בלבד . שימו לב : כל אחד משני החלקים יכול להיות ריק .
|
|