בעיית זרימה

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

בעיית "Min cost flow" הינה בעיית אופטימיזציה שמטרתה מציאת הדרך הזולה ביותר להעברת זרימה בגודל מסוים ברשת זרימה קיימת.

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

בהינתן, רשת זרימה \,G(V,E,s,t,c) כאשר s \in V צומת מקור, t \in V צומת בור וקשת (u,v) \in E בעלת קיבולת \,c(u,v), זרימה \,f(u,v) ומחיר \,a(u,v). מחיר העברת הזרימה בקשת (u,v) הינו f(u,v) \cdot a(u,v).

מטרת הבעיה הינה להעביר כמות נתונה של זרימה \,d מקודקוד המקור (s) לקודקוד הבור (t), כך שהמחיר הכולל,

\sum_{u,v \in V} a(u,v) \cdot f(u,v) יהיה מינימלי.

הפתרון נדרש לקיים את אילוצי הזרימה הבאים:

אילוצי קיבול: \,f(u,v) \le c(u,v)
סימטריות: \,f(u,v) = - f(v,u)
שימור זרימה (שימור חומר): \,\sum_{w \in V} f(u,w) = 0 for all \,u \neq s, t
שימור גודל הזרימה הנדרש: \,\sum_{w \in V} f(s,w) = d and \,\sum_{w \in V} f(w,t) = d

הכללה ובעיות הקשורות לבעיית Min cost flow[עריכת קוד מקור | עריכה]

גרסאות אחרות של בעיה זו מדברות על מציאת זרימה מקסימלית בעלת המחיר הקטן ביותר מבין כל הזרימות המקסימליות האפשריות, בעיות מסוג זה נקראות "minimum cost maximum flow". הכללה של בעיה זו היא minimum cost circulation problem שבעזרתה ניתן לפתור את הבעיה הנדונה. זה נעשה על ידי חסימת ערכי קיבולות הקשתות ברשת על ידי 0 (חסם תחתון) והוספת קשת נוספת בעלת קיבולת c(t,s)=d וחסם תחתון l(t,s)=d, (המחברת ישירות את קודקוד הבור (t) חזרה לקודקוד המקור (s)) אשר קובעת את הזרימה הכוללת להיות f(s,t)=d. את הבעיה ניתן לחלק למקרים פרטיים בהם אילוצי הקיבולת מוסרים (ולכן הבעיה הופכת לבעיית מציאת המסלול הקצר ביותר), ומקרים בהם אנו מתעלמים ממחיר הזרימה (ולכן מחיר הזרימה דרך כל אחת מהקשתות שווה), בהם נקבל את בעיית הזרימה המקסימלית.

שיטות לפתרון הבעיה[עריכת קוד מקור | עריכה]

בעיית min cost flow ניתנת לפתרון על ידי תכנון לינארי, מאחר שאנו מחפשים אופטימיזציה לפונקציה לינארית וכל האילוצים הם פשוטים. כמו כן, קיימים אלגוריתמים קומבינטורים לפתרון הבעיה כאשר חלקם הכללות של אלגוריתמים לחיפוש ומציאת זרימה מקסימלית ברשת וחלקם האחר נוקט בגישות אחרות שונות.

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

  • Cycle Canceling
  • Minimum Mean Cycle Canceling
  • Successive Shortest Path and Capacity Scaling - שיטות דואליות שהן הכללה של אלגוריתם פורד פולקרסון.
  • Cost Scaling
  • Network Simplex - מקרה פרטי של תכנון לינארי בעזרת simplex medthod .

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

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

  • Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin (1993). Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Inc.. ISBN 0-13-617549-X
  • Morton Klein (1967). "A primal method for minimal cost flows with applications to the assignment and transportation problems". Management Science 14: 205-220.
  • Andrew V. Goldberg and Robert E. Tarjan (1989). "Finding minimum-cost circulations by canceling negative cycles". Journal of the ACM 36 (4): 873-886.
  • Jack Edmonds and Richard M. Karp (1972). "Theoretical improvements in algorithmic efficiency for network flow problems". Journal of the ACM 19 (2): 248-264.
  • Andrew V. Goldberg and Robert E. Tarjan (1990). "Finding minimum-cost circulations by successive approximation". Math. Oper. Res. 15 (3): 430-466.

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