הצגת המקור של הדף "מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/אלגוריתמי זרימה"

{{מבני נתונים ואלגוריתמים - מחברת קורס}}


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



{{הארה|1=
{{:מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/מבנה החומר בזרימה}}
}}

{{הארה|1 = 
#ב[[מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/זרימה - הגדרות|זרימה - הגדרות]], תוכל למצוא מימוש {{משמאל לימין|C++}} לאלגוריתמי זרימה.
#ב[[מבני נתונים ואלגוריתמים - מחברת קורס#ספר הקורס|ספר הקורס]], הפרק "Maximum Flow" (תתי פרקים 1 ו2) מכסה נושא זה.

}} 


==שיטת Ford-Fulkerson==

שיטת Ford-Fulkerson מתבססת על הרעיונות הבאים:
#מסלולים משפרים מאפשרים למעשה לקבוע את זרימת המקסימום:
##ראינו ב[[מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/זרימה שיורית וחתכים#גודל זרימה ומסלולים משפרים|גודל זרימה ומסלולים משפרים]] שכל עוד מוצאים מסלול משפר בגרף הרשת השיורית, אפשר לשפר את הזרימה.
##ראינו ב[[מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/זרימה שיורית וחתכים#זרימה וחתכי S-T|זרימה וחתכי S-T]] שאם אי אפשר למצוא מסלול משפר בגרף הרשת השיורית, אי   אפשר לשפר את הזרימה.
#קל לבנות את הרשת השיורית ולמצוא מסלול בה (או לחלופין, להיווכח שאין מסלול כזה). אם כי לא נתעמק בזאת, לא קשה לראות שאפשר לעשות זאת בסיבוכיות <math dir = "ltr">\displaystyle O(E)</math>.שתי נקודות אלו מובילות לרעיון הבא, הידוע כשיטת Ford -Fulkerson:

{{:מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/אלגוריתמי זרימה/הגדרת שיטת Ford-Fulkerson}}


{{הארה|1 = 
בקורס נלמד מספר אלגוריתמים (ודמויי אלגוריתמים) למציאת זרימה מקסימלית בעזרת מציאת מסלול משפר ברשת השיורית.

[[תמונה:Dsa flow flow hierarchy.png|מרכז|100%|אלגוריתמי הזרימה.]]

#שיטת 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 יחידת זרימה (לפחות).}} 

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

{{משפט|תוכן = 
נניח שברשת הזרימה, גודל זרימת המקסימום הוא <math dir = "ltr">\displaystyle \left|f_{\ast}\right|</math>. אז אלגוריתם
Ford-Fulkerson עובד בזמן <math dir = "ltr">\displaystyle O(|E| \cdot \left|f_{\ast}\right|)</math>.}} 


{{הוכחה|1 = 
היות שהקיבולים שלמים, אם יש מסלול שיפור ברשת השיורית, גודל הזרימה יגדל ב1 (לפחות). היות שגודל זרימת המקסימום
הוא <math dir = "ltr">\displaystyle \left|f_{\ast}\right|</math> (על פי הגדרתנו), אז לאחר <math dir = "ltr">\displaystyle \left|f_{\ast}\right|</math> שיפורים, נגיע בהכרח לזרימת מקסימום. זה מראה שהאלגוריתם עובד. הזכרנו מקודם
שמציאת מסלול שיפור אורכת <math dir = "ltr">\displaystyle \left|E\right|</math>,‏ ומכאן הסיבוכיות.}}

==אלגוריתם Edmonds-Karp==

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

{{הגדרה|תוכן = 
(אלגוריתם Edmonds-Karp) בהינתן רשת הזרימה:
#ראשית קבע את זרימת האפס. (אתחול זה משותף לכל אלגוריתם בשיטת Ford-Fulkerson)
#כל עוד יש מסלול משפר בגרף הרשת השיורית, מצא את המסלול '''הקצר ביותר''' (ספציפית, כמוחזר על ידי [[מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/חיפוש רוחבי|חיפוש רוחבי]]), ושפר על פיו.}} 


{{שימו לב|1 = 
בניגוד ל[[#אלגוריתם Ford-Fulkerson|אלגוריתם Ford-Fulkerson]], אלגוריתם זה עובד גם על רשתות זרימה שקיבוליהן אינן מספרים שלמים.}} 


{{משפט|תוכן = 
אלגוריתם Edmonds-Karp עובד בזמן <math dir = "ltr">\displaystyle O(|E|^2 \cdot |V|)</math>.}} 

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

{{הוכחה|1 = 
אם בוחרים בכל פעם את המסלול הקצר ביותר כמסלול השיפור בגרף הרשת השיורית (בלי קשר לצורה בה זה נעשה), אפשר להראות
שיש לכל היותר <math dir = "ltr">\displaystyle O(|V| \cdot |E|)</math> שיפורים סה"כ.
מצד שני, בלי קשר למספר השיפורים, אפשר להראות שבניית גרף הרשת השיורית, והרצת BFS עליו - אורכות <math dir = "ltr">\displaystyle O(|E|)</math> זמן.
הסיבוכיות נובעת משילוב שתי הנקודות.}}


{{מבני נתונים ואלגוריתמים - מחברת קורס|מוגבל}}
[[קטגוריה:מבני נתונים ואלגוריתמים]]