چگونه با الگوریتم فلوید-وارشال در سی شارپ «مسیرها» کوتاه‌ترین مسیرهای تمام جفت را پیدا کنیم

مقدمه

در پست قبلی نحوه حل مشکل کوتاهترین مسیر همه جفت را با استفاده از الگوریتم فلوید-وارشال دیدیم. ما همچنین چندین راه را برای بهبود عملکرد الگوریتم با استفاده از موازی سازی و برداری بررسی کردیم.

با این حال، اگر به نتایج الگوریتم فلوید-وارشال فکر کنید، به سرعت لحظه جالبی را متوجه خواهید شد - ما فواصل (مقادیر کوتاه ترین مسیرها) بین راس ها را در یک نمودار می دانیم اما "مسیرها" را نمی دانیم، به عنوان مثال، ما نمی دانیم چه رئوس در کوتاه ترین مسیر کمک می کند، و نمی توانیم این "مسیرها" را از نتایجی که داریم بازسازی کنیم.

در این پست از شما دعوت می کنم به من بپیوندید و الگوریتم فلوید-وارشال را گسترش دهید. این بار، ما می‌خواهیم مطمئن شویم که می‌توانیم مسافت را محاسبه کرده و «مسیر» را بازسازی کنیم.

کمی تئوری شناخته شده…

قبل از پرداختن به کدها و معیارها، بیایید تئوری نحوه عملکرد الگوریتم فلوید-وارشال را بازبینی کنیم.

در اینجا یک توضیح متنی از الگوریتم است:

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 خواهد بود.

ما دو مسیر پیدا کرده‌ایم: یک مسیر جدید ( 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 منطقی است.

همانطور که قبلاً انجام داده‌ایم، سلول‌های 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) وجود دارد. بنابراین، ما مسیرهای زیر را برای پردازش داریم:

این آخرین تکرار الگوریتم بود. تنها چیزی که باقی می‌ماند این است که سلول‌های 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 (در اینجا مستقیماً از k به j می‌رسیم).

این لحظه حیاتی است. زیرا دانستن رأسی که از آن آمده‌ایم به ما امکان می‌دهد با حرکت به عقب (مانند خرچنگ) از راس 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 است. طبق الگوریتم، این به این معنی است که مسیر از راس 3 به راس 4 می رود (نشان داده شده با رنگ آبی).

   
   

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 حاوی داده‌های مربوط به کوتاه‌ترین مسیرها است. نه بیشتر نه کمتر.

اکنون، ما با تئوری تمام شده ایم، زمان اجرا است.

پیاده سازی در سی شارپ

در پست قبلی ، علاوه بر پیاده‌سازی نسخه اصلی الگوریتم فلوید-وارشال، بهینه‌سازی‌های مختلفی را نیز ادغام کرده‌ایم: پشتیبانی از نمودارهای پراکنده، موازی‌سازی و بردارسازی، و در پایان، همه آنها را با هم ترکیب کردیم.

هیچ دلیلی برای تکرار همه اینها امروز وجود ندارد. با این حال، من می خواهم به شما نشان دهم که چگونه حافظه مسیر را در نسخه های اصلی و برداری شده (با پشتیبانی از نمودارهای پراکنده) الگوریتم ادغام کنید.

ادغام در الگوریتم اصلی

شاید باورش سخت باشد اما برای ادغام حفظ مسیر در نسخه اصلی الگوریتم ها، تنها کاری که باید انجام دهیم این است:

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; } } } } }

محک زدن

جمع آوری اطلاعات مسیر به اندازه کافی معقول به نظر می رسد زیرا... خوب چرا که نه؟ به خصوص زمانی که ادغام در الگوریتم های موجود بسیار آسان است. با این حال، بیایید ببینیم که ادغام آن به طور پیش فرض چقدر عملی است.

در اینجا دو مجموعه از معیارها وجود دارد: با و بدون (هر دو نسخه اصلی و برداری الگوریتم را اجرا می کنند). همه بنچمارک ها توسط BenchmarkDotNet v0.13.1 (.NET 6.0.4 x64) بر روی دستگاهی مجهز به پردازنده Intel Core i5-6200U CPU 2.30GHz (Skylake) و دارای ویندوز 10 اجرا شدند.

همه آزمایش‌ها بر روی مجموعه از پیش تعریف‌شده نمودارهای مورد استفاده در پست قبلی انجام شد: رأس‌های 300، 600، 1200، 2400 و 4800.

در زیر نتایج محک وجود دارد که روش‌های Baseline و BaselineWithRoutes با نسخه اصلی الگوریتم و روش‌های SpartialVectorOptimisations و SpartialVectorOptimisationsWithRoutes با نسخه برداری (با پشتیبانی از نمودارهای پراکنده) الگوریتم مطابقت دارند.

تفسیر نتایج معیار ساده نیست. اگر نگاه دقیق‌تری بیندازید، ترکیبی را می‌بینید که در واقع جمع‌آوری مسیر باعث می‌شود الگوریتم سریع‌تر یا بدون تأثیر قابل توجهی اجرا شود.

این بسیار گیج کننده به نظر می رسد (و اگر چنین است - من به شدت به شما توصیه می کنم که به این برنامه با دنیس باخوالوف و آندری آکینشین گوش دهید تا بهتر بفهمید چه چیزهای فریبنده ای می تواند بر اندازه گیری ها تأثیر بگذارد). بهترین برداشت من در اینجا این است که رفتار "گیج کننده" ناشی از عملکرد عالی حافظه نهان CPU است (زیرا نمودارها به اندازه کافی بزرگ نیستند که کش ها را اشباع کنند). تا حدی، این نظریه مبتنی بر نمونه " پررنگ " است که در آن می توانیم تخریب قابل توجهی را در بزرگترین نمودار مشاهده کنیم. با این حال، من آن را تأیید نکردم.

به طور کلی، بنچمارک نشان می‌دهد که اگر در مورد سناریوهای بسیار با کارایی بالا و نمودارهای بزرگ صحبت نمی‌کنیم، خوب است که حافظه مسیر را به صورت پیش‌فرض در هر دو الگوریتم ادغام کنیم (اما به خاطر داشته باشید، مصرف حافظه را دوبرابر می‌کند، زیرا باید به جای یکی دو ماتریس W و R را اختصاص دهید).

تنها چیزی که باقی می ماند اجرای الگوریتم بازسازی مسیر است.

پیاده سازی الگوریتم بازسازی مسیر

پیاده سازی الگوریتم های بازسازی مسیر در سی شارپ ساده است و تقریباً به طور کامل شبه کد نشان داده شده قبلی را منعکس می کند (ما 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; }

می‌تواند انواع بیشتری از نحوه «تغییر» یا «بهبود» این کد وجود داشته باشد. لحظه مهم در اینجا این است که به یاد داشته باشید - هر "تغییر" از نظر حافظه یا چرخه های CPU دارای جنبه های منفی است.

با خیال راحت آزمایش کنید! امکانات تقریبا نامحدود است!

نتیجه گیری

در این پست، تئوری الگوریتم فلوید-وارشال را عمیقاً بررسی کردیم و آن را با امکان به خاطر سپردن مسیرهای کوتاه‌ترین مسیرها گسترش دادیم. سپس پیاده‌سازی‌های سی شارپ (اصلی و بردار) را از پست قبلی به‌روزرسانی کردیم. در پایان، ما چند نسخه از الگوریتم را برای بازسازی "مسیرها" پیاده سازی کرده ایم.

ما بسیار تکرار کرده ایم، اما در عین حال، امیدوارم چیز جدید و جالبی در این یکی پیدا کرده باشید. این پایان مشکل کوتاهترین مسیرهای همه جفت نیست. این تازه شروع کار است.

امیدوارم از خواندن لذت برده باشید و دفعه بعد شما را ببینم!