Sarrera , bikote guztien bide laburrenaren arazoa nola konpondu ikusi genuen erabiliz. Paralelismoa eta bektorizazioa erabiliz algoritmoaren errendimendua hobetzeko hainbat modu ere aztertu ditugu. Aurreko mezuan Floyd-Warshall algoritmoa 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: Hasteko, tamainako ( ) grafiko bat tamainako ( ) matrize gisa irudikatzen dugu, non gelaxka bakoitzak erpinetik erpinera arteko ertz baten pisua duen (ikus 1. Irudia). Erpinen artean ertzerik ez dagoen kasuetan, gelaxka balio berezi batean ezartzen da (1. Irudian gelaxka ilun gisa agertzen da). N G N x N W W[i,j] i j NO_EDGE Hemendik aurrera, esaten dugu – eta erpinen arteko distantzia dauka. W[i,j] i j Ondoren, erpin bat hartu eta erpin-pare guztietan zehar itertuko dugu distantzia gaur egun ezagutzen den eta arteko distantzia baino txikiagoa den egiaztatuz. k W[i,j] i ⭢ k ⭢ j i j Baliorik txikiena -n gordetzen da eta #3 urratsa hurrengo errepikatzen da ren erpin guztiak gisa erabili arte. W[i,j] k G k 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, matrizearen gelaxka bakoitzak eta erpinen arteko bide laburreneko distantzia edo balio bat dauka, haien artean biderik ez badago. W W[i,j] i j NO_EDGE 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 distantzia ezaguneko konpartimentu bat da, -tik bitarteko bitarteko erpinetik zehar bide potentzial berriaren distantzia duena. W[i,j] i j k 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: , , , , eta . 0 ⭢ 1 :2 0 ⭢ 4 :10 1 ⭢ 3 :1 2 ⭢ 4 :1 3 ⭢ 2 :1 3 ⭢ 4 :3 “tik” ⭢ “noraino” :”distantzia” formatua erabiltzen dut bideak idazteko. Aurreko argitalpeneko - Egilearen oharra Badakigu ere ez dagoela erpinera daraman ertzerik, beraz rako algoritmo bat exekutatzeak ez du zentzurik. Begi bistakoa da, gainera, ertz bakar bat dagoela ( ) erpinetik erpinera doana, eta horrek guztiaren exekuzioa ere nahiko zentzugabe bihurtzen du ( -a hemengoa da) eta erpinera delako. eta dituen ertzak ditu, ez du zentzurik edo ez den edozein ren algoritmoak exekutatzeko ( -a "to" da hemen). 0 k = 0 0 ⭢ 1 0 1 i != 0 i 1 2 4 2 4 j j Horregatik, gure lehen urratsa , eta ren algoritmo bat exekutatzen aritzea izango da. k = 1 i = 0 j = 2,4 Urratsa Bidea Iruzkina 1 0 ⭢ 1 ⭢ 2 Aurkitutako bidea. Distantzia = 3 (ez zen ezer) 2 0 ⭢ 1 ⭢ 4 Aurkitutako bidea. Distantzia = 8 (10 zen). Bi bide aurkitu ditugu: bide berri bat ( ) eta lasterbide bat ( ). Biak erpinetik pasatzen dira. Ez badugu informazio hori ( eta iritsi garela oraintxe bertan) nonbait gordetzen, betirako galduko da (eta hori nahi dugunaren guztiz kontrakoa da). 0 ⭢ 1 ⭢ 2 0 ⭢ 1 ⭢ 4 1 2 4 1 Beraz, zer egin behar dugu? matrizea balio berriekin eguneratuko dugu (ikus 3a irudia) eta tamaina bereko matrize berri baten eta gelaxketan -ren balioa ere gordeko dugu ( ). matrize gisa baina balioekin hasieratuta (ikus 3b irudia). W R R[0,2] R[0,4] k k = 1 W NO_EDGE Oraintxe bertan, ez zentratu matrizea zer den zehazki. Jarrai dezagun eta exekutatu hurrengo algoritmoa. R k = 2 Hemen, baina oraingoan, grafikoaren ordez matrizea erabiliko dugu. Begiratu matrizeari, batez ere 2. zutabean eta 2. errenkadan (4. irudia). k = 1, G W W Hemen ikus dezakezu, erpinerako bi bide daude erpinetik eta erpinetik (2. zutabea), eta bi bide daude erpinetik erpinera eta erpinera (2. errenkada). Hori jakinda, zentzuzkoa da algoritmoa , eta konbinazioetarako soilik exekutatzeko. 2 0 1 2 3 4 k = 2 i = 0,1 j = 3,4 Urratsa Bidea Iruzkina 1 0 ⭢ 2 ⭢ 3 Aurkitutako bidea. Distantzia = 4 (ez zen ezer) 2 0 ⭢ 2 ⭢ 4 Aurkitutako bidea. Distantzia = 6 (8 zen) 3 1 ⭢ 2 ⭢ 3 Aurkitutako bidea. Distantzia = 2 (ez zen ezer) 4 1 ⭢ 2 ⭢ 4 Aurkitutako bidea. Distantzia = 4 (6 zen) Lehenago egin dugun bezala, , , , gelaxkak eta gelaxkekin eguneratzen ari gara. , eta (ikus 5. irudia). 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 baino ez da geratzen prozesatzeko (grafikoan erpinetik beste edozein erpinera doan ertzerik ez dagoelako). k = 3 4 Berriz ere, ikus dezagun matrizeari (6. irudia). W matrizearen arabera, erpinerako hiru bide daude , eta erpinetatik (3. zutabea), eta bide bat dago erpinetik erpinera (3. errenkada). Beraz, bide hauek ditugu prozesatzeko: W 3 0 1 2 3 4 Urratsa Bidea Iruzkina 1 0 ⭢ 3 ⭢ 4 Aurkitutako bidea. Distantzia = 5 (6 zen) 2 1 ⭢ 3 ⭢ 4 Aurkitutako bidea. Distantzia = 3 (4 zen) 3 2 ⭢ 3 ⭢ 4 Aurkitutako bidea. Distantzia = 2 (3 zen) Hau izan zen algoritmoaren azken iterazioa. , , gelaxkak distantzia berriekin eguneratzea eta , , gelaxkak ezartzea besterik ez da geratzen. tik . W[0,4] W[1,4] W[2,4] R[0,4] R[1,4] R[2,4] R[2,4] 3 Hona hemen algoritmoaren amaieran daukaguna (7. irudia). dakigunez, matrizeak bide laburrenen bikote guztiak ditu orain grafikoan. Baina zer gordetzen da matrizearen barruan? Aurreko mezutik W G R Etxera itzulia Bide laburren berri bat aurkitzen genuen bakoitzean, matrizeari dagokion gelaxka uneko balioarekin eguneratzen ari ginen. Hasieran, ekintza honek misteriotsua dirudi, oso esanahi sinplea du: erpina gordetzen ari ginen, eta bertatik helmugako erpinera iritsi ginen: (hemen iristen gara zuzenean). R k i ⭢ k ⭢ j j k Momentu hau erabakigarria da. Etortzen garen erpin bat ezagutzeak bidea berreraikitzeko aukera ematen digulako atzeraka (otarrain bat bezala) erpinetik ("era") erpinera (""tik"). j i Hona hemen tik ibilbidea berreraikitzeko algoritmoaren testu-deskribapena: i j Prestatu matrize dinamiko hutsa. X Hasi gelaxkako balio bat irakurtzen. R[i,j] z bada, tik rako ibilbidea aurkitzen da eta #7 urratsera jarraitu beharko genuke. z NO_EDGE i j Jarri matrize dinamiko bati. z X Irakurri gelaxkaren balioa . R[i,z] z Errepikatu #3, #4 eta #5 urratsak #3ko irteera-baldintzara iritsi arte. Jarri Xren aurretik. i Erantsi ri. j X Orain array dinamikoak tik ibilbidea dauka. X i j Kontuan izan goiko algoritmoak lehendik dauden bideetarako soilik funtzionatzen duela. Errendimenduaren ikuspuntutik ere ez da perfektua eta ziur optimiza daitekeela. Hala ere, argitalpen honen esparruan, berariaz deskribatzen da orri batean errazago ulertzeko eta erreproduzitzeko moduan. - Egilearen oharra 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 grafikoan eta berreraiki dezagun ibilbide bat erpinetik erpinera (ikus 8. irudia). G 0 4 Hona hemen goiko ilustrazioaren testu-deskribapena: ren balioa irakurtzen hasiko gara, eta horrek lortzen du. Algoritmoaren arabera, horrek esan nahi du ibilbidea erpinera doala erpinetik (URDIZ ageri da). R[0,4] 3 4 3 -ren balioa ez denez, jarraitu eta -ren balioa irakurtzen dugu, -n (BERDEZ erakusten da). R[0,4] NO_EDGE R[0,3] 2 Berriz ere, -ren balioa ez denez, jarraitu eta -ren balioa irakurtzen dugu, (GORRIZ ageri da). R[0,3] NO_EDGE R[0,2] 1 Azkenik, balio bat irakurriko dugu, eta horrek balioa ematen du, hau da, ez dago erpin gehiago ibilbidean laguntzen duten eta izan ezik. Beraz, ondoriozko ibilbidea hau da: grafikoari erreparatuz gero erpinetik erpinerako biderik laburrenari dagokio. R[0,1] NO_EDGE 0 4 0 ⭢ 1 ⭢ 2 ⭢ 3 ⭢ 4 0 4 Irakurle gogoetatsu batek galdetuko luke: Nola ziurtatu dezakegu matrizetik irakurtzen ditugun datu guztiak bide berekoak direla? R - Irakurle pentsakorra Oso galdera ona da. Ziur gaude matrizea balio berri batekin eguneratzen dugulako matrizeko biderik laburrenaren balioa eguneratzen dugunean. Beraz, azkenean, matrizearen errenkada bakoitzak bide laburrenei lotutako datuak ditu. Ez gehiago, ez gutxiago. R W R Orain, teoriarekin amaitu dugu, ezarpen garaia da. C#-n inplementatzea , Floyd-Warshall algoritmoaren jatorrizko bertsioa ezartzeaz gain, hainbat optimizazio ere integratu ditugu: grafiko eskasentzako euskarria, paralelismoa eta bektorializazioa, eta, azkenean, denak ere konbinatu ditugu. Aurreko mezuan 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: Hedatu funtzioaren sinadura matrizea parametro bereizi gisa sartzeko - . R int[] routes Gorde k biderik laburrena aldatzen den bakoitzean (lerroak: 2 eta 14). routes 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: Hedatu funtzioaren sinadura matrizea parametro bereizi gisa sartzeko - . R int[] routes Iterazio bakoitzean, hasieratu balioko bektore berri bat (lerroa: 6). k Gorde balio bektorea bide laburrena aldatzen den bakoitzean (lerroak: 31-32). k routes 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; } } } } } Oroigarri txiki bat - eragiketak bektore berri bat itzultzen du, non balioak sarrera-bektoreen dagozkien bi balioetatik txikiagoaren berdinak diren, hau da, bektorearen balioa berdina bada, orduan eragiketak -tik balio bat hautatzen du, bestela, tik balio bat hautatzen du. Vector.ConditionalSelect lt_vec -1 ij_vec k_vec - Egilearen oharra 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 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. BenchmarkDotNet Esperimentu guztiak erabilitako grafikoen multzoan exekutatu ziren: 300, 600, 1200, 2400 eta 4800 erpinak. aurreko mezuan Iturburu-kodea eta grafiko esperimentalak GitHub-eko biltegian daude eskuragarri. Grafiko esperimentalak direktorioan aurki daitezke. Data/Sparse-Graphs.zip Post honetako erreferentzia guztiak APSP02.cs fitxategian ezartzen dira. Jarraian, eta metodoak algoritmoaren jatorrizko bertsioarekin bat datozen eta eta metodoak algoritmoaren bertsio bektorializatu bati dagozkio. Baseline BaselineWithRoutes SpartialVectorOptimisations SpartialVectorOptimisationsWithRoutes Metodoa Tamaina Batez bestekoa (ms) Errorea (ms) StdDev (ms) Oinarrizko lerroa 300 40.233 0,0572 0,0477 BaselineWithRoutes 300 40.349 0,1284 0,1201 SpartialVectorOptimisations 300 4.472 0,0168 0,0140 SpartialVectorOptimisationsWithRoutes 300 4.517 0,0218 0,0193 Oinarrizko lerroa 600 324.637 5.6161 4,6897 BaselineWithRoutes 600 321.173 1.4339 1.2711 SpartialVectorOptimisations 600 32.133 0,2151 0,1679 SpartialVectorOptimisationsWithRoutes 600 34.646 0,1286 0,1073 Oinarrizko lerroa 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 SpartialVectorOptimisationsWithRoutes 1200 381.625 3,6975 3.2777 Oinarrizko lerroa 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 SpartialVectorOptimisationsWithRoutes 2400 3.079.006 8.6125 1918.7 Oinarrizko lerroa 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 SpartialVectorOptimisationsWithRoutes 4800 21.004.612 79,8752 70,8073 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 - eta ekin 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 " " lagin batean oinarritzen da, non grafiko handienean degradazio nabarmena ikus dezakegun. Hala ere, ez nuen egiaztatu. Denis Bakhvalov Andrey Akinshin- ikuskizun lodia 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 eta baten ordez). W R 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 ( erabiltzen dugu matrize dinamikoa irudikatzeko): 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; } Goiko algoritmoa ez da perfektua eta hobetu daiteke zalantzarik gabe. Egin dezakegun hobekuntzarik errazena tamainako array bat aurrez esleitu eta alderantzizko ordenan betetzea da: 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); } “Optimizazio” honek esleipen-kopurua batera murrizten duen arren, ez du zertan algoritmoa aurrekoa baino “azkarragoa” edo “memoria gutxiago esleitu” egiten. Kontua da tik bide bat ordenatuta eduki behar badugu, beti matrizetik ateratzen ditugun datuak “alderantzikatu” beharko ditugula, eta ez dago ihes egiteko modurik. i j R 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! Routes.cs fitxategian GitHub-en ibilbide-algoritmo guztien inplementazioak aurki ditzakezu. 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) . Azkenean, algoritmoaren bertsio batzuk ezarri ditugu "ibilbideak" berreraikitzeko. aurreko mezutik 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!
