|
|
עמוד:230
נעבור לדון בכך כעת . . 2 ו 4 . 3 . ייצוג רשת באמצעות גרף נעבור כעת לדון בקלט לאלגוריתים לניתוב . כפי שציינו , הקלט הוא תיאור של רשת התקשורת . כשדנים ברשתות מיתוג מנות , מדובר על ניתוב מנות בין צומתי המיתוג של הרשת . אפשר למצוא דמיון רב בין ניתוב מנות ברשת תקשורת , לבין ניתוב כלי רכב ברשת כבישים , לכן נרבה להיעזר בהמשך בדוגמה של רשת הכבישים , שתמחיש את הניתוב ברשת תקשורת . שני ההיבטים המשותפים לשני סוגי הרשתות הם : הרשת מורכבת מצמתים שחלקם מחוברים ביניהם ( באמצעות ערוץ תקשורת או קטע כביש . ( ? לרוב קיימות כמה דרכים חלופיות מנה או כלי רכב יכולים לנוע בהן מנקודה א לנקודה ב ברשת . אפשר לתאר רשת באמצעות גרף . גרף הוא מבנה המורכב מקבוצת צמתים ( או קודקודים ) שחלקם מחוברים על-ידי צלעות ( או קשתות . ( כאשר גרף מתאר רשת תקשורת , כל צומת ( node ) בגרף מייצג צומת מיתוג של הרשת , וכל צלע בגרף מייצגת ערוץ תקשורת . כשמתארים רשת כבישים באמצעות גרף , צומתי הגרף מייצגים צומתי כבישים , וצלעות הגרף מייצגות קטעי כבישים המחברים בין הצמתים . מובן שהגרף לא יתאר את כל ההיבטים של הרשת ( למשל , בגרף לא יתואר הנוף הנשקף בקטע כביש מסוים , ( אך הוא יתאר את כל ההיבטים הרלוונטיים לניתוב ( הקשרים בין הצמתים ואורך הקטעים המחברים ביניהם . ( לכן , כאשר רוצים לבחור נתיב בין שני צמתים , אפשר להסתפק בתיאור הנתון באמצעות גרף . כפי שציינו , מטרתו של אלגוריתם ניתוב אינו רק למצוא מסלול כלשהו המחבר בין שני צמתים , אלא למצוא את המסלול הקצר ביותר . המונח 'קצר ביותר' דורש הבהרה . מהי אמת המידה ( המטריקה , ( metrics שנשתמש בה כדי למדוד מרחקים ברשת תקשורת ? ערוצי תקשורת , ממש כמו קטעי כביש , נבדלים זה מזה באורכם . אפשרות אחת היא להחליט שאמת המידה שתשמש את האלגוריתם היא המרחק הפיזי ( בקילומטרים ) בין הצמתים .
|
|