מָבוֹא , ראינו כיצד לפתור את בעיית הנתיב הקצר ביותר של כל הזוגות באמצעות . כמו כן, בדקנו מספר דרכים לשפר את ביצועי האלגוריתם על ידי שימוש בהקבלה ובווקטוריזציה. בפוסט הקודם האלגוריתם של פלויד-ורשל עם זאת, אם תחשבו על תוצאות האלגוריתם של פלויד-ורשל, תבינו במהירות את הרגע המעניין - אנחנו יודעים את המרחקים (ערכי הנתיבים הקצרים ביותר) בין קודקודים בגרף אבל אנחנו לא יודעים את ה"מסלולים" כלומר, אנחנו לא יודעים אילו קודקודים תורמים לכל נתיב הקצר ביותר, ואנחנו לא יכולים לבנות מחדש את ה"מסלולים" הללו מהתוצאות שיש לנו. בפוסט הזה, אני מזמין אתכם להצטרף אלי ולהרחיב את האלגוריתם של פלויד-ורשל. הפעם, אנחנו הולכים לוודא שנוכל לחשב את המרחק ולבנות מחדש את "המסלול". קצת תיאוריה ידועה... לפני שנצלול לתוך קוד ואמות מידה, בואו נשנה תיאוריה של איך האלגוריתם של פלויד-ורשל עובד. להלן תיאור טקסטואלי של האלגוריתם: נתחיל בייצוג גרף ( ) בגודל כמטריצה ( ) בגודל כאשר כל תא מכיל את המשקל של קצה מקודקוד לקודקוד (ראה תמונה 1). במקרים בהם אין קצה בין קודקודים, התא מוגדר לערך מיוחד (מוצג כתאים כהים בתמונה 1). G N W N x N W[i,j] i j NO_EDGE מעתה נאמר – מכיל מרחק בין קודקודים ו- . W[i,j] i j לאחר מכן, ניקח קודקוד ונחזור על כל זוגות הקודקודים ובודקים אם המרחק קטן מהמרחק הידוע כיום בין ל- . k W[i,j] i ⭢ k ⭢ j i j הערך הקטן ביותר מאוחסן ב- ושלב #3 חוזר על עצמו עבור ה- הבא עד שכל הקודקודים של שימשו כ- . W[i,j] 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 אני משתמש בפורמט "מ" ⭢ "ל" :"מרחק" כדי לרשום נתיבים. מהפוסט הקודם - הערת המחבר אנחנו גם יודעים שאין קצוות המובילים לקודקוד , ולכן ביצוע אלגוריתם עבור אינו הגיוני. זה גם ברור, יש קצה בודד ( ) המוביל מקודקוד לקודקוד , מה שהופך גם את הביצוע של כל (ה- הוא "מכאן") די חסר משמעות ומכיוון שקודקוד יש קצוות עם ו , זה גם לא הגיוני לבצע אלגוריתמים עבור כל שהוא לא או (ה- הוא "to" כאן). 0 k = 0 0 ⭢ 1 0 1 i != 0 i 1 2 4 j 2 4 j לכן הצעד הראשון שלנו יהיה לבצע אלגוריתם עבור , ו- . 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 אז מה עלינו לעשות? נעדכן את המטריצה בערכים חדשים (ראה תמונה 3a) וגם נאחסן את הערך של (שהוא ) בתאים ו- של מטריצה חדשה באותו גודל כמטריצה אך אתחול עם ערכי (ראה תמונה 3b). W k k = 1 R[0,2] R[0,4] R W NO_EDGE כרגע, אל תתמקד במטריצה בדיוק. בואו פשוט נמשיך ונבצע את האלגוריתם עבור הבא. R k = 2 כאן, נעשה את אותו ניתוח (כדי להבין אילו שילובים הגיוני לבצע) כפי שעשינו עבור אבל הפעם, נשתמש במטריצה במקום גרף . הסתכלו על המטריצה , במיוחד בעמודה מס' 2 ובשורה מס' 2 (תמונה 4). k = 1, W G W כאן אתה יכול לראות, ישנם שני נתיבים לקודקוד מקודקוד ומקודקוד (עמודה מס' 2), ושני נתיבים מקודקוד לקודקוד ולקודקוד (שורה מס' 2). לדעת זאת, הגיוני לבצע את האלגוריתם רק עבור שילובים של , ו- . 2 0 1 2 3 4 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) כפי שכבר עשינו בעבר, אנו מעדכנים את התאים , , , עם מרחקים חדשים ותאים , , ו- עם (ראה תמונה 5). 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 נותרו רק לעיבוד (מכיוון שאין קצוות המובילים מקודקוד לכל קודקוד אחר בגרף). k = 3 4 שוב, בואו נסתכל על המטריצה (תמונה 6). W לפי המטריצה , ישנם שלושה נתיבים לקודקוד מקודקודים , ו (עמודה מס' 3), ויש נתיב אחד מקודקוד לקודקוד (שורה מס' 3). לכן, יש לנו את הנתיבים הבאים לעיבוד: W 3 0 1 2 3 4 שָׁלָב נָתִיב הֶעָרָה 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 הכן מערך דינמי ריק X התחל בקריאת ערך מהתא . z R[i,j] אם הוא , אזי נמצא המסלול מ- ל- ועלינו להמשיך לשלב #7. z NO_EDGE i j הוסף למערך דינמי . z X קרא את הערך של התא לתוך . R[i,z] z חזור על שלבים #3, #4 ו- #5 עד שתגיע למצב היציאה ב- #3. הוסף ל-X. i הוסף ל- j X כעת המערך הדינמי מכיל את המסלול מ- ל- . 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 בואו ננסה את זה על הגרף שלנו ונבנה מחדש מסלול מקודקוד לקודקוד (ראה תמונה 8). G 0 4 להלן תיאור טקסטואלי של האיור לעיל: נתחיל בקריאת הערך מ- , שמביא ל . לפי האלגוריתם, זה אומר שהמסלול עובר לקודקוד מקודקוד (מוצג בכחול). R[0,4] 3 4 3 מכיוון שהערך של אינו , אנו ממשיכים וקוראים את הערך של שמביא ל (מוצג בירוק). R[0,4] NO_EDGE R[0,3] 2 שוב, מכיוון שהערך של אינו , אנו ממשיכים וקוראים את הערך של שמביא ל (מוצג באדום). R[0,3] NO_EDGE R[0,2] 1 לבסוף, אנו קוראים ערך של , שמביא לערך , כלומר, אין יותר קודקודים מלבד ו שתורמים למסלול. לכן, המסלול המתקבל הוא: שאם מסתכלים על הגרף אכן מתאים לנתיב הקצר ביותר מקודקוד לקודקוד . R[0,1] NO_EDGE 0 4 0 ⭢ 1 ⭢ 2 ⭢ 3 ⭢ 4 0 4 קורא מתחשב עשוי לשאול: כיצד נוכל להיות בטוחים שכל הנתונים שאנו קוראים ממטריצה שייכים לאותו נתיב? R - קורא מתחשב זו שאלה טובה מאוד. אנו בטוחים כי אנו מעדכנים את המטריצה בערך חדש כאשר אנו מעדכנים את ערך הנתיב הקצר ביותר במטריצה אז בסופו של דבר, כל שורה של מטריצה מכילה נתונים הקשורים לנתיבים הקצרים ביותר. לא יותר, לא פחות. R W R עכשיו, סיימנו עם התיאוריה, הגיע זמן היישום. יישום ב-C# , מלבד הטמעת גרסה מקורית של אלגוריתם פלויד-ורשל, שילבנו גם אופטימיזציות שונות: תמיכה בגרפים דלילים, מקביליות ווקטוריזציה, ובסופו של דבר, גם שילבנו את כולם. בפוסט הקודם אין סיבה לחזור על כל זה היום. עם זאת, ברצוני להראות לכם כיצד לשלב שינון מסלול בגרסאות מקוריות ווקטוריות (עם תמיכה בגרפים דלילים) של האלגוריתם. אינטגרציה באלגוריתם מקורי אולי קשה להאמין אבל כדי לשלב שינון מסלול בגרסה המקורית של האלגוריתמים, כל שעלינו לעשות הוא: הרחב את חתימת הפונקציה כך שתכלול מטריצת כפרמטר נפרד - . R int[] routes שמור k בכל פעם שהנתיב הקצר ביותר משתנה (שורות: 2 ו-14). routes זהו זה. רק שורה וחצי של קוד: 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; } } } } } אינטגרציה באלגוריתם וקטוריזי אינטגרציה בגרסה וקטורית (עם תמיכה בגרפים דלילים) דורשת קצת יותר מאמץ כדי להשלים, עם זאת, השלבים הרעיוניים זהים: הרחב את חתימת הפונקציה כך שתכלול מטריצת כפרמטר נפרד - . R int[] routes בכל איטרציה, אתחול וקטור חדש של ערכים (שורה: 6). k שמור וקטור ערכי בכל פעם שהנתיב הקצר ביותר משתנה (שורות: 31-32). k routes עדכן חלק לא מוקטור של האלגוריתם באותו אופן שבו עדכנו את האלגוריתם המקורי (שורה: 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; } } } } } תזכורת קטנה – פעולת מחזירה וקטור חדש שבו הערכים שווים לקטן מבין שני הערכים התואמים של וקטורי קלט, כלומר, אם הערך של וקטור שווה ל , אז הפעולה בוחרת ערך מתוך , אחרת, הוא בוחר ערך מתוך . Vector.ConditionalSelect lt_vec -1 ij_vec k_vec - הערת המחבר Benchmarking איסוף מידע על המסלול נראה הגיוני מספיק כי... נו למה לא? במיוחד כשכל כך קל להשתלב באלגוריתמים קיימים. עם זאת, בואו נראה כמה מעשי זה לשלב אותו כברירת מחדל. הנה שתי קבוצות של אמות מידה: עם ובלי (שניהם מבצעים גרסאות מקוריות וגם גרסאות וקטוריות של האלגוריתם). כל ההשוואות בוצעו על ידי v0.13.1 (.NET 6.0.4 x64) על מכונה המצוידת במעבד Intel Core i5-6200U CPU 2.30GHz (Skylake) ופועלת Windows 10. BenchmarkDotNet כל הניסויים בוצעו על קבוצת הגרפים שהוגדרה מראש ששימשה : 300, 600, 1200, 2400 ו-4800 קודקודים. בפוסט הקודם קוד המקור והגרפים הניסיוניים זמינים במאגר ב-GitHub. ניתן למצוא את הגרפים הניסיוניים בספריית . Data/Sparse-Graphs.zip כל אמות המידה בפוסט זה מיושמות בקובץ APSP02.cs . להלן תוצאות ההשוואה שבהן שיטות ו- מתאימות לגרסה המקורית של האלגוריתם ושיטות ו- מתאימות לגירסה וקטורית (עם תמיכה בגרפים דלילים) של האלגוריתם. 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; } יכולות להיות עוד גרסאות רבות של האופן שבו ניתן "לשנות" או "לשפר" את הקוד הזה. הרגע החשוב כאן הוא לזכור - לכל "שינוי" יש חסרונות מבחינת זיכרון או מחזורי מעבד. אתם מוזמנים להתנסות! האפשרויות כמעט בלתי מוגבלות! אתה יכול למצוא יישומים של כל אלגוריתמי המסלול ב-GitHub בקובץ Routes.cs . מַסְקָנָה בפוסט הזה, עשינו צלילה עמוקה לתוך התיאוריה שמאחורי האלגוריתם של פלויד-ורשל והרחבנו אותה עם האפשרות לשנן את הנתיבים הקצרים ביותר. לאחר מכן עדכנו את יישומי C# (מקוריים וקטוריים) . בסופו של דבר, יישמנו כמה גרסאות של האלגוריתם כדי לבנות מחדש את ה"מסלולים". מהפוסט הקודם חזרנו על הרבה, אבל יחד עם זאת, אני מקווה שמצאת משהו חדש ומעניין בקטע הזה. זה לא הסוף של בעיית הנתיבים הקצרים ביותר של כל הזוגות. זו רק ההתחלה. אני מקווה שנהנית מהקריאה, ולהתראות בפעם הבאה!
