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

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

כדאי לדעת: נחלק את החומר שנלמד בזרימה לשלשה חלקים: בזרימה - הגדרות נגדיר מספר מושגים הנדרשים להגדרת הבעיה, כמו זרימה חוקית וגודל הזרימה. בזרימה שיורית וחתכים נעסוק במסלולים משפרים ברשת השיורית וחתכי S-T, ונראה מדוע מספיק לבדוק האם קיים מסלול משפר. באלגוריתמי זרימה נעסוק (מעט) בדרכים יעילות למצוא מסלול משפר.

כדאי לדעת: #בזרימה - הגדרות, תוכל למצוא מימוש C++ לאלגוריתמי זרימה. בספר הקורס, הפרק "Maximum Flow" (תתי פרקים 1 ו2) מכסה נושא זה.

שיטת Ford-Fulkerson

שיטת Ford-Fulkerson מתבססת על הרעיונות הבאים:

1. מסלולים משפרים מאפשרים למעשה לקבוע את זרימת המקסימום:
   1. ראינו בגודל זרימה ומסלולים משפרים שכל עוד מוצאים מסלול משפר בגרף הרשת השיורית, אפשר לשפר את הזרימה.
   2. ראינו בזרימה וחתכי S-T שאם אי אפשר למצוא מסלול משפר בגרף הרשת השיורית, אי אפשר לשפר את הזרימה.
2. קל לבנות את הרשת השיורית ולמצוא מסלול בה (או לחלופין, להיווכח שאין מסלול כזה). אם כי לא נתעמק בזאת, לא קשה לראות שאפשר לעשות זאת בסיבוכיות $\displaystyle O(E)$.שתי נקודות אלו מובילות לרעיון הבא, הידוע כשיטת Ford -Fulkerson:

הגדרה: שיטת Ford-Fulkerson בהינתן רשת הזרימה: ראשית קבע את זרימת האפס (כלומר הזרימה המשייכת לכל קשת זרימה 0). (זו בוודאי זרימה חוקית.) כל עוד יש מסלול משפר ברשת השיורית, שפר את הזרימה דרך מסלול זה.

כדאי לדעת: בקורס נלמד מספר אלגוריתמים (ודמויי אלגוריתמים) למציאת זרימה מקסימלית בעזרת מציאת מסלול משפר ברשת השיורית. אלגוריתמי הזרימה. שיטת Ford-Fulkerson מציעה להשתמש בכל פעם במסלול משפר ברשת השיורית כל עוד הדבר אפשרי. השיטה אינה מגדירה במדויק איך למצוא מסלול משפר כזה, וחשוב מכך, אינה מוכיחה סופיות (שהיא, כפי שראינו בתחילת הקורס כשדיברנו על הוכחת נכונות חיפוש לינארי, תנאי הכרחי לנכונות אלגוריתם). אלגוריתם Ford-Fulkerson הוא מקרה פרטי של שיטת Ford-Fulkerson, ופועל כאשר הקיבולים הם מספרים שלמים. אלגוריתם Edmonds-Karp הוא מקרה פרטי של שיטת Ford-Fulkerson, ופועל לכל מערכת קיבולים (לאו-דווקא שלמים).בנוסף, יש גם שיטות אחרות ומעניינות שאינן פועלות כלל לפי הרעיון הכללי הנ"ל. לא נלמד שיטות אלו בקורס; תוכל לקרוא על כך יותר בספר הקורס בפרק "Maximum Flow" (תתי-פרקים 4-5).

אלגוריתם Ford-Fulkerson

אלגוריתם Ford-Fulkerson הוא פחות-או-יותר שיטת Ford-Fulkerson בהקשר רשתות זרימה שבהן הקיבולים הם מספרים שלמים:

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

בניגוד למקרה הכללי, כאן (כשהקיבולים הם מספרים שלמים), קל-יחסית להראות שהאלגוריתם אכן עובד, ולנתח את סיבוכיותו:

משפט: נניח שברשת הזרימה, גודל זרימת המקסימום הוא $\displaystyle \left|f_{\ast }\right|$. אז אלגוריתם Ford-Fulkerson עובד בזמן $\displaystyle O(|E|\cdot \left|f_{\ast }\right|)$.

הוכחה: היות שהקיבולים שלמים, אם יש מסלול שיפור ברשת השיורית, גודל הזרימה יגדל ב1 (לפחות). היות שגודל זרימת המקסימום הוא $\displaystyle \left|f_{\ast }\right|$ (על פי הגדרתנו), אז לאחר $\displaystyle \left|f_{\ast }\right|$ שיפורים, נגיע בהכרח לזרימת מקסימום. זה מראה שהאלגוריתם עובד. הזכרנו מקודם שמציאת מסלול שיפור אורכת $\displaystyle \left|E\right|$,‏ ומכאן הסיבוכיות.

אלגוריתם Edmonds-Karp

אלגוריתם Edmonds-Karp הוא פחות-או-יותר שיטת Ford-Fulkerson, אך תוך ציון כיצד יש לבחור מסלול שיפור בגרף הרשת השיורית:

הגדרה: (אלגוריתם Edmonds-Karp) בהינתן רשת הזרימה: ראשית קבע את זרימת האפס. (אתחול זה משותף לכל אלגוריתם בשיטת Ford-Fulkerson) כל עוד יש מסלול משפר בגרף הרשת השיורית, מצא את המסלול הקצר ביותר (ספציפית, כמוחזר על ידי חיפוש רוחבי), ושפר על פיו.

שימו לב: בניגוד לאלגוריתם Ford-Fulkerson, אלגוריתם זה עובד גם על רשתות זרימה שקיבוליהן אינן מספרים שלמים.

משפט: אלגוריתם Edmonds-Karp עובד בזמן $\displaystyle O(|E|^{2}\cdot |V|)$.

להלן "הוכחת נפנופי-ידיים":

הוכחה: אם בוחרים בכל פעם את המסלול הקצר ביותר כמסלול השיפור בגרף הרשת השיורית (בלי קשר לצורה בה זה נעשה), אפשר להראות שיש לכל היותר $\displaystyle O(|V|\cdot |E|)$ שיפורים סה"כ. מצד שני, בלי קשר למספר השיפורים, אפשר להראות שבניית גרף הרשת השיורית, והרצת BFS עליו - אורכות $\displaystyle O(|E|)$ זמן. הסיבוכיות נובעת משילוב שתי הנקודות.

הפרק הקודם: זרימה שיורית וחתכים

אלגוריתמי זרימה תרגילים

הפרק הבא: נספחים