פרדוקס ברס

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

פרדוקס בְּרָס (Braess's paradox), הנקרא על שם המתמטיקאי הגרמני דיטריך ברס, הוא דוגמה למצב שבו הוספת קשת נוספת לרשת שבה הישויות הנעות בוחרות את מסלול הזרימה האופטימלי באופן אנוכי, יכולה לגרום לירידה בביצועים הממוצעים של הרשת (זאת כמובן על אף האינטואיציה שאומרת שיותר מסלולים תמיד יובילו לביצועים משופרים).

הגדרה[עריכת קוד מקור | עריכה]

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

דוגמה[עריכת קוד מקור | עריכה]

דוגמה לפרדוקס של ברס

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

נניח בתחילה שהכביש המקווקו אינו קיים. אם A נהגים עוברים דרך נקודה A זה לוקח A/100+45 דקות ואם B נהגים בוחרים לעבור דרך נקודה B זה לוקח להם B/100+45 דקות. המקרה הגרוע ביותר הוא כאשר כל הנהגים בחרו לנסוע באותו הנתיב. אז ההאטה היא מקסימלית והנסיעה כולה לוקחת 90 דקות.אך בחירה אקראית באחד הנתיבים תוביל לתוצאה טובה יותר. אילו חצי מהנהגים יסעו בכל אחד מהנתיבים הזמן של הנסיעה יתקצר ל-2250/100+45=67.5. זהו שיווי משקל נאש.

כעת נניח שבונים כביש נוסף שמחבר את A עם B וזמן הנסיעה בו כל כך קצר שניתן אפילו לומר שהוא 0. במקרה כזה, הנהג האנוכי, אשר מנסה לשפר רק את מצבו שלו, יבחר לנסוע קודם לנקודה A (שם רק במקרה הגרוע הדרך לוקחת 45 דקות) אז יעבור בזמן 0 לנקודה B ומשם ימשיך ליעד (שוב, רק במקרה הגרוע הדרך תיקח 90 דקות). כלומר הנהג שמנסה לעשות אופטימיזציה לדרך שלו בלבד יבחר בדרך שרק במקרה הגרוע נמשכת 90 דקות, על פני מסלול שתמיד לוקח 90 דקות. אבל מאחר שכל הנהגים יבחרו באותה האסטרטגיה הם כולם יסעו קודם ל-A, אז ל-B ולבסוף ליעד וכך ייתממש המקרה הכי גרוע שבו הדרך נמשכת 90 דקות. אז הוספת הכביש לא רק שלא שיפרה את ביצועי המערכת אלא אף החמירה אותם. כאן הפתרון האופטימלי למערכת אינו יציב.

לקריאה נוספת[עריכת קוד מקור | עריכה]

  • Katharina Belaga-Werbitzky: „Das Paradoxon von Braess in erweiterten Wheatstone-Netzen mit M/M/1-Bedienern“ ISBN 3-89959-123-2)

קישורים חיצוניים[עריכת קוד מקור | עריכה]