מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/מסלולים זולים לכלל הזוגות

מתוך ויקיספר, אוסף ספרי הלימוד והמדריכים החופשי.

קפיצה אל: ניווט, חיפוש


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


{{{גודל}}}

כדאי לדעת:

  1. באלגוריתם Dijkstra עסקנו בבעיה דומה, אלא ששם היינו צריכים למצוא את המסלולים הזולים מצומת מוצא מסוים, ולא בין כל שני זוגות כמו כאן.
  2. בספר הקורס, הפרק "All-Pairs Shortest Paths" מכסה נושא זה.




[עריכה] הבעיה

נתונים גרף מכוון \displaystyle G = (V, E) וטבלת עלויות לקשתות \displaystyle E. בהינתן צמתים \displaystyle u, v \in V, רוצים למצוא את המסלול הזול ביותר מ\displaystyle u ל\displaystyle v.


Achtung.svg

שימו לב:

בדף זה לא נעסוק במחירי קשתות שאינם חיוביים.






דוגמה:

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

בעיית המסלולים הזוגים לכלל הזוגות.
  1. המסלול הזול ביותר מ\displaystyle 1 ל\displaystyle 2, לדוגמה, הוא \displaystyle 1 \rightarrow 4 \rightarrow 2, ועלותו 2.
  2. המסלול הזול ביותר מ\displaystyle 2 ל\displaystyle 4, לדוגמה, הוא \displaystyle 2 \rightarrow 3 \rightarrow 4, ועלותו 11.
  3. אין מסלול מ\displaystyle 2 ל\displaystyle 1, ולכן עלות המסלול הזול ביותר היא \infty.



[עריכה] הקלט

כפי שנאמר מקודם, נניח שמחירי הקשתות נתונות ע"י טבלת עלויות. בד"כ אנו מניחים שזה נעשה על ידי טבלת ערבול על הקשתות, אך כאן נניח משהו שונה במקצת. נניח שEdge-Costs היא מטריצה שלה כניסהEdge-Costs[u][v] לכל שני צמתים (כלומר, אף פעם לא מוחזר הערך Nil, כבטבלת ערבול). הערך Edge-Costs[u][v], הנו:

  1. 0, אם \displaystyle u = v.
  2. מחיר הקשת מu לv, אם יש קשת כזו.
  3. \displaystyle \infty, אם אין קשת כזו, ו\displaystyle u \neq v.
{{{גודל}}}

כדאי לדעת:

במידה מסויימת, הוספת הכניסות לEdge-Costs "מוסיפה" לגרף קשתות בעלות משקלים 0 ו\displaystyle \infty.

סטודנטים להנדסה יזהו אולי דמיון למעגלים חשמליים, בהם:

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






דוגמה:

בתרשים הבא, A מראה שוב את הגרף שראינו לעיל. B מראה קשתות ש"נוספו" בגלל 3, וC קשתות ש"נוספו" בגלל 2.

הקלט לבעיה.



קל לראות שהתוספות הנ"ל אינן משנות דבר משמעותי:



משפט:

אין הבדל בין מחירי המסלולים הזולים ביותר בגרף המקורי לאלה שבגרף ה"מוסף".



[עריכה] הרעיון הכללי

{{{גודל}}}

כדאי לדעת:

כל האלגוריתמים (שאותם נלמד) למציאת מסלולים זולים לכלל הזוגות מתבססים על אותו הרעיון.

  1. ראשית, מניחים שהקלט של הבעיה מתאר את הבעיה בצורה נוחה (לעיתים יש צורך בהוספת עוד קשתות לגרף. מסלולים זולים לכלל הזוגות עוסק בכך).
  2. כעת עובדים בשיטת הפרד ומשול - מוצאים את פתרונן של בעיות "גדולות" יותר בעזרת פתרונן של בעיות "קטנות" יותר. השאלה היא כיצד מגדירים מהן בעיות "קטנות" ו"גדולות":
    • באלגוריתם "הכפלת מטריצות" נראה שיטה לפיה פותרים בעיות קטנות יותר, בהן המסלול הזול ביותר מוגבל באורך.
    • באלגוריתם Floyd-Warshall נראה שיטה לפיה פותרים בעיות קטנות יותר, בהן המסלול הזול ביותר מוגבל בקבוצות צמתי הביניים של המסלול.




הפרק הקודם:
אלגוריתם Dijkstra		 מסלולים זולים לכלל הזוגות
תרגילים		 הפרק הבא:
אלגוריתם "הכפלת מטריצות"



מקור: http://he.wikibooks.org/wiki/%D7%9E%D7%91%D7%A0%D7%99_%D7%A0%D7%AA%D7%95%D7%A0%D7%99%D7%9D_%D7%95%D7%90%D7%9C%D7%92%D7%95%D7%A8%D7%99%D7%AA%D7%9E%D7%99%D7%9D_-_%D7%9E%D7%97%D7%91%D7%A8%D7%AA_%D7%A7%D7%95%D7%A8%D7%A1/%D7%92%D7%A8%D7%A4%D7%99%D7%9D/%D7%9E%D7%A1%D7%9C%D7%95%D7%9C%D7%99%D7%9D_%D7%96%D7%95%D7%9C%D7%99%D7%9D_%D7%9C%D7%9B%D7%9C%D7%9C_%D7%94%D7%96%D7%95%D7%92%D7%95%D7%AA