כיצד למצוא את ה"מסלולים" של כל הזוגות הקצרים ביותר עם אלגוריתם פלויד-ורשל ב-C#

מָבוֹא

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

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

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

קצת תיאוריה ידועה...

לפני שנצלול לתוך קוד ואמות מידה, בואו נשנה תיאוריה של איך האלגוריתם של פלויד-ורשל עובד.

להלן תיאור טקסטואלי של האלגוריתם:

1. נתחיל בייצוג גרף ( G ) בגודל N כמטריצה ( W ) בגודל N x N כאשר כל תא W[i,j] מכיל את המשקל של קצה מקודקוד i לקודקוד j (ראה תמונה 1). במקרים בהם אין קצה בין קודקודים, התא מוגדר לערך NO_EDGE מיוחד (מוצג כתאים כהים בתמונה 1).

   
   

2. מעתה נאמר – W[i,j] מכיל מרחק בין קודקודים i ו- j .

   
   

3. לאחר מכן, ניקח קודקוד k ונחזור על כל זוגות הקודקודים W[i,j] ובודקים אם המרחק i ⭢ k ⭢ j קטן מהמרחק הידוע כיום בין i ל- j .

   
   

4. הערך הקטן ביותר מאוחסן ב- W[i,j] ושלב #3 חוזר על עצמו עבור ה- k הבא עד שכל הקודקודים של G שימשו כ- k .

הנה הפסאודו-קוד:

 algorithm FloydWarshall(W) do for k = 0 to N - 1 do for i = 0 to N - 1 do for j = 0 to N - 1 do W[i,j] = min(W[i,j], W[i,k] + W[k,j]) end for end for end for end algorithm

בסיום, כל תא W[i,j] של המטריצה W מכיל או מכיל מרחק של הנתיב הקצר ביותר בין קודקודים i ו- j או ערך NO_EDGE , אם אין נתיב ביניהם.

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

ובכן... זה אולי נשמע מובן מאליו אבל... אנחנו צריכים לאסוף נתונים נוספים!

... קצת מאותה תיאוריה אבל מזווית אחרת

המהות של אלגוריתם פלויד-ורשל היא תא של מרחק ידוע W[i,j] עם מרחק של נתיב פוטנציאלי חדש מ- i ל- j דרך קודקוד ביניים k .

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

בתחילה, אנו יודעים על כל קצוות הגרף, מה שנותן לנו את הנתיבים הבאים: 0 ⭢ 1 :2 , 0 ⭢ 4 :10 , 1 ⭢ 3 :1 , 2 ⭢ 4 :1 , 3 ⭢ 2 :1 ו 3 ⭢ 4 :3 .

אנחנו גם יודעים שאין קצוות המובילים לקודקוד 0 , ולכן ביצוע אלגוריתם עבור k = 0 אינו הגיוני. זה גם ברור, יש קצה בודד ( 0 ⭢ 1 ) המוביל מקודקוד 0 לקודקוד 1 , מה שהופך גם את הביצוע של כל i != 0 (ה- i הוא "מכאן") די חסר משמעות ומכיוון שקודקוד 1 יש קצוות עם 2 ו 4 , זה גם לא הגיוני לבצע אלגוריתמים עבור כל j שהוא לא 2 או 4 (ה- j הוא "to" כאן).

לכן הצעד הראשון שלנו יהיה לבצע אלגוריתם עבור k = 1 , i = 0 ו- j = 2,4 .

שָׁלָב	נָתִיב	הֶעָרָה
1	0 ⭢ 1 ⭢ 2	נתיב נמצא. מרחק = 3 (היה כלום)
2	0 ⭢ 1 ⭢ 4	נתיב נמצא. מרחק = 8 (היה 10).

מצאנו שני נתיבים: נתיב חדש ( 0 ⭢ 1 ⭢ 2 ) וקיצור דרך ( 0 ⭢ 1 ⭢ 4 ). שניהם עוברים דרך קודקוד 1 . אם לא נאחסן את המידע הזה (העובדה שהגענו ל 2 ו 4 עד 1 ) איפשהו עכשיו, הוא יאבד לנצח (וזה בדיוק ההפך ממה שאנחנו רוצים).

אז מה עלינו לעשות? נעדכן את המטריצה W בערכים חדשים (ראה תמונה 3a) וגם נאחסן את הערך של k (שהוא k = 1 ) בתאים R[0,2] ו- R[0,4] של מטריצה חדשה R באותו גודל כמטריצה W אך אתחול עם ערכי NO_EDGE (ראה תמונה 3b).

כרגע, אל תתמקד במטריצה R בדיוק. בואו פשוט נמשיך ונבצע את האלגוריתם עבור k = 2 הבא.

כאן, נעשה את אותו ניתוח (כדי להבין אילו שילובים הגיוני לבצע) כפי שעשינו עבור k = 1, אבל הפעם, נשתמש במטריצה W במקום גרף G . הסתכלו על המטריצה W , במיוחד בעמודה מס' 2 ובשורה מס' 2 (תמונה 4).

כאן אתה יכול לראות, ישנם שני נתיבים לקודקוד 2 מקודקוד 0 ומקודקוד 1 (עמודה מס' 2), ושני נתיבים מקודקוד 2 לקודקוד 3 ולקודקוד 4 (שורה מס' 2). לדעת זאת, הגיוני לבצע את האלגוריתם רק עבור שילובים של k = 2 , i = 0,1 ו- j = 3,4 .

שָׁלָב	נָתִיב	הֶעָרָה
1	0 ⭢ 2 ⭢ 3	נתיב נמצא. מרחק = 4 (היה כלום)
2	0 ⭢ 2 ⭢ 4	נתיב נמצא. מרחק = 6 (היה 8)
3	1 ⭢ 2 ⭢ 3	נתיב נמצא. מרחק = 2 (היה כלום)
4	1 ⭢ 2 ⭢ 4	נתיב נמצא. מרחק = 4 (היה 6)

כפי שכבר עשינו בעבר, אנו מעדכנים את התאים W[0,3] , W[0,4] , W[1,3] , W[1,4] עם מרחקים חדשים ותאים R[0,3] , R[0,4] , R[1,3] ו- R[1,4] עם k = 2 (ראה תמונה 5).

נותרו רק k = 3 לעיבוד (מכיוון שאין קצוות המובילים מקודקוד 4 לכל קודקוד אחר בגרף).

שוב, בואו נסתכל על המטריצה W (תמונה 6).

לפי המטריצה W , ישנם שלושה נתיבים לקודקוד 3 מקודקודים 0 , 1 ו 2 (עמודה מס' 3), ויש נתיב אחד מקודקוד 3 לקודקוד 4 (שורה מס' 3). לכן, יש לנו את הנתיבים הבאים לעיבוד:

שָׁלָב	נָתִיב	הֶעָרָה
1	0 ⭢ 3 ⭢ 4	נתיב נמצא. מרחק = 5 (היה 6)
2	1 ⭢ 3 ⭢ 4	נתיב נמצא. מרחק = 3 (היה 4)
3	2 ⭢ 3 ⭢ 4	נתיב נמצא. מרחק = 2 (היה 3)

זה היה האיטרציה האחרונה של האלגוריתם. כל שנותר הוא לעדכן את התאים W[0,4] , W[1,4] , W[2,4] במרחקים חדשים ולהגדיר את התאים R[0,4] , R[1,4] , R[2,4] עד 3 .

הנה מה שיש לנו בסוף האלגוריתם (תמונה 7).

כפי שאנו יודעים מהפוסט הקודם , מטריצה W מכילה כעת את כל זוגות הנתיבים הקצרים ביותר בגרף G אבל מה מאוחסן בתוך מטריצה R ?

שיבה הביתה

בכל פעם שמצאנו נתיב חדש וקצר ביותר, עדכנו את התא המתאים של המטריצה R בערך הנוכחי של k . אמנם בהתחלה, פעולה זו עשויה להיראות מסתורית, יש לה משמעות פשוטה מאוד - אחסנו את הקודקוד, שממנו הגענו לקודקוד היעד: i ⭢ k ⭢ j (כאן אנו מגיעים j ישירות מ- k ).

הרגע הזה הוא מכריע. כי הכרת קודקוד שממנו באנו מאפשרת לנו לבנות את המסלול מחדש על ידי מעבר לאחור (כמו לובסטר) מקודקוד j (ה"אל") לקודקוד i ("מאת").

להלן תיאור טקסטואלי של האלגוריתם לבנייה מחדש של המסלול מ- i ל- j :

1. הכן מערך דינמי ריק X
2. התחל בקריאת ערך z מהתא R[i,j] .
3. אם z הוא NO_EDGE , אזי נמצא המסלול מ- i ל- j ועלינו להמשיך לשלב #7.
4. הוסף z למערך דינמי X .
5. קרא את הערך של התא R[i,z] לתוך z .
6. חזור על שלבים #3, #4 ו- #5 עד שתגיע למצב היציאה ב- #3.
7. הוסף i ל-X.
8. הוסף j ל- X
9. כעת המערך הדינמי X מכיל את המסלול מ- i ל- j .

בפסאודו-קוד, זה נראה אפילו יותר פשוט:

 algorithm RebuildRoute(i, j, R) x = array() z = R[i,j] while (z ne NO_EDGE) do x.prepend(z) z = R[i,z] end while x.prepend(i) x.append(j) return x end algorithm

בואו ננסה את זה על הגרף G שלנו ונבנה מחדש מסלול מקודקוד 0 לקודקוד 4 (ראה תמונה 8).

להלן תיאור טקסטואלי של האיור לעיל:

1. נתחיל בקריאת הערך מ- R[0,4] , שמביא ל 3 . לפי האלגוריתם, זה אומר שהמסלול עובר לקודקוד 4 מקודקוד 3 (מוצג בכחול).

   
   

2. מכיוון שהערך של R[0,4] אינו NO_EDGE , אנו ממשיכים וקוראים את הערך של R[0,3] שמביא ל 2 (מוצג בירוק).

   
   

3. שוב, מכיוון שהערך של R[0,3] אינו NO_EDGE , אנו ממשיכים וקוראים את הערך של R[0,2] שמביא ל 1 (מוצג באדום).

   
   

4. לבסוף, אנו קוראים ערך של R[0,1] , שמביא לערך NO_EDGE , כלומר, אין יותר קודקודים מלבד 0 ו 4 שתורמים למסלול. לכן, המסלול המתקבל הוא: 0 ⭢ 1 ⭢ 2 ⭢ 3 ⭢ 4 שאם מסתכלים על הגרף אכן מתאים לנתיב הקצר ביותר מקודקוד 0 לקודקוד 4 .

קורא מתחשב עשוי לשאול:

זו שאלה טובה מאוד. אנו בטוחים כי אנו מעדכנים את המטריצה R בערך חדש כאשר אנו מעדכנים את ערך הנתיב הקצר ביותר במטריצה W אז בסופו של דבר, כל שורה של מטריצה R מכילה נתונים הקשורים לנתיבים הקצרים ביותר. לא יותר, לא פחות.

עכשיו, סיימנו עם התיאוריה, הגיע זמן היישום.

יישום ב-C#

בפוסט הקודם , מלבד הטמעת גרסה מקורית של אלגוריתם פלויד-ורשל, שילבנו גם אופטימיזציות שונות: תמיכה בגרפים דלילים, מקביליות ווקטוריזציה, ובסופו של דבר, גם שילבנו את כולם.

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

אינטגרציה באלגוריתם מקורי

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

1. הרחב את חתימת הפונקציה כך שתכלול מטריצת R כפרמטר נפרד - int[] routes .

   
   

2. שמור k routes בכל פעם שהנתיב הקצר ביותר משתנה (שורות: 2 ו-14).

זהו זה. רק שורה וחצי של קוד:

 public void BaselineWithRoutes( int[] matrix, int[] routes, int sz) { for (var k = 0; k < sz; ++k) { for (var i = 0; i < sz; ++i) { for (var j = 0; j < sz; ++j) { var distance = matrix[i * sz + k] + matrix[k * sz + j]; if (matrix[i * sz + j] > distance) { matrix[i * sz + j] = distance; routes[i * sz + j] = k; } } } } }

אינטגרציה באלגוריתם וקטוריזי

אינטגרציה בגרסה וקטורית (עם תמיכה בגרפים דלילים) דורשת קצת יותר מאמץ כדי להשלים, עם זאת, השלבים הרעיוניים זהים:

1. הרחב את חתימת הפונקציה כך שתכלול מטריצת R כפרמטר נפרד - int[] routes .

   
   

2. בכל איטרציה, אתחול וקטור חדש של k ערכים (שורה: 6).

   
   

3. שמור וקטור ערכי k routes בכל פעם שהנתיב הקצר ביותר משתנה (שורות: 31-32).

   
   

4. עדכן חלק לא מוקטור של האלגוריתם באותו אופן שבו עדכנו את האלגוריתם המקורי (שורה: 41).

 public void SpartialVectorOptimisationsWithRoutes( int[] matrix, int[] routes, int sz) { for (var k = 0; k < sz; ++k) { var k_vec = new Vector<int>(k); for (var i = 0; i < sz; ++i) { if (matrix[i * sz + k] == Constants.NO_EDGE) { continue; } var ik_vec = new Vector<int>(matrix[i * sz + k]); var j = 0; for (; j < sz - Vector<int>.Count; j += Vector<int>.Count) { var ij_vec = new Vector<int>(matrix, i * sz + j); var ikj_vec = new Vector<int>(matrix, k * sz + j) + ik_vec; var lt_vec = Vector.LessThan(ij_vec, ikj_vec); if (lt_vec == new Vector<int>(-1)) { continue; } var r_vec = Vector.ConditionalSelect(lt_vec, ij_vec, ikj_vec); r_vec.CopyTo(matrix, i * sz + j); var ro_vec = new Vector<int>(routes, i * sz + j); var rk_vec = Vector.ConditionalSelect(lt_vec, ro_vec, k_vec); rk_vec.CopyTo(routes, i * sz + j); } for (; j < sz; ++j) { var distance = matrix[i * sz + k] + matrix[k * sz + j]; if (matrix[i * sz + j] > distance) { matrix[i * sz + j] = distance; routes[i * sz + j] = k; } } } } }

Benchmarking

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

הנה שתי קבוצות של אמות מידה: עם ובלי (שניהם מבצעים גרסאות מקוריות וגם גרסאות וקטוריות של האלגוריתם). כל ההשוואות בוצעו על ידי v0.13.1 (.NET 6.0.4 x64) על מכונה המצוידת במעבד Intel Core i5-6200U CPU 2.30GHz (Skylake) ופועלת Windows 10.

כל הניסויים בוצעו על קבוצת הגרפים שהוגדרה מראש ששימשה בפוסט הקודם : 300, 600, 1200, 2400 ו-4800 קודקודים.

להלן תוצאות ההשוואה שבהן שיטות Baseline ו- BaselineWithRoutes מתאימות לגרסה המקורית של האלגוריתם ושיטות SpartialVectorOptimisations ו- SpartialVectorOptimisationsWithRoutes מתאימות לגירסה וקטורית (עם תמיכה בגרפים דלילים) של האלגוריתם.

שִׁיטָה	גוֹדֶל	ממוצע (ms)	שגיאה (ms)	StdDev (ms)
קו בסיס	300	40.233	0.0572	0.0477
BaselineWithRoutes	300	40.349	0.1284	0.1201
SpartialVectorOptimisations	300	4.472	0.0168	0.0140
אופטימיזציות וקטור חלקיות עם מסלולים	300	4.517	0.0218	0.0193
קו בסיס	600	324.637	5.6161	4.6897
BaselineWithRoutes	600	321.173	1.4339	1.2711
SpartialVectorOptimisations	600	32.133	0.2151	0.1679
אופטימיזציות וקטור חלקיות עם מסלולים	600	34.646	0.1286	0.1073
קו בסיס	1200	2,656.024	6.9640	5.8153
BaselineWithRoutes	1200	2,657.883	8.8814	7.4164
SpartialVectorOptimisations	1200	361.435	2.5877	2.2940
אופטימיזציות וקטור חלקיות עם מסלולים	1200	381.625	3.6975	3.2777
קו בסיס	2400	21,059.519	38.2291	33.8891
BaselineWithRoutes	2400	20,954.852	56.4719	50.0609
SpartialVectorOptimisations	2400	3,029.488	12.1528	11.3677
אופטימיזציות וקטור חלקיות עם מסלולים	2400	3,079.006	8.6125	7.1918
קו בסיס	4800	164,869.803	547.6675	427.5828
BaselineWithRoutes	4800	184,305. 980	210.9535	164.6986
SpartialVectorOptimisations	4800	21,882.379	200.2820	177.5448
אופטימיזציות וקטור חלקיות עם מסלולים	4800	21,004.612	79.8752	70.8073

תוצאות בנצ'מרק אינן פשוטות לפירוש. אם תסתכלו מקרוב, תמצאו שילוב כאשר איסוף המסלול למעשה גרם לאלגוריתם לרוץ מהר יותר או ללא השפעה משמעותית כלל.

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

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

הדבר היחיד שנותר הוא יישום של אלגוריתם בניית המסלול מחדש.

יישום אלגוריתם בניית מסלול מחדש

היישום של אלגוריתמים לבניית מסלול מחדש ב-C# הוא פשוט ומשקף כמעט לחלוטין את הפסאודו-קוד שהודגם קודם לכן (אנו משתמשים LinkedList<T> כדי לייצג מערך דינמי):

 public static IEnumerable<int> RebuildWithLinkedList( int[] routes, int sz, int i, int j) { var x = new LinkedList<int>(); var z = routes[i * sz + j]; while (z != Constants.NO_EDGE) { x.AddFirst(z); z = routes[i * sz + z]; } x.AddFirst(i); x.AddLast(j); return x; }

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

 public static IEnumerable<int> RebuildWithArray( int[] routes, int sz, int i, int j) { var x = new int[sz]; var y = sz - 1; // Fill array from the end x[y--] = j; var z = routes[i * sz + j]; while (z != Constants.NO_EDGE) { x[y--] = z; z = routes[i * sz + z]; } x[y] = i; // Create an array segment from 'y' to the end of the array // // This is required because 'sz' (and therefore length of the array x) // equals to the number of vertices in the graph // // So, in cases when route doesn't span through // all vertices - we need return a segment of the array return new ArraySegment<int>(x, y, sz - y); }

אמנם "אופטימיזציה" זו מצמצמת את מספר ההקצאות לאחת, היא לא בהכרח הופכת את האלגוריתם ל"מהיר יותר" או "מקצה פחות זיכרון" מהקודם. הנקודה כאן היא שאם אנחנו צריכים מסלול מסודר מ- i עד j , תמיד נצטרך "להפוך" את הנתונים שאנו שואבים מהמטריצה R , ואין דרך לברוח ממנו.

אבל אם נוכל להציג נתונים בסדר הפוך, אז נוכל לעשות שימוש ב-LINQ ולהימנע מכל הקצאות מיותרות:

 public static IEnumerable<int> RebuildWithReverseYield( int[] routes, int sz, int i, int j) { yield return j; var z = routes[i * sz + j]; while (z != Constants.NO_EDGE) { yield return z; z = routes[i * sz + z]; } yield return i; }

יכולות להיות עוד גרסאות רבות של האופן שבו ניתן "לשנות" או "לשפר" את הקוד הזה. הרגע החשוב כאן הוא לזכור - לכל "שינוי" יש חסרונות מבחינת זיכרון או מחזורי מעבד.

אתם מוזמנים להתנסות! האפשרויות כמעט בלתי מוגבלות!

מַסְקָנָה

---

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

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

אני מקווה שנהנית מהקריאה, ולהתראות בפעם הבאה!