דיניץ'

Summary:

אופן פעולת האלג'

דיניץ'

Guy (guest) 02 Jun 2013 12:07

לגבי אופן פעולת דיניץ': לדוגמא בשאלה שלוש מהמצגת האחרונה ( מכונות ומשימות )

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

שתזרים m מתוך s (דרך המשימות

השונות- דרך כל קשת זרימה =1 ) ולכן יסתיים גם התהליך וזו תהיה גם זרימה מקסימלית?

Re: דיניץ'

Shai V 09 Jun 2013 06:44

Dinic finds a BLOCKING flow. Notice that, in the example, Filter and Capuccino can block Mocha… so Dinic's algorithm won't necessarily terminate in the first step…

Guy (guest) 09 Jun 2013 10:24

ממה שהבנתי, זרימה חוסמת היא כזו שיש קשת אחת לפחות רוויה בכל מסלול מ s ל t

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

לכן, הייתי מצפה שבסוף הפאזה הראשונה, הזרימה החוסמת תגרום לכל מסלול באורך שלוש לא להיות קיים יותר, ואז אין יותר מסלולים באורך גדול מ3…

ומפה שהאלגוריתם יסיים.

אשמח לדעת איפה הטעות שלי..

תודה רבה.

Shai V 09 Jun 2013 11:59

Let all the $n_i$'s be 1…
Look at just the top of the picture - just Filter and Mocha and the two top machines….
Max flow on this sub graph is 2. All paths are of lengths 3. Filter - top machine is a blocking flow - there are three possible s-t paths - all have a saturated edge.

Although the network has only paths of length 3, the residual network can have longer paths… specifically in this case after adding the flow I suggested, there is a path of length 5 in the residual network.