|
|
עמוד:242
4 . 3 . 3 אלגוריתמי ניתוב דינמיים בקביעת משקלי הצלעות , התייחסנו עד כה לתכונות של קטעי הכבישים או הערוצים , כאילו הן קבועות ואינן משתנות עם הזמן , אולם זה לא תמיד המצב . העומס בכבישים אינו קבוע , והוא עשוי להשתנות מרגע לרגע ; למשל : בשעות הלילה , העומס בנתיבי איילון נמוך ואילו בשעות הבוקר , בימי השבוע , העומס בדרך-כלל גבוה ביותר . אילו היינו מתייחסים רק לתכונות הקבועות של הכבישים , היינו בוחרים נתיבים באופן לא אופטימלי , כי היינו מעדיפים תמיד לנסוע בנתיבי איילון , וקרוב לוודאי שבשעות מסוימות היינו נקלעים לפקקי תנועה . כדי לקבל החלטות ניתוב טובות , יש להתייחס לעומס הרגעי של כל קטע כביש , כלומר לעומס הקיים בכביש ברגע חישוב הנתיב . כאמור , גם ברשתות תקשורת קיים עומס וכמו ברשת הכבישים , גם ברשתות תקשורת העומס פוגע קשות בזמני המעבר של מנות ברשת , והוא משתנה מרגע לרגע , בהתאם לתעבורה ברשת . כאשר רוצים לבחור נתיב קצר בין שתי נקודות , יש להתייחס לעומס הרגעי של כל הערוצים בזמן חישוב הנתיב , אחרת נקבל החלטות ניתוב לא נכונות . דוגמה נוספת מרשת הכבישים ו אם ברגע מסוים צומת שמריהו עמוס מאוד , עדיף לנסוע מחיפה לת"א דרך צומת מורשה , למרות שנתיב זה ארוך יותר מן הנתיב הישיר , דרך צומת שמריהו . נהגים שצריכים לבחור נתיב נסיעה ברשת כבישים עירונית , מתייחסים לנתונים של העומס הרגעי בקטעי הכביש לאורך נתיבי התנועה המקשרים בין מקום הימצאם ליעדם , ומשתדלים לבחור נתיב שאינו עמוס . מצב העומס בכבישים נצפה על-ידי מסוקים , הטסים מעל האזורים הצפופים ומדווחים ברשתות הרדיו על מצבי עומס חריגים . כיום מחליט הנהג בעצמו , על סמך הדיווחים , באיזה נתיב לנסוע . נניח לרגע שבעתיד יהיה בכל כלי רכב מחשב ניווט קטן , שיוכל לקלוט תשדורות ממסוק או מלווין ולדעת בכל רגע הערות = א . אפשר להשתמש באלגוריתם של דייקסטרה למציאת המסלול הקצר ביותר מצומת המקור לכל אחד מצמתי בגרף . ב . אפשר להוכיח שאלגוריתם זה מוצא תמיד את המסלול הקצר ביותר בגרף ( ההוכחה חורגת ממסגרת זו . (
|
|