вступ У ми бачили, як розв’язати задачу найкоротшого шляху з усіма парами за допомогою . Ми також дослідили кілька способів покращити продуктивність алгоритму за допомогою паралелізму та векторизації. попередній публікації алгоритму Флойда-Воршалла Однак, якщо ви подумаєте про результати алгоритму Флойда-Воршалла, ви швидко зрозумієте цікавий момент – ми знаємо відстані (значення найкоротших шляхів) між вершинами в графі, але ми не знаємо «маршрутів», тобто ми не знаємо, які вершини сприяють кожному найкоротшому шляху, і ми не можемо перебудувати ці «маршрути» за отриманими результатами. У цій публікації я запрошую вас приєднатися до мене та розширити алгоритм Флойда-Воршалла. Цього разу ми перевіримо, чи зможемо розрахувати відстань і перебудувати «маршрут». Трохи відомої теорії… Перш ніж заглибитися в код і тести, давайте переглянемо теорію того, як працює алгоритм Флойда-Воршалла. Ось текстовий опис алгоритму: Ми починаємо з представлення графа ( ) розміром як матриці ( ) розміром , де кожна комірка містить вагу ребра від вершини до вершини (див. Малюнок 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 Я використовую формат «від» ⭢ «до» :«відстань» із щоб записувати шляхи. попередньої публікації, – Примітка автора Ми також знаємо, що немає ребер, що ведуть до вершини , тому виконання алгоритму для не має сенсу. Також очевидно, що існує єдине ребро ( ), що веде від вершини до вершини , що також робить виконання всіх ( «звідки» тут) абсолютно безглуздим, а оскільки вершина має ребра з і , також немає сенсу виконувати алгоритми для будь-якого , яке не є або ( тут «до»). 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 – Примітка автора Бенчмаркінг Збір інформації про маршрут здається досить розумним, тому що… чому б і ні? Особливо, коли його так легко інтегрувати в існуючі алгоритми. Однак давайте подивимося, наскільки практично це інтегрувати його за замовчуванням. Ось два набори тестів: із і без (обидва виконують оригінальну та векторизовану версії алгоритму). Усі тести були виконані за допомогою v0.13.1 (.NET 6.0.4 x64) на машині, оснащеній процесором Intel Core i5-6200U CPU 2,30 ГГц (Skylake) і під керуванням Windows 10. BenchmarkDotNet Усі експерименти проводилися на попередньо визначеному наборі графів, які використовувалися в : 300, 600, 1200, 2400 і 4800 вершин. попередній публікації Вихідний код і експериментальні графіки доступні в репозиторії на GitHub. Експериментальні графіки можна знайти в каталозі . файлі Data/Sparse-Graphs.zip Усі контрольні тести в цьому дописі реалізовано у APSP02.cs . Нижче наведено результати тестування, де методи і відповідають оригінальній версії алгоритму, а методи і відповідають векторизованій (з підтримкою розріджених графіків) версії алгоритму. Baseline BaselineWithRoutes SpartialVectorOptimisations SpartialVectorOptimisationsWithRoutes метод Розмір Середнє (мс) Помилка (мс) Стандартне відхилення (мс) Базовий рівень 300 40,233 0,0572 0,0477 BaselineWithRoutes 300 40,349 0,1284 0,1201 PartialVectorOptimizations 300 4,472 0,0168 0,0140 PartialVectorOptimizationsWithRoutes 300 4,517 0,0218 0,0193 Базовий рівень 600 324,637 5,6161 4,6897 BaselineWithRoutes 600 321.173 1,4339 1,2711 PartialVectorOptimizations 600 32.133 0,2151 0,1679 PartialVectorOptimizationsWithRoutes 600 34,646 0,1286 0,1073 Базовий рівень 1200 2656,024 6,9640 5,8153 BaselineWithRoutes 1200 2657,883 8,8814 7,4164 PartialVectorOptimizations 1200 361,435 2,5877 2,2940 PartialVectorOptimizationsWithRoutes 1200 381,625 3,6975 3,2777 Базовий рівень 2400 21 059,519 38,2291 33,8891 BaselineWithRoutes 2400 20 954,852 56,4719 50,0609 PartialVectorOptimizations 2400 3 029,488 12.1528 11,3677 PartialVectorOptimizationsWithRoutes 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 PartialVectorOptimizations 4800 21 882,379 200,2820 177,5448 PartialVectorOptimizationsWithRoutes 4800 21 004,612 79,8752 70,8073 Результати порівняльного аналізу нелегко інтерпретувати. Якщо ви придивитесь уважніше, то знайдете комбінацію, коли збирання маршрутів фактично пришвидшило алгоритм або взагалі без будь-якого суттєвого ефекту. Виглядає це дуже заплутано (і якщо так – настійно раджу послухати цю з і щоб краще зрозуміти, які хитрощі можуть впливати на вимірювання). Моя найкраща думка полягає в тому, що «заплутує» поведінка спричинена високою продуктивністю кешу ЦП (оскільки графіки недостатньо великі, щоб наситити кеші). Частково ця теорія базується на « » зразку, де ми бачимо значне погіршення на найбільшому графіку. Однак я не перевіряв це. передачу Денисом Бахваловим Андрієм Акіншиним, жирному Загалом тест показує, що якщо ми не говоримо про надзвичайно високопродуктивні сценарії та величезні графіки, цілком нормально інтегрувати запам’ятовування маршруту в обидва алгоритми за замовчуванням (але майте на увазі, що це подвоїть споживання пам’яті, оскільки нам потрібно виділити дві матриці і замість однієї). 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# (оригінальні та векторизовані) з . Зрештою, ми реалізували кілька версій алгоритму для перебудови «маршрутів». попереднього допису Ми багато повторили, але в той же час, я сподіваюся, що ви знайшли в цьому щось нове і цікаве. Це ще не кінець проблеми найкоротших шляхів усіх пар. Це лише початок. Сподіваюся, вам сподобалося прочитати, і до зустрічі наступного разу!
