Nola aurkitu bikote guztietako bide laburrenen "ibilbideak" Floyd-Warshall algoritmoarekin C#-n

Sarrera

Aurreko mezuan , bikote guztien bide laburrenaren arazoa nola konpondu ikusi genuen Floyd-Warshall algoritmoa erabiliz. Paralelismoa eta bektorizazioa erabiliz algoritmoaren errendimendua hobetzeko hainbat modu ere aztertu ditugu.

Hala ere, Floyd-Warshall algoritmoaren emaitzetan pentsatzen baduzu, azkar konturatuko zara momentu interesgarriaz: badakigu grafiko batean erpinen arteko distantziak (bide laburrenen balioak), baina ez ditugu "ibilbideak" ezagutzen, alegia, ez dakigu zer erpinek laguntzen dioten bide laburrenari, eta ezin ditugu “ibilbide” horiek berreraiki ditugun emaitzetatik.

Post honetan, nirekin bat egitera eta Floyd-Warshall algoritmoa zabaltzera gonbidatzen zaitut. Oraingoan, distantzia kalkulatu eta "ibilbidea" berreraiki dezakegula ziurtatuko dugu.

Teoria pixka bat ezaguna...

Kode eta erreferentzia-puntuetan murgildu aurretik, berrikusi dezagun Floyd-Warshall algoritmoak nola funtzionatzen duen jakiteko.

Hona hemen algoritmoaren testu-deskribapena:

1. Hasteko, N tamainako ( G ) grafiko bat N x N tamainako ( W ) matrize gisa irudikatzen dugu, non W[i,j] gelaxka bakoitzak i erpinetik j erpinera arteko ertz baten pisua duen (ikus 1. Irudia). Erpinen artean ertzerik ez dagoen kasuetan, gelaxka NO_EDGE balio berezi batean ezartzen da (1. Irudian gelaxka ilun gisa agertzen da).

   
   

2. Hemendik aurrera, esaten dugu – W[i,j] i eta j erpinen arteko distantzia dauka.

   
   

3. Ondoren, k erpin bat hartu eta W[i,j] erpin-pare guztietan zehar itertuko dugu i ⭢ k ⭢ j distantzia gaur egun ezagutzen den i eta j arteko distantzia baino txikiagoa den egiaztatuz.

   
   

4. Baliorik txikiena W[i,j] -n gordetzen da eta #3 urratsa hurrengo k errepikatzen da G ren erpin guztiak k gisa erabili arte.

Hona hemen sasi-kodea:

 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

Bukatutakoan, W matrizearen W[i,j] gelaxka bakoitzak i eta j erpinen arteko bide laburreneko distantzia edo NO_EDGE balio bat dauka, haien artean biderik ez badago.

Hasieran aipatu dudan bezala, informazio hori bakarrik edukitzeak ezinezko egiten du erpin horien arteko ibilbideak berreraikitzea. Beraz... zer egin behar dugu ibilbide hauek berreraiki ahal izateko?

Beno... bistakoa dirudi baina... datu gehiago bildu behar ditugu!

… Teoria bereko pixka bat baina angelu ezberdin batetik

Floyd-Warshall algoritmoaren funtsa W[i,j] distantzia ezaguneko konpartimentu bat da, i -tik j bitarteko k bitarteko erpinetik zehar bide potentzial berriaren distantzia duena.

Hainbeste arreta arrastatzen dut xehetasun honetara, ibilbideen informazioa nola gorde dezakegunaren gakoa delako. Har dezagun 5 erpinen aurreko grafikoa (ikus 2. irudia) eta exekutatu bertan Floyd-Warshall algoritmoa.

Hasieran, grafikoen ertz guztiak ezagutzen ditugu, eta horrek bide hauek ematen dizkigu: 0 ⭢ 1 :2 , 0 ⭢ 4 :10 , 1 ⭢ 3 :1 , 2 ⭢ 4 :1 , 3 ⭢ 2 :1 eta 3 ⭢ 4 :3 .

Badakigu ere ez dagoela 0 erpinera daraman ertzerik, beraz k = 0 rako algoritmo bat exekutatzeak ez du zentzurik. Begi bistakoa da, gainera, ertz bakar bat dagoela ( 0 ⭢ 1 ) 0 erpinetik 1 erpinera doana, eta horrek i != 0 guztiaren exekuzioa ere nahiko zentzugabe bihurtzen du ( i -a hemengoa da) eta 1 erpinera delako. 2 eta 4 dituen ertzak ditu, ez du zentzurik 2 edo 4 ez den edozein j ren algoritmoak exekutatzeko ( j -a "to" da hemen).

Horregatik, gure lehen urratsa k = 1 , i = 0 eta j = 2,4 ren algoritmo bat exekutatzen aritzea izango da.

Bi bide aurkitu ditugu: bide berri bat ( 0 ⭢ 1 ⭢ 2 ) eta lasterbide bat ( 0 ⭢ 1 ⭢ 4 ). Biak 1 erpinetik pasatzen dira. Ez badugu informazio hori ( 2 eta 4 1 iritsi garela oraintxe bertan) nonbait gordetzen, betirako galduko da (eta hori nahi dugunaren guztiz kontrakoa da).

Beraz, zer egin behar dugu? W matrizea balio berriekin eguneratuko dugu (ikus 3a irudia) eta tamaina bereko R matrize berri baten R[0,2] eta R[0,4] gelaxketan k -ren balioa ere gordeko dugu ( k = 1 ). W matrize gisa baina NO_EDGE balioekin hasieratuta (ikus 3b irudia).

Oraintxe bertan, ez zentratu R matrizea zer den zehazki. Jarrai dezagun eta exekutatu hurrengo k = 2 algoritmoa.

Hemen, k = 1, baina oraingoan, G grafikoaren ordez W matrizea erabiliko dugu. Begiratu W matrizeari, batez ere 2. zutabean eta 2. errenkadan (4. irudia).

Hemen ikus dezakezu, 2 erpinerako bi bide daude 0 erpinetik eta 1 erpinetik (2. zutabea), eta bi bide daude 2 erpinetik 3 erpinera eta 4 erpinera (2. errenkada). Hori jakinda, zentzuzkoa da algoritmoa k = 2 , i = 0,1 eta j = 3,4 konbinazioetarako soilik exekutatzeko.

Lehenago egin dugun bezala, W[0,3] , W[0,4] , W[1,3] , W[1,4] gelaxkak eta R[0,3] gelaxkekin eguneratzen ari gara. R[0,4] , R[1,3] eta R[1,4] k = 2 (ikus 5. irudia).

k = 3 baino ez da geratzen prozesatzeko (grafikoan 4 erpinetik beste edozein erpinera doan ertzerik ez dagoelako).

Berriz ere, ikus dezagun W matrizeari (6. irudia).

W matrizearen arabera, 3 erpinerako hiru bide daude 0 , 1 eta 2 erpinetatik (3. zutabea), eta bide bat dago 3 erpinetik 4 erpinera (3. errenkada). Beraz, bide hauek ditugu prozesatzeko:

Hau izan zen algoritmoaren azken iterazioa. W[0,4] , W[1,4] , W[2,4] gelaxkak distantzia berriekin eguneratzea eta R[0,4] , R[1,4] , R[2,4] gelaxkak ezartzea besterik ez da geratzen. R[2,4] tik 3 .

Hona hemen algoritmoaren amaieran daukaguna (7. irudia).

Aurreko mezutik dakigunez, W matrizeak bide laburrenen bikote guztiak ditu orain G grafikoan. Baina zer gordetzen da R matrizearen barruan?

Etxera itzulia

Bide laburren berri bat aurkitzen genuen bakoitzean, R matrizeari dagokion gelaxka k uneko balioarekin eguneratzen ari ginen. Hasieran, ekintza honek misteriotsua dirudi, oso esanahi sinplea du: erpina gordetzen ari ginen, eta bertatik helmugako erpinera iritsi ginen: i ⭢ k ⭢ j (hemen j iristen gara k zuzenean).

Momentu hau erabakigarria da. Etortzen garen erpin bat ezagutzeak bidea berreraikitzeko aukera ematen digulako atzeraka (otarrain bat bezala) j erpinetik ("era") i erpinera (""tik").

Hona hemen i tik j ibilbidea berreraikitzeko algoritmoaren testu-deskribapena:

1. Prestatu X matrize dinamiko hutsa.
2. Hasi R[i,j] gelaxkako z balio bat irakurtzen.
3. z NO_EDGE bada, i tik j rako ibilbidea aurkitzen da eta #7 urratsera jarraitu beharko genuke.
4. Jarri z X matrize dinamiko bati.
5. Irakurri R[i,z] gelaxkaren balioa z .
6. Errepikatu #3, #4 eta #5 urratsak #3ko irteera-baldintzara iritsi arte.
7. Jarri i Xren aurretik.
8. Erantsi j X ri.
9. Orain X array dinamikoak i tik j ibilbidea dauka.

Sasi-kodean, are sinpleagoa dirudi:

 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

Proba dezagun gure G grafikoan eta berreraiki dezagun ibilbide bat 0 erpinetik 4 erpinera (ikus 8. irudia).

Hona hemen goiko ilustrazioaren testu-deskribapena:

1. R[0,4] ren balioa irakurtzen hasiko gara, eta horrek 3 lortzen du. Algoritmoaren arabera, horrek esan nahi du ibilbidea 4 erpinera doala 3 erpinetik (URDIZ ageri da).

   
   

2. R[0,4] -ren balioa NO_EDGE ez denez, jarraitu eta R[0,3] -ren balioa irakurtzen dugu, 2 -n (BERDEZ erakusten da).

   
   

3. Berriz ere, R[0,3] -ren balioa NO_EDGE ez denez, jarraitu eta R[0,2] -ren balioa irakurtzen dugu, 1 (GORRIZ ageri da).

   
   

4. Azkenik, R[0,1] balio bat irakurriko dugu, eta horrek NO_EDGE balioa ematen du, hau da, ez dago erpin gehiago ibilbidean laguntzen duten 0 eta 4 izan ezik. Beraz, ondoriozko ibilbidea hau da: 0 ⭢ 1 ⭢ 2 ⭢ 3 ⭢ 4 grafikoari erreparatuz gero 0 erpinetik 4 erpinerako biderik laburrenari dagokio.

Irakurle gogoetatsu batek galdetuko luke:

Oso galdera ona da. Ziur gaude R matrizea balio berri batekin eguneratzen dugulako W matrizeko biderik laburrenaren balioa eguneratzen dugunean. Beraz, azkenean, R matrizearen errenkada bakoitzak bide laburrenei lotutako datuak ditu. Ez gehiago, ez gutxiago.

Orain, teoriarekin amaitu dugu, ezarpen garaia da.

C#-n inplementatzea

Aurreko mezuan , Floyd-Warshall algoritmoaren jatorrizko bertsioa ezartzeaz gain, hainbat optimizazio ere integratu ditugu: grafiko eskasentzako euskarria, paralelismoa eta bektorializazioa, eta, azkenean, denak ere konbinatu ditugu.

Ez dago hau guztia errepikatzeko arrazoirik gaur. Hala ere, ibilbideen memorizazioa algoritmoaren jatorrizko bertsioetan eta bektorializatuetan (grafiko eskasetarako laguntzarekin) nola integratzen den erakutsi nahi dizut.

Jatorrizko algoritmoan integratzea

Zaila izango da sinestea, baina ibilbideen memorizazioa algoritmoen jatorrizko bertsioan integratzeko, egin behar duguna da:

1. Hedatu funtzioaren sinadura R matrizea parametro bereizi gisa sartzeko - int[] routes .

   
   

2. Gorde k routes biderik laburrena aldatzen den bakoitzean (lerroak: 2 eta 14).

Hori da. Kode lerro bat eta erdi besterik ez:

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

Algoritmo bektorializatuan integratzea

Bertsio bektorializatu batean integratzeak (grafiko eskasetarako laguntzarekin) esfortzu apur bat gehiago eskatzen du osatzeko, baina, kontzeptuzko urratsak berdinak dira:

1. Hedatu funtzioaren sinadura R matrizea parametro bereizi gisa sartzeko - int[] routes .

   
   

2. Iterazio bakoitzean, hasieratu k balioko bektore berri bat (lerroa: 6).

   
   

3. Gorde k balio bektorea routes bide laburrena aldatzen den bakoitzean (lerroak: 31-32).

   
   

4. Eguneratu algoritmoaren zati ez bektorializatu bat jatorrizko algoritmoa eguneratu genuen moduan (lerroa: 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

Ibilbideen informazioa biltzea nahikoa arrazoizkoa dirudi, zeren... zergatik ez? Batez ere lehendik dauden algoritmoetan integratzea hain erraza denean. Hala ere, ikus dezagun zein praktikoa den lehenespenez integratzea.

Hona hemen bi erreferentzia multzo: batera eta gabe (biek algoritmoaren jatorrizko bertsioak eta bektorializatuak exekutatzen dituzte). Erreferentzia guztiak BenchmarkDotNet v0.13.1 (.NET 6.0.4 x64) exekutatu zituen Intel Core i5-6200U CPU 2.30GHz (Skylake) prozesadorearekin eta Windows 10 exekutatzen duen makina batean.

Esperimentu guztiak aurreko mezuan erabilitako grafikoen multzoan exekutatu ziren: 300, 600, 1200, 2400 eta 4800 erpinak.

Jarraian, Baseline eta BaselineWithRoutes metodoak algoritmoaren jatorrizko bertsioarekin bat datozen eta SpartialVectorOptimisations eta SpartialVectorOptimisationsWithRoutes metodoak algoritmoaren bertsio bektorializatu bati dagozkio.

Erreferentziazko emaitzak ez dira interpretatzeko errazak. Hurbiletik begiratzen baduzu, konbinazio bat aurkituko duzu ibilbide-bilketak algoritmoa azkarrago edo eragin handirik gabe exekutatu duenean.

Honek oso nahasia dirudi (eta hala bada - Denis Bakhvalov eta Andrey Akinshin- ekin ikuskizun hau entzutea gomendatzen dizut, neurketetan zein gauza zailak eragin dezaketen hobeto ulertzeko). Nire iritzirik onena da portaera "nahasia" PUZaren cachearen errendimendu bikainak eragiten duela (grafikoak ez direlako nahiko handiak cacheak asetzeko). Partzialki, teoria hau " lodia " lagin batean oinarritzen da, non grafiko handienean degradazio nabarmena ikus dezakegun. Hala ere, ez nuen egiaztatu.

Oro har, erreferenteak erakusten du oso errendimendu handiko agertokiez eta grafiko erraldoiez ari ez bagara, ondo dago ibilbideen memorizazioa bi algoritmoetan lehenespenez integratzea (baina kontuan izan, memoria-kontsumoa bikoiztu egingo dela, behar dugulako). esleitu bi matrize W eta R baten ordez).

Geratzen den gauza bakarra ibilbidea berreraikitzeko algoritmoaren ezarpena da.

Ibilbidea Berreraikitzeko Algoritmoa ezartzea

Ibilbideen berreraikitze algoritmoak C#-n inplementatzea erraza da eta ia guztiz islatzen du aurrez erakutsitako sasi-kodea ( LinkedList<T> erabiltzen dugu matrize dinamikoa irudikatzeko):

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

Goiko algoritmoa ez da perfektua eta hobetu daiteke zalantzarik gabe. Egin dezakegun hobekuntzarik errazena sz tamainako array bat aurrez esleitu eta alderantzizko ordenan betetzea da:

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

“Optimizazio” honek esleipen-kopurua batera murrizten duen arren, ez du zertan algoritmoa aurrekoa baino “azkarragoa” edo “memoria gutxiago esleitu” egiten. Kontua da i tik j bide bat ordenatuta eduki behar badugu, beti R matrizetik ateratzen ditugun datuak “alderantzikatu” beharko ditugula, eta ez dago ihes egiteko modurik.

Baina datuak alderantzizko ordenan aurkez ditzakegu, orduan LINQ erabil dezakegu eta beharrezkoak ez diren esleipenak saihestu:

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

Kode hau "aldatu" edo "hobetu" daitekeen aldaera gehiago egon daitezke. Hemen une garrantzitsua gogoratzea da: edozein "aldaketak" alde txarrak ditu memoria edo CPU zikloei dagokienez.

Anima zaitez esperimentatzen! Aukerak ia mugagabeak dira!

Ondorioa

Post honetan, Floyd-Warshall algoritmoaren atzean dagoen teorian sakondu dugu eta bide laburrenak "ibilbide" memorizatzeko aukerarekin zabaldu dugu. Ondoren, C# inplementazioak eguneratu ditugu (jatorrizkoak eta bektorializatuak) aurreko mezutik . Azkenean, algoritmoaren bertsio batzuk ezarri ditugu "ibilbideak" berreraikitzeko.

Asko errepikatu dugu, baina aldi berean, espero dut honetan zerbait berri eta interesgarria aurkitu izana. Hau ez da bikote guztien bide laburrenen arazoaren amaiera. Hau hasiera besterik ez da.

Irakurketa gustatu izana espero dut, eta hurrengora arte!