Mawaniro e "Nzira" dzeVese-Pairi Pfupi Nzira Neiyo Floyd-Warshall Algorithm muC#.

Nhanganyaya

Muchinyorwa chakapfuura , takaona magadzirisiro ezvese-pairi pfupi nzira dambudziko uchishandisa iyo Floyd-Warshall algorithm . Isu takaongororawo nzira dzinoverengeka dzekuvandudza kuita kwealgorithm nekushandisa parallelism uye vectorization.

Nekudaro, kana iwe ukafunga nezve mhedzisiro yeiyo Floyd-Warshall algorithm, iwe unokurumidza kuona iyo inonakidza nguva - isu tinoziva madaro (tsika dzenzira pfupi) pakati pema vertex mugirafu asi isu hatizive "nzira" kureva, hatizive kuti ma vertex api anobatsira munzira imwe neimwe pfupi, uye hatigone kuvaka patsva idzi “nzira” kubva mumibairo yatinayo.

Mune ino post, ini ndinokukoka iwe kuti ubatane neni uye kuwedzera iyo Floyd-Warshall algorithm. Panguva ino, tichava nechokwadi chekuti tinogona kuverenga chinhambwe uye kuvakazve "nzira".

Chidimbu cheIchi Chinozivikanwa Theory…

Tisati tanyura mukodhi uye mabhenji, ngationgororei dzidziso yekuti Floyd-Warshall algorithm inoshanda sei.

Heino tsananguro yezvinyorwa zve algorithm:

1. Tinotanga nekumiririra girafu ( G ) yehukuru N sematrix ( W ) yehukuru N x N apo sero rega rega W[i,j] rine huremu hwemupendero kubva kune vertex i kusvika kune vertex j (ona Mufananidzo 1). Muzviitiko kana pasina mupendero pakati pemavheti, sero rinoiswa kune yakakosha NO_EDGE kukosha (inoratidzwa semaseru erima muMufananidzo 1).

   
   

2. Kubva zvino zvichienda mberi, tinoti – W[i,j] ine chinhambwe pakati pemavheti i na j .

   
   

3. Tevere, tinotora vertex k todzokorora nepamaviri ese ema vertex W[i,j] tichitarisa kana nhambwe i ⭢ k ⭢ j idiki pane nhambwe inozivikanwa parizvino pakati i na j .

   
   

4. Hukoshi hudiki hwakachengetwa muW W[i,j] uye nhanho #3 inodzokororwa kune inotevera k kusvika mavheti ese G ashandiswa se k .

Heino pseudo-code:

 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

Kana yaitwa, sero yega yega W[i,j] yematrix W ingave ine chinhambwe chenzira ipfupi pakati pe vertex i na j kana NO_EDGE kukosha, kana pasina nzira pakati pawo.

Sezvandambotaura pakutanga - kungova neruzivo urwu chete kunoita kuti zvisaite kugadzirazve nzira dziri pakati pemavheti aya. Saka… chii chatinofanira kuita kuti tikwanise kuvaka patsva nzira idzi?

Zvakanaka ... zvingaite sezviri pachena asi ... tinoda kuunganidza mamwe data!

… Chidiki chedzidziso imwechete asi Kubva kune Yakasiyana Engiro

Hwaro hweiyo Floyd-Warshall algorithm inzvimbo yezvinhambwe inozivikanwa W[i,j] ine chinhambwe chenzira ingangove itsva kubva kuna i kuenda j kuburikidza nepakati vertex k .

Ini ndinokwevera kutarisisa kune iyi tsanangudzo nekuti ndiyo kiyi yekuti tingachengetedza sei ruzivo rwenzira. Ngatitorei yapfuura girafu ye5 vertexes (ona Mufananidzo 2) uye tiite iyo Floyd-Warshall algorithm pairi.

Pakutanga, tinoziva nezvese girafu mipendero, inotipa nzira dzinotevera: 0 ⭢ 1 :2 , 0 ⭢ 4 :10 , 1 ⭢ 3 :1 , 2 ⭢ 4 :1 , 3 ⭢ 2 :1 uye 3 ⭢ 4 :3 .

Isu tinoziva zvakare kuti hapana mipendero inotungamira kune vertex 0 , saka kuita algorithm ye k = 0 haina musoro. Zviri pachena zvakare, kune mupendero mumwechete ( 0 ⭢ 1 ) unotungamira kubva ku vertex 0 kuenda ku vertex 1 , izvo zvinoitawo kuurayiwa kwezvose i != 0 (iyo i "kubva" pano) hazvina zvazvinoreva uye nekuti vertex 1 ine mipendero na 2 na 4 , hazvina musorowo kuita algorithms kune chero j isiri 2 kana 4 (iyo j ndi "ku" pano).

Ndicho chikonzero danho redu rekutanga richava rekuita algorithm ye k = 1 , i = 0 uye j = 2,4 .

Tawana nzira mbiri: nzira itsva ( 0 ⭢ 1 ⭢ 2 ) uye nzira yekudimbudzira ( 0 ⭢ 1 ⭢ 4 ). Ose ari maviri anopinda nepakati 1 . Kana tikasachengeta ruzivo urwu (iyo yatinayo kusvika 2 4 kusvika 1 ) pane imwe nzvimbo izvozvi, inorasika zvachose (uye izvo zvakapesana nezvatinoda).

Saka tinofanira kuitei? Tichavandudza matrix W nemhando itsva (ona Mufananidzo 3a) uyewo chengetedza kukosha k (iyo k = 1 ) mumasero R[0,2] uye R[0,4] yematrix itsva R yehukuru hwakafanana. sematrix W asi yakatanga NO_EDGE kukosha (ona Mufananidzo 3b).

Parizvino, usatarise kuti chii chaizvo matrix R Ngatirambei tichienda uye tiite algorithm yeinotevera k = 2 .

Pano, tichaita kuongorora kwakafanana (kunzwisisa kuti zvipi zvakasanganiswa zvine musoro kuti tiite) sezvatakaita k = 1, asi panguva ino, tichashandisa matrix W pane girafu G Tarisa matrix W , kunyanya mukoromo #2 uye mutsara #2 (Mufananidzo 4).

Pano unogona kuona, kune nzira mbiri dzekuenda kuvertex 2 kubva kuvertex 0 uye kubva kuvertex 1 (column #2), uye nzira mbiri kubva kune 2 kuenda kuvertex 3 uye kune vertex 4 (mutsara #2). Kuziva izvozvo, zvine musoro kuita algorithm chete kusanganisa k = 2 , i = 0,1 uye j = 3,4 .

Sezvatatoita kare, tiri kugadzirisa masero W[0,3] , W[0,4] , W[1,3] , W[1,4] ane madaro matsva uye masero R[0,3] , R[0,4] , R[1,3] uye R[1,4] ine k = 2 (ona Mufananidzo 5).

Pane k = 3 chete yasara kuti igadziriswe (nekuti hapana mipendero inotungamira kubva kune vertex 4 kune chero imwe vertex mugirafu).

Zvakare, ngatitarisei matrix W (Mufananidzo 6).

Maererano nematrix W , kune nzira nhatu dzekuenda kune vertex 3 kubva kune vertexes 0 , 1 uye 2 (column #3), uye pane imwe nzira kubva ku vertex 3 kusvika kune vertex 4 (mutsara #3). Naizvozvo, isu tine nzira dzinotevera dzekugadzirisa:

Iyi yaive yekupedzisira iteration yealgorithm. Chasara kugadzirisa maseru W[0,4] , W[1,4] , W[2,4] ane madaro matsva uye kuseta maseru R[0,4] , R[1,4] , R[2,4] kusvika 3 .

Hezvino izvo zvatinazvo pamagumo egorgorithm (Mufananidzo 7).

Sezvatinoziva kubva kune yapfuura positi , matrix W ikozvino ine mapeya ese enzira mapfupi mugirafu G Asi chii chakachengetwa mukati mematrix R ?

Kuuya kumba

Pese patakawana nzira ipfupi pfupi, taive tichivandudza sero rinoenderana rematrix R nehuwandu hwazvino hwe k . Nepo pekutanga, chiitiko ichi chingaite sechisinganzwisisike chine chirevo chakareruka - isu taichengeta vertex, kubva kwatakasvika kwainosvika vertex: i ⭢ k ⭢ j (pano tave kusvika j zvakananga kubva k ).

Iyi nguva yakakosha. Nekuti kuziva vertex yatakabva kunotibvumira kuvaka patsva nzira nekudzokera kumashure (selobster) kubva kuvertex j (iyo "kusvika") kuenda kuvertex i ("kubva").

Heino tsananguro yezvinyorwa zve algorithm yekuvakazve nzira kubva ku i kuenda j :

1. Gadzirira isina chinhu dynamic array X .
2. Tanga nekuverenga kukosha z kubva muchitokisi R[i,j] .
3. Kana z ari NO_EDGE , ipapo nzira kubva kuna i kuenda j inowanikwa uye tinofanira kuenderera kunhanho #7.
4. Gadzirira z kune inoshanduka-shanduka X .
5. Verenga kukosha kwesero R[i,z] mu z .
6. Dzokorora nhanho #3, #4, uye #5 kusvika mamiriro ekubuda mu#3 asvikwa.
7. Gadzirira i kuna X.
8. Wedzera j kuna X .
9. Ikozvino dynamic array X ine nzira kubva i kuenda j .

Mune pseudo-code, inotaridzika zvakanyanya nyore:

 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

Ngatiiedzei pagirafu G yedu uye tivakezve nzira kubva kune vertex 0 kuenda kuvertex 4 (ona Mufananidzo 8).

Heino tsananguro yezvinyorwa zvemufananidzo uri pamusoro:

1. Tinotanga nekuverenga kukosha kubva R[0,4] , izvo zvinoguma 3 . Zvinoenderana nealgorithm, izvi zvinoreva kuti nzira inoenda kune vertex 4 kubva vertex 3 (inoratidzwa muBLUE).

   
   

2. Nekuti kukosha kweR R[0,4] hakusi NO_EDGE , tinoenderera mberi nekuverenga kukosha kweR R[0,3] izvo zvinoguma 2 (inoratidzwa muGREEN).

   
   

3. Zvekare, nekuti kukosha kweR R[0,3] hakusi NO_EDGE , tinoenderera mberi nekuverenga kukosha kweR R[0,2] inoguma 1 (inoratidzwa muRED).

   
   

4. Pakupedzisira, tinoverenga kukosha kweR R[0,1] , izvo zvinoguma NO_EDGE kukosha, zvinoreva, hapasisina vertexes kunze 0 uye 4 iyo inobatsira munzira. Nokudaro, nzira inoguma ndeiyi: 0 ⭢ 1 ⭢ 2 ⭢ 3 ⭢ 4 iyo kana iwe ukatarisa girafu inonyatsoenderana nenzira ipfupi kubva kuvertex 0 kusvika kune vertex 4 .

Muverengi anofunga angabvunza kuti:

Mubvunzo wakanaka kwazvo. Isu tine chokwadi nekuti isu tinovandudza matrix R nehutsva hutsva patinogadzirisa iyo pfupi nzira kukosha mune matrix W Saka mukupedzisira, mutsara wega wega we matrix R une data rine chekuita nemakwara mapfupi. Kwete, kwete zvishoma.

Zvino, isu tapedza nedzidziso, inguva yekushandisa.

Kuitwa muC#

Mune iyo yapfuura positi , kunze kwekuita iyo yekutanga vhezheni yeFloyd-Warshall algorithm, isu takabatanidzawo akasiyana optimizations: rutsigiro rwemagirafu mashoma, parallelism, uye vectorization, uye pakupedzisira, isu takabatanidza ese.

Hapana chikonzero chekudzokorora zvese izvi nhasi. Nekudaro, ini ndoda kukuratidza nzira yekubatanidza nzira yekuyeuka mune yepakutanga uye vectorized (nerutsigiro rwe sparse magirafu) shanduro yegorgorithm.

Kubatanidzwa Mukutanga Algorithm

Zvingave zvakaoma kutenda asi kubatanidza nzira yemusoro mushanduro yekutanga yealgorithms, zvese zvatinofanira kuita ndezvekuti:

1. Wedzera siginicha yebasa kuti ubatanidze R matrix separamita yakaparadzana - int[] routes .

   
   

2. Sevha k routes pese panochinjwa nzira ipfupi (mitsara: 2 ne14).

Ndizvozvo. Mutsetse mumwe nehafu wekodhi:

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

Kubatanidzwa muVectorized Algorithm

Kubatanidzwa mune vectorized (nerutsigiro rwemagirafu mashoma) vhezheni inotora imwe nhamburiko kuti ipedze, zvisinei, nhanho dzepfungwa dzakafanana:

1. Wedzera siginicha yebasa kuti ubatanidze R matrix separamita yakaparadzana - int[] routes .

   
   

2. Pane imwe neimwe iteration, tanga vector itsva ye k values (mutsara: 6).

   
   

3. Chengetedza k values vector routes pese painoshandurwa nzira pfupi (mitsetse: 31-32).

   
   

4. Gadziridza iyo isiri-vectorized chikamu chegorgorithm nenzira imwechete sezvatakagadzirisa iyo yekutanga algorithm (mutsara: 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

Kuunganidza ruzivo rwemakwara kunoita sekwakakwana nekuti… zvakanaka nei? Kunyanya kana zviri nyore kubatanidza mune iripo algorithms. Nekudaro, ngationei kuti inoshanda sei kuibatanidza nekukasira.

Heano maviri seti emabhenji: ane uye pasina (ese ari maviri epa epakutanga uye vectorized shanduro yegorgorithm). Mabhenjimaki ese akaitwa neBenchmarkDotNet v0.13.1 (.NET 6.0.4 x64) pamuchina une Intel Core i5-6200U CPU 2.30GHz (Skylake) processor uye inoshanda Windows 10.

Zvese zviedzo zvakaitwa pane yakafanotsanangurwa seti yemagirafu akashandiswa mune yapfuura positi : 300, 600, 1200, 2400, uye 4800 vertexes.

Pazasi pane mibairo yekumisikidza apo nzira Baseline BaselineWithRoutes dzinoenderana neshanduro yekutanga yegorgorithm uye SpartialVectorOptimisations uye SpartialVectorOptimisationsWithRoutes nzira dzinoenderana nevectorized (nerutsigiro rwemagirafu mashoma) yegorgorithm.

Benchmark zvawanikwa hazvisi nyore kududzira. Kana iwe ukanyatsotarisisa, iwe unowana musanganiswa apo nzira yekuunganidza yakanyatsoita kuti algorithm imhanye nekukurumidza kana pasina yakakosha mhedzisiro.

Izvi zvinotaridzika zvakanyanya kuvhiringidza (uye kana zviri izvo - ndinokurayira zvakasimba kuti uteerere kuratidzwa uku naDenis Bakhvalov naAndrey Akinshin kuti unzwisise zviri nani zvinhu zvinonyengera zvinogona kukanganisa zviyero). Chandinonyanya kutora pano ndechekuti "kuvhiringa" maitiro anokonzerwa nehukuru hweCPU cache kuita (nekuti magirafu haana kukura zvakakwana kugutsa cache). Zvishoma, dzidziso iyi yakavakirwa pa " bold " sampuli apo isu tinogona kuona kuderera kukuru pane yakakura girafu. Zvisinei, handina kuzviongorora.

Kazhinji, mucherechedzo unoratidza kuti kana tisiri kutaura nezve yakanyanyisa-inoshanda mamiriro uye magirafu mahombe, zvakanaka kubatanidza nzira yekurangarira mune ese maalgorithms nekukasira (asi ramba uchifunga, ichapeta ndangariro kushandiswa nekuti isu tinoda govera matrices maviri W uye R pane imwe).

Chinhu chega chasara kuita kweiyo nzira yekuvakazve algorithm.

Kuitwa kweRoute Rebuild Algorithm

Kuitwa kwenzira yekuvakazve maalgorithms muC# kwakatwasuka uye kunenge kwakanyatso kuratidza yakamboratidzwa pseudo-code (tinoshandisa LinkedList<T> kumiririra dynamic array):

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

Iyo algorithm iri pamusoro haina kukwana uye zvechokwadi inogona kuvandudzwa. Iko kunatsiridza kuri nyore kwatinogona kuita ndeye kugovera dhizaini yehukuru hwe sz uye kuizadza mune reverse order:

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

Kunyange iyi "optimization" ichidzikisa huwandu hwekugoverwa kune imwe, hazviiti kuti algorithm "ikurumidze" kana "kugovera ndangariro shoma" pane yapfuura. Pfungwa iri pano ndeyokuti kana tichida kuva negwara rakarayirwa kubva i kusvika j , isu nguva dzose tichafanira "kudzosera" data yatinotora kubva kumatrix R , uye hapana nzira yekupukunyuka nayo.

Asi kana tikakwanisa kupa data mune reverse order, saka tinogona kushandisa LINQ uye kudzivirira chero kugoverwa kusingakoshi:

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

Panogona kuve nemimwe misiyano yakawanda yekuti kodhi iyi inogona "kushandurwa" kana "kuvandudzwa." Nguva yakakosha pano ndeyekuyeuka - chero "shanduko" ine yakaderera maererano nendangariro kana CPU kutenderera.

Inzwa wakasununguka kuedza! Mikana inenge isingagumi!

Mhedziso

Mune ino positi, takave nekunyura kwakadzama mune dzidziso kuseri kweiyo Floyd-Warshall algorithm uye takaiwedzera nemukana wekuyeuka mapfupi nzira "makwara." Ipapo takagadziridza C # maitirwo (yekutanga uye vectorized) kubva kune yapfuura positi . Pakupedzisira, takashandisa shanduro shomanana dzegorgorithm kuti tivakezve "nzira".

Takadzokorora kakawanda, asi panguva imwe chete, ndinovimba wawana chimwe chinhu chitsva uye chinonakidza mune ino. Uku hakusi kupera kwedambudziko renzira pfupi-peiri. Aya angori mavambo.

Ndinovimba wakanakidzwa nekuverenga, uye tozoonana nguva inotevera!