שאלת מבחן באלגוריתמים - האוניברסיטה הפתוחה 2020 - זרימה ברשתות

במסגרת הפקה של סרט קולנוע עלינו ללהק שחקנים מבין השחקנים $A_1, A_2, \ldots, A_n$, ולבחור משקיעים מבין המשקיעים $I_1, I_2, \ldots, I_m$. ידוע לנו השכר המדויק $W_i$ של שחקן $A_i$ (לכל $1 \leq i \leq n$), וסכום ההשקעה המדויק $P_k$ של משקיע $I_k$ (לכל $1 \leq k \leq m$). עבור כל זוג של שחקן-משקיע ידוע לנו האם הם בקשר של "נאמנות": שחקן $A_i$ ישתתף בסרט רק אם כל המשקיעים להם הוא נאמן ישתתפו במימון, ובדומה, משקיע $I_k$ ישקיע בסרט רק אם כל השחקנים להם הוא נאמן ילוהקו למשחק. (מעבר לכך אין אילוצים נוספים, ובפרט, איננו מחויבים ללהק מספר מסוים של שחקנים, או לגייס מספר מסוים של משקיעים). בחירה חוקית של שחקנים ומשקיעים הינה בחירה שמקיימת את אילוצי הנאמנות. בבעיית ההפקה מחפשים בחירה חוקית כך שיתקבל רווח מרבי, כשהרווח הינו סך כל המימון מן המשקיעים פחות סך כל המשכורות לשחקנים. בשאלה זו נפתור את בעיית ההפקה בעזרת בנייה של רשת זרימה, כך שהזרימה המרבית ברשת תגדיר את הפתרון האופטימלי לבעיית ההפקה. מעבר לקדקודי המקור והיעד, יהיו ברשת קדקוד יחיד לכל שחקן, וקדקוד יחיד לכל משקיע. המפתח לפתרון נכון הינו התשובה לשאלה הבאה: אילו צלעות/קיבול ות יש להגדיר בין קדקודי-משקיעים לבין קדקודי-שחקנים ברשת, כך שזרימה מרבית תגדיר (בפרט) פתרון חוקי לבעיית ההפקה. ענו על 3 הסעיפים הבאים. שימו לב: סעיף (ג) מופיע בעמוד הבא. (הנכם רשאים להניח שהרווח המרבי חיובי ממש. אין צורך לנתח יעילות). (א) מהן הצלעות ברשת ומהן הקיבולות שלהן? (ב) מדוע זרימה מרבית ברשת מגדירה בחירה חוקית של שחקנים ומשקיעים? (ג) הוכיחו שזרימה מרבית ברשת מגדירה בחירה אופטימלית של שחקנים ומשקיעים.

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

פתרון: ## בניית רשת הזרימה ### (א) צלעות וקיבולות הרשת הרשת מכילה את הקודקודים $s$ (מקור), $t$ (יעד), $u_i$ לכל שחקן $A_i$, ו-$v_k$ לכל משקיע $I_k$. הצלעות הן: | צלע | כיוון | קיבולת | משמעות | |---|---|---|---| | $s \to v_k$ | מקור למשקיע | $P_k$ | הכנסת משקיע | | $u_i \to t$ | שחקן לסינק | $W_i$ | עלות שחקן | | $u_i \to v_k$ | שחקן למשקיע | $\infty$ | $A_i$ נאמן ל-$I_k$ | | $v_k \to u_i$ | משקיע לשחקן | $\infty$ | $I_k$ נאמן ל-$A_i$ | --- ### (ב) מדוע הזרימה המרבית מגדירה בחירה חוקית? תהי $(S, T)$ **חתך מינימלי** המתאים לזרימה מרבית, עם $s \in S, t \in T$. נגדיר: $$\text{שחקנים נבחרים} = \{A_i : u_i \in S\}, \quad \text{משקיעים נבחרים} = \{I_k : v_k \in S\}$$ מאחר שערך החתך **סופי**, אף צלע בעלת קיבולת $\infty$ אינה יכולה להיות בחתך. לכן: - אם $A_i$ נבחר ($u_i \in S$) ו-$A_i$ נאמן ל-$I_k$: קיימת צלע $u_i \to v_k$ בקיבולת $\infty$, ולכן **חייב להתקיים** $v_k \in S$, כלומר $I_k$ נבחר. ✓ - אם $I_k$ נבחר ($v_k \in S$) ו-$I_k$ נאמן ל-$A_i$: קיימת צלע $v_k \to u_i$ בקיבולת $\infty$, ולכן **חייב להתקיים** $u_i \in S$, כלומר $A_i$ נבחר. ✓ כך כל **אילוצי הנאמנות** מקוימים, והבחירה חוקית. $\blacksquare$ --- ### (ג) הוכחת אופטימליות **טענה:** ערך חתך $(S,T)$ שווה ל-$\displaystyle\sum_k P_k - \text{רווח}(S,T)$. **הוכחה:** ערך כל חתך סופי (חוקי) הוא: $$c(S,T) = \underbrace{\sum_{v_k \in T} P_k}_{\text{צלעות } s\to v_k \text{ שנחתכות}} + \underbrace{\sum_{u_i \in S} W_i}_{\text{צלעות } u_i\to t \text{ שנחתכות}}$$ כאשר $D = \{I_k : v_k \in S\}$ המשקיעים הנבחרים, ו-$E = \{A_i : u_i \in S\}$ השחקנים הנבחרים: $$c(S,T) = \left(\sum_{k=1}^m P_k - \sum_{I_k \in D} P_k\right) + \sum_{A_i \in E} W_i = \sum_{k=1}^m P_k - \underbrace{\left(\sum_{I_k \in D} P_k - \sum_{A_i \in E} W_i\right)}_{\text{רווח}(D,E)}$$ לכן: $$\text{רווח}(D,E) = \sum_{k=1}^m P_k - c(S,T)$$ מאחר ש-$\sum_k P_k$ **קבוע**, מקסום הרווח שקול ל**מזעור ערך החתך**. כמו כן, כל בחירה חוקית $(D,E)$ מגדירה חתך חוקי עם $c(S,T) = \sum_k P_k - \text{רווח}(D,E)$ וערך סופי (אין צלעות $\infty$ נחתכות בגלל חוקיות הבחירה). לפי **משפט המקסימום-מינימום** (max-flow min-cut): הזרימה המרבית שווה לחתך המינימלי. החתך המינימלי ממזער את $c(S,T)$, ולכן ממקסם את הרווח — כלומר, הזרימה המרבית מגדירה בחירה **אופטימלית**. $\blacksquare$