ראשי > מסלולים קצרים > טכניקת ההקלה

טכניקת ההקלה

מבוא

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

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

איך זה עובד ?

עבור כל קודקוד v בגרף, אנו מחזיקים מאפיין [d[v, שהוא חסם עליון על משקלו של מסלול קצר ביותר מקודקוד המקור אל v.
למאפיין זה קוראים בד"כ אומדן של מסלול קצר ביותר ואנו נעזרים בפונקציה הבאה, המאוד פשוטה וטריוויאלית, כדי לאתחל את האומדנים של כל הקודקודים בגרף :

INITIALIZE-ESTIMATES (G,s)
1. for each vertex v in G
2.     d[v] = inf
3. d[s] = 0

בשלב זה של הלימודים, הסבר על פסואדו הקוד הפשוט הנ"ל, יהיה מיותר.

תהליך ההקלה

בתהליך ההקלה של קשת מ u אל v, בודקים אם ניתן לשפר את המסלול הקצר ביתור שנמצא עד כה אל v ע"י הגעה לקודקוד v דרך קודקוד u.
אם כך הדבר, נעדכן את [d[v. הפונקציה הבאה, הפשוטה אף היא, מבצעת צעד הקלה על הקשת מ u אל v .
שים לב כי w זוהי פונקצית המשקל על קשתות הגרף.

Improve (u, v, w)
1. if d[v] > d[u] + w(u,v) then
2.     d[v] = d[u] + w(u,v)

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

סיכום טכניקת ההקלה

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