C# тилинде Флойд-Уоршалл алгоритми менен бардык жуптардын эң кыска жолдорунун "маршруттарын" кантип тапса болот

Introduction

Мурунку постто биз Флойд-Уоршалл алгоритмин колдонуу менен бардык жуптардын эң кыска жол маселесин кантип чечүүнү көрдүк. Биз ошондой эле параллелизмди жана векторизацияны колдонуу менен алгоритмдин иштешин жакшыртуунун бир нече жолдорун изилдедик.

Бирок, Флойд-Уоршалл алгоритминин натыйжалары жөнүндө ойлонсоңуз, кызыктуу учурду тез эле түшүнөсүз – биз графиктеги чокулардын ортосундагы аралыктарды (эң кыска жолдордун маанилери) билебиз, бирок “маршруттарды” билбейбиз, б.а. биз ар бир эң кыска жолго кандай чокулар салым кошоорун билбейбиз жана биз бул “маршруттарды” бизде болгон натыйжалардан кайра кура албайбыз.

Бул постто мен сизди мага кошулууга жана Флойд-Уоршалл алгоритмин кеңейтүүгө чакырам. Бул жолу биз аралыкты эсептеп, “маршрутту” кайра түзө аларыбызды текшеребиз.

Бир аз белгилүү теория…

Кодго жана эталондорго кирүүдөн мурун, келгиле, Флойд-Уоршалл алгоритми кандай иштээри жөнүндөгү теорияны кайра карап чыгалы.

Бул жерде алгоритмдин тексттик сүрөттөлүшү:

1. Биз N өлчөмүндөгү ( G ) графигин N x N өлчөмүндөгү ( W ) матрица катары көрсөтүүдөн баштайбыз, мында ар бир 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 кадам G -тин бардык чокулары k катары колдонулганга чейин кийинки 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 матрицасынын ар бир W[i,j] уячасы же i жана j чокуларынын ортосундагы эң кыска жолдун аралыгын же алардын ортосунда жол жок болсо, NO_EDGE маанисин камтыйт.

Мен башында айтып өткөндөй – ушул гана маалыматка ээ болуу бул чокулардын ортосундагы каттамдарды кайра курууну мүмкүн эмес кылат. Анда... бул каттамдарды калыбына келтирүү үчүн эмне кылышыбыз керек?

Ооба… бул ачык угулушу мүмкүн, бирок… биз көбүрөөк маалымат чогултушубуз керек!

… Бир аз эле теория, бирок башка бурчтан

Флойд-Уоршалл алгоритминин маңызы k орто чокусу аркылуу i j чейинки потенциалдуу жаңы жолдун аралыгы менен белгилүү W[i,j] аралыктагы бөлүм болуп саналат.

Мен бул деталга абдан көп көңүл буруп жатам, анткени бул биз маршруттук маалыматты кантип сактай аларыбыздын ачкычы. Мурунку 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 менен четтери бар, ошондой эле 2 же 4 эмес ар кандай j үчүн алгоритмдерди аткаруунун мааниси жок ( j бул жерде “to”).

Ошондуктан биринчи кадамыбыз k = 1 , i = 0 жана j = 2,4 үчүн алгоритмди аткаруу болот.

Биз эки жолду таптык: жаңы жол ( 0 ⭢ 1 ⭢ 2 ) жана жарлык ( 0 ⭢ 1 ⭢ 4 ). Экөө тең 1 чокусу аркылуу өтөт. Эгер биз бул маалыматты ( 2 жана 4 менен 1 чейин болгон факты) азыр бир жерде сактабасак, ал биротоло жоголуп кетет (жана бул биз каалаган нерсеге таптакыр карама-каршы).

Анда биз эмне кылышыбыз керек? Биз W матрицасын жаңы маанилер менен жаңыртабыз (3а сүрөттү караңыз), ошондой эле k маанисин (ал k = 1 ) бирдей өлчөмдөгү жаңы R матрицасынын R[0,2] жана R[0,4] уячаларында сактайбыз. W матрицасы катары, бирок NO_EDGE маанилери менен инициализацияланган (3b сүрөтүн караңыз).

Азыр R матрицасы эмне экенине көңүл бурбаңыз. Келгиле, уланталы жана кийинки k = 2 үчүн алгоритмди аткаралы.

Бул жерде биз k = 1, бирок бул жолу G графигинин ордуна W матрицасын колдонобуз. 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 матрицасына ылайык, 0 , 1 жана 2 чокуларынан 3 чокусуна үч жол бар (№3 мамыча), ал эми 3 чокудан 4 чокусуна чейин бир жол бар (№3 катар). Ошондуктан, биз иштетүү үчүн төмөнкү жолдору бар:

Бул алгоритмдин акыркы итерациясы болгон. Болгону W[0,4] , W[1,4] , W[2,4] уячаларын жаңы аралыктар менен жаңыртып, R[0,4] , R[1,4] , R[2,4] уячаларын коюу гана калды. R[2,4] чейин 3 .

Алгоритмдин аягында бизде эмне бар (7-сүрөт).

Мурунку посттон билгенибиздей, W матрицасы азыр G графигиндеги эң кыска жолдордун бардык жуптарын камтыйт. Бирок R матрицасында эмне сакталат?

Үйгө кайтуу

Биз жаңы эң кыска жолду тапкан сайын, биз R матрицасынын тиешелүү уячасын учурдагы k мааниси менен жаңыртып жаттык. Башында бул аракет табышмактуу көрүнүшү мүмкүн, бирок анын абдан жөнөкөй мааниси бар – биз көздөгөн чокуга жеткен чокусун сактап жатканбыз: i ⭢ k ⭢ j (бул жерде биз k дан түз эле j жетип жатабыз).

Бул учур чечүүчү. Анткени биз келген чокуну билүү j чокусунан ("чейин") i чокусуна ("ден") артка (омар сыяктуу) жылып, маршрутту кайра курууга мүмкүндүк берет.

Бул жерде i j чейинки маршрутту калыбына келтирүү алгоритминин тексттик сүрөттөлүшү:

1. Бош динамикалык массив X даярдаңыз.
2. R[i,j] уячасынан z маанисин окуу менен баштаңыз.
3. Эгерде z NO_EDGE болсо, анда i j чейинки маршрут табылып, №7 кадамга өтүшүбүз керек.
4. X динамикалык массивинин алдына z жазыңыз.
5. R[i,z] уячасынын маанисин z ичинде оку.
6. №3, №4 жана №5 кадамдарды №3 чыгуу шартына жеткенге чейин кайталаңыз.
7. X дегенге i жаз.
8. X j тиркеңиз.
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 чокусуна чейинки эң кыска жолго туура келет.

Ойлуу окурман сурашы мүмкүн:

Бул абдан жакшы суроо. Биз ишенебиз, анткени биз W матрицасында эң кыска жол маанисин жаңыртканыбызда R матрицасын жаңы маани менен жаңыртабыз. Ошентип, акырында, R матрицасынын ар бир сабында эң кыска жолдорго тиешелүү маалыматтар камтылган. Артык эмес, кем эмес.

Азыр биз теория менен бүттүк, ишке ашыруу мезгили келди.

C# тилинде ишке ашыруу

Мурунку постто , Флойд-Уоршалл алгоритминин оригиналдуу версиясын ишке ашыруудан тышкары, биз ар кандай оптималдаштырууларды да бириктирдик: сейрек графиктерди колдоо, параллелизм жана векторизация, акырында биз алардын баарын бириктирдик.

Мунун баарын бүгүн кайталоого эч кандай негиз жок. Бирок, мен сизге маршруттук жаттоону алгоритмдин оригиналдуу жана векторлоштурулган (сейрек графиктердин колдоосу менен) версияларына кантип интеграциялоону көрсөткүм келет.

Оригиналдуу Алгоритмге Интеграция

Ишенүү кыйын болушу мүмкүн, бирок маршрутту жаттап алууну алгоритмдердин оригиналдуу версиясына кошуу үчүн, биз эмне кылышыбыз керек:

1. R матрицасын өзүнчө параметр катары кошуу үчүн функциянын кол тамгасын кеңейтүү – int[] routes .

   
   

2. Эң кыска жол өзгөргөн сайын routes k сактаңыз (саптар: 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. Эң кыска жол өзгөргөн сайын routes k маанилердин векторун сактаңыз (саптар: 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) процессору менен жабдылган жана Windows 10 иштетилген машинада аткарылган.

Бардык эксперименттер мурунку постто колдонулган графиктердин алдын ала аныкталган топтому боюнча аткарылды: 300, 600, 1200, 2400 жана 4800 чокулары.

Төмөндө эталондук жыйынтыктар келтирилген, анда Baseline жана BaselineWithRoutes ыкмалары алгоритмдин баштапкы версиясына, ал эми SpartialVectorOptimisations жана SpartialVectorOptimisationsWithRoutes ыкмалары алгоритмдин векторлоштурулган (сейрек графиктерди колдоо менен) версиясына туура келет.

Эталондук натыйжаларды чечмелөө оңой эмес. Эгер жакшылап карасаңыз, маршрутту чогултуу алгоритмди тезирээк же такыр эч кандай таасирсиз иштеткен комбинацияны табасыз.

Бул абдан чаташкан көрүнөт (жана ошондой болсо – мен сизге Денис Бахвалов жана Андрей Акиншин менен бул шоуну угууну катуу кеңеш берем, кандай татаал нерселер өлчөөлөргө таасир эте аларын жакшыраак түшүнүңүз). Бул жерде менин эң жакшы түшүнүгүм "чаташкан" жүрүм-турум CPU кэшинин мыкты иштешинен улам келип чыгат (анткени графиктер кэштерди толтурууга жетиштүү чоң эмес). Жарым-жартылай, бул теория " калың " үлгүгө негизделген, анда биз эң чоң графикте олуттуу деградацияны көрө алабыз. Бирок, мен аны текшерген жокмун.

Жалпысынан, эталон көрсөткөндөй, эгерде биз өтө жогорку деңгээлдеги сценарийлер жана чоң графиктер жөнүндө сөз кылбасак, маршруттук жаттап алууну эки алгоритмге тең демейки боюнча интеграциялоо туура болот (бирок эсиңизде болсун, эстутум керектөө эки эсеге көбөйөт, анткени биз бир матрицанын ордуна 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; }

Бул кодду "өзгөртүү" же "жакшыртуу" боюнча дагы көптөгөн варианттар болушу мүмкүн. Бул жерде маанилүү учур эстен чыгарбоо керек - ар кандай "өзгөрүүлөр" эс тутумунун же CPU циклинин терс жактары бар.

Эксперименттен тартынбаңыз! Мүмкүнчүлүктөр дээрлик чексиз!

Корутунду

Бул постто биз Флойд-Уоршалл алгоритминин артындагы теорияга терең сүңгүп кирдик жана аны эң кыска жолдордун "маршруттарын" жаттоо мүмкүнчүлүгү менен кеңейттик. Андан кийин биз C# ишке ашырууларын (оригиналдуу жана векторлоштурулган) мурунку посттон жаңырттык. Акыр-аягы, биз "маршруттарды" кайра куруу үчүн алгоритмдин бир нече версиясын ишке ашырдык.

Биз көп кайталадык, бирок ошол эле учурда, мен сиз бул жаңы жана кызыктуу бир нерсе таптым деп үмүттөнөм. Бул бардык түгөйлөрдүн эң кыска жолдорунун көйгөйүнүн аягы эмес. Бул башталышы гана.

Окуу сизге жакты деп үмүттөнөм жана кийинки жолу көрүшкөнчө!