ວິທີການຊອກຫາ "ເສັ້ນທາງ" ຂອງທຸກຄູ່ເສັ້ນທາງທີ່ສັ້ນທີ່ສຸດດ້ວຍ Floyd-Warshall Algorithm ໃນ C#

ແນະນຳ

ໃນ ບົດຂຽນທີ່ຜ່ານມາ , ພວກເຮົາໄດ້ເຫັນວິທີການແກ້ໄຂບັນຫາເສັ້ນທາງສັ້ນທີ່ສຸດຄູ່ທັງຫມົດໂດຍໃຊ້ Floyd-Warshall algorithm . ພວກເຮົາຍັງໄດ້ຄົ້ນຫາຫຼາຍວິທີເພື່ອປັບປຸງປະສິດທິພາບຂອງສູດການຄິດໄລ່ໂດຍໃຊ້ຂະໜານ ແລະ vectorization.

ຢ່າງໃດກໍຕາມ, ຖ້າທ່ານຄິດກ່ຽວກັບຜົນໄດ້ຮັບຂອງ Floyd-Warshall algorithm, ທ່ານຈະຮູ້ທັນທີທັນໃດທີ່ຫນ້າສົນໃຈ - ພວກເຮົາຮູ້ໄລຍະຫ່າງ (ຄ່າຂອງເສັ້ນທາງທີ່ສັ້ນທີ່ສຸດ) ລະຫວ່າງ vertexes ໃນກາຟແຕ່ພວກເຮົາບໍ່ຮູ້ວ່າ "ເສັ້ນທາງ" ຫມາຍຄວາມວ່າ, ພວກ​ເຮົາ​ບໍ່​ຮູ້​ວ່າ​ສິ່ງ​ທີ່ vertexes ປະ​ກອບ​ສ່ວນ​ໃຫ້​ແຕ່​ລະ​ເສັ້ນ​ທາງ​ສັ້ນ​ທີ່​ສຸດ, ແລະ​ພວກ​ເຮົາ​ບໍ່​ສາ​ມາດ​ສ້າງ "ເສັ້ນ​ທາງ" ເຫຼົ່າ​ນີ້​ຄືນ​ໃຫມ່​ຈາກ​ຜົນ​ໄດ້​ຮັບ​ທີ່​ພວກ​ເຮົາ​ມີ.

ໃນບົດຂຽນນີ້, ຂ້າພະເຈົ້າຂໍເຊີນທ່ານເຂົ້າຮ່ວມກັບຂ້າພະເຈົ້າແລະຂະຫຍາຍລະບົບສູດການຄິດໄລ່ Floyd-Warshall. ເວລານີ້, ພວກເຮົາຈະເຮັດໃຫ້ແນ່ໃຈວ່າພວກເຮົາສາມາດຄິດໄລ່ໄລຍະທາງແລະສ້າງ "ເສັ້ນທາງ".

ທິດສະດີທີ່ຮູ້ຈັກເລັກນ້ອຍ…

ກ່ອນທີ່ຈະເຂົ້າໄປໃນລະຫັດແລະມາດຕະຖານ, ໃຫ້ພວກເຮົາທົບທວນຄືນທິດສະດີຂອງວິທີການເຮັດວຽກຂອງ Floyd-Warshall.

ນີ້ແມ່ນຄໍາອະທິບາຍຂໍ້ຄວາມຂອງ algorithm:

1. ພວກເຮົາເລີ່ມຕົ້ນໂດຍການເປັນຕົວແທນຂອງກາຟ ( G ) ຂອງຂະຫນາດ N ເປັນ matrix ( W ) ຂອງຂະຫນາດ N x N ທີ່ທຸກໆເຊນ W[i,j] ມີນ້ໍາຫນັກຂອງຂອບຈາກຈຸດສູງສຸດ i ຫາ vertex j (ເບິ່ງຮູບ 1). ໃນ​ກໍ​ລະ​ນີ​ທີ່​ບໍ່​ມີ​ຂອບ​ເຂດ​ລະ​ຫວ່າງ vertexes​, ເຊ​ລ​ໄດ້​ຖືກ​ຕັ້ງ​ຄ່າ​ເປັນ NO_EDGE ພິ​ເສດ (ສະ​ແດງ​ໃຫ້​ເຫັນ​ເປັນ​ຕາ​ຕະ​ລາງ​ສີ​ດໍາ​ໃນ​ຮູບ​ພາບ 1​)​.

   
   

2. ຈາກນີ້ໄປ, ພວກເຮົາເວົ້າວ່າ – W[i,j] ມີໄລຍະຫ່າງລະຫວ່າງຈຸດສູງສຸດ i ແລະ j .

   
   

3. ຕໍ່ໄປ, ພວກເຮົາເອົາ vertex k ແລະ iterate ຜ່ານທຸກຄູ່ຂອງ vertexes W[i,j] ກວດເບິ່ງວ່າໄລຍະທາງ i ⭢ k ⭢ j ແມ່ນນ້ອຍກວ່າໄລຍະຫ່າງລະຫວ່າງ i ກັບ j .

   
   

4. ຄ່າທີ່ນ້ອຍທີ່ສຸດຈະຖືກເກັບໄວ້ໃນ W[i,j] ແລະຂັ້ນຕອນ #3 ແມ່ນຊ້ໍາກັນສໍາລັບ k ຕໍ່ໄປຈົນກ່ວາຈຸດສູງສຸດທັງຫມົດຂອງ G ຖືກນໍາໃຊ້ເປັນ k .

ນີ້ແມ່ນລະຫັດ pseudo:

 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] ຂອງ matrix W ຈະມີໄລຍະຫ່າງຂອງເສັ້ນທາງທີ່ສັ້ນທີ່ສຸດລະຫວ່າງຈຸດ i ແລະ j ຫຼືຄ່າ NO_EDGE , ຖ້າບໍ່ມີເສັ້ນທາງລະຫວ່າງພວກມັນ.

ດັ່ງທີ່ຂ້າພະເຈົ້າໄດ້ກ່າວໃນຕອນຕົ້ນ - ມີພຽງແຕ່ຂໍ້ມູນນີ້ເຮັດໃຫ້ມັນເປັນໄປບໍ່ໄດ້ທີ່ຈະສ້າງເສັ້ນທາງລະຫວ່າງຈຸດສູງສຸດເຫຼົ່ານີ້. ດັ່ງນັ້ນ… ພວກເຮົາຄວນເຮັດແນວໃດເພື່ອໃຫ້ສາມາດສ້າງເສັ້ນທາງເຫຼົ່ານີ້ຄືນໃຫມ່?

ດີ… ມັນອາດຈະຟັງໄດ້ຊັດເຈນ ແຕ່… ພວກເຮົາຕ້ອງເກັບກຳຂໍ້ມູນຕື່ມອີກ!

… ເລັກນ້ອຍຂອງທິດສະດີດຽວກັນແຕ່ຈາກມຸມທີ່ແຕກຕ່າງກັນ

ໂດຍເນື້ອແທ້ແລ້ວຂອງ Floyd-Warshall algorithm ແມ່ນຊ່ອງຫວ່າງຂອງໄລຍະທາງທີ່ຮູ້ຈັກ W[i,j] ທີ່ມີໄລຍະຫ່າງຂອງເສັ້ນທາງທີ່ອາດຈະເປັນໄປໄດ້ໃຫມ່ຈາກ i ຫາ j ຜ່ານຈຸດກາງ k .

ຂ້າພະເຈົ້າດຶງຄວາມສົນໃຈຫຼາຍກັບລາຍລະອຽດນີ້ເພາະວ່າມັນເປັນກຸນແຈຂອງວິທີທີ່ພວກເຮົາສາມາດຮັກສາຂໍ້ມູນເສັ້ນທາງ. ໃຫ້ພວກເຮົາເອົາເສັ້ນສະແດງກ່ອນຫນ້າຂອງ 5 vertexes (ເບິ່ງຮູບ 2) ແລະປະຕິບັດວິທີການ Floyd-Warshall ກ່ຽວກັບມັນ.

ໃນເບື້ອງຕົ້ນ, ພວກເຮົາຮູ້ກ່ຽວກັບຂອບກາຟທັງຫມົດ, ເຊິ່ງເຮັດໃຫ້ພວກເຮົາມີເສັ້ນທາງດັ່ງຕໍ່ໄປນີ້: 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 , ມັນຍັງບໍ່ມີຄວາມຫມາຍທີ່ຈະປະຕິບັດ algorithms ສໍາລັບ j ໃດໆທີ່ບໍ່ແມ່ນ 2 ຫຼື 4 ( j ແມ່ນ "to" ທີ່ນີ້).

ນັ້ນແມ່ນເຫດຜົນທີ່ວ່າຂັ້ນຕອນທໍາອິດຂອງພວກເຮົາແມ່ນເພື່ອປະຕິບັດ algorithm ສໍາລັບ k = 1 , i = 0 ແລະ j = 2,4 .

ພວກເຮົາໄດ້ພົບເຫັນສອງເສັ້ນທາງ: ເສັ້ນທາງໃຫມ່ ( 0 ⭢ 1 ⭢ 2 ) ແລະທາງລັດ ( 0 ⭢ 1 ⭢ 4 ). ທັງສອງຜ່ານຈຸດສູງສຸດ 1 . ຖ້າພວກເຮົາບໍ່ເກັບຮັກສາຂໍ້ມູນນີ້ (ຄວາມຈິງທີ່ພວກເຮົາໄດ້ໄປຫາ 2 ແລະ 4 ເຖິງ 1 ) ບາງບ່ອນໃນປັດຈຸບັນ, ມັນຈະສູນເສຍຕະຫຼອດໄປ (ແລະນັ້ນແມ່ນຂ້ອນຂ້າງກົງກັນຂ້າມກັບສິ່ງທີ່ພວກເຮົາຕ້ອງການ).

ດັ່ງນັ້ນພວກເຮົາຄວນເຮັດແນວໃດ? ພວກ​ເຮົາ​ຈະ​ປັບ​ປຸງ matrix W ກັບ​ຄ່າ​ໃຫມ່ (ເບິ່ງ​ຮູບ​ພາບ 3a​) ແລະ​ຍັງ​ເກັບ​ຄ່າ​ຂອງ k (ຊຶ່ງ​ເປັນ k = 1 ) ໃນ​ເຊ​ລ R[0,2] ແລະ R[0,4] ຂອງ matrix R ໃຫມ່​ຂະ​ຫນາດ​ດຽວ​ກັນ ເປັນ matrix W ແຕ່ເລີ່ມຕົ້ນດ້ວຍຄ່າ NO_EDGE (ເບິ່ງຮູບ 3b).

ໃນປັດຈຸບັນ, ບໍ່ໄດ້ສຸມໃສ່ສິ່ງທີ່ແນ່ນອນ matrix R ແມ່ນ. ໃຫ້ເຮົາສືບຕໍ່ໄປ ແລະປະຕິບັດ algorithm ສໍາລັບ k = 2 ຕໍ່ໄປ.

ໃນທີ່ນີ້, ພວກເຮົາຈະເຮັດການວິເຄາະດຽວກັນ (ເພື່ອເຂົ້າໃຈວ່າການລວມກັນແມ່ນຫຍັງທີ່ມີຄວາມຫມາຍທີ່ຈະປະຕິບັດ) ດັ່ງທີ່ພວກເຮົາໄດ້ເຮັດສໍາລັບ k = 1, ແຕ່ເວລານີ້, ພວກເຮົາຈະໃຊ້ matrix W ແທນກຣາຟ G . ເບິ່ງ matrix W , ໂດຍສະເພາະໃນຖັນ #2 ແລະແຖວ #2 (ຮູບ 4).

ໃນທີ່ນີ້ທ່ານສາມາດເຫັນໄດ້, ມີສອງເສັ້ນທາງໄປສູ່ຈຸດສູງສຸດ 2 ຈາກຈຸດສູງສຸດ 0 ແລະຈາກຈຸດສູງສຸດ 1 (ຖັນ # 2), ແລະສອງເສັ້ນທາງຈາກຈຸດສູງສຸດ 2 ຫາຈຸດສູງສຸດ 3 ແລະເຖິງຈຸດສູງສຸດ 4 (ແຖວທີ 2). ຮູ້ວ່າ, ມັນເຮັດໃຫ້ຄວາມຮູ້ສຶກທີ່ຈະປະຕິບັດ algorithm ພຽງແຕ່ສໍາລັບການປະສົມຂອງ 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 ໄວ້ເພື່ອປະມວນຜົນ (ເນື່ອງຈາກວ່າບໍ່ມີຂອບທີ່ນໍາຈາກ vertex 4 ກັບ vertex ອື່ນໆໃນກາຟ).

ອີກເທື່ອຫນຶ່ງ, ໃຫ້ພວກເຮົາເບິ່ງຢູ່ໃນ matrix W (ຮູບ 6).

ອີງຕາມ matrix W , ມີສາມເສັ້ນທາງໄປຫາຈຸດສູງສຸດ 3 ຈາກ vertexes 0 , 1 ແລະ 2 (ຖັນ #3), ແລະມີເສັ້ນທາງດຽວຈາກຈຸດສູງສຸດ 3 ຫາຈຸດ 4 (ແຖວ #3). ດັ່ງນັ້ນ, ພວກເຮົາມີເສັ້ນທາງການປຸງແຕ່ງດັ່ງຕໍ່ໄປນີ້:

ນີ້ແມ່ນການ iteration ສຸດທ້າຍຂອງ algorithm. ທັງໝົດທີ່ເຫຼືອແມ່ນການປັບປຸງເຊລ W[0,4] , W[1,4] , W[2,4] ດ້ວຍໄລຍະຫ່າງໃໝ່ ແລະກຳນົດເຊລ R[0,4] , R[1,4] , R[2,4] ເຖິງ 3 .

ນີ້ແມ່ນສິ່ງທີ່ພວກເຮົາມີຢູ່ໃນຕອນທ້າຍຂອງ algorithm (ຮູບ 7).

ດັ່ງທີ່ພວກເຮົາຮູ້ຈາກ ການຕອບທີ່ຜ່ານມາ , matrix W ປະຈຸບັນມີຄູ່ຂອງເສັ້ນທາງສັ້ນທີ່ສຸດໃນກຣາບ G ແຕ່ສິ່ງທີ່ເກັບໄວ້ໃນ matrix R ແມ່ນຫຍັງ?

ກັບບ້ານ

ທຸກໆຄັ້ງທີ່ພວກເຮົາພົບເສັ້ນທາງທີ່ສັ້ນທີ່ສຸດ, ພວກເຮົາປັບປຸງຕາລາງທີ່ສອດຄ້ອງກັນຂອງ matrix R ດ້ວຍຄ່າປະຈຸບັນຂອງ k . ໃນຂະນະທີ່ທໍາອິດ, ການປະຕິບັດນີ້ອາດຈະເບິ່ງຄືວ່າມີຄວາມລຶກລັບ, ມັນມີຄວາມຫມາຍທີ່ງ່າຍດາຍຫຼາຍ - ພວກເຮົາເກັບຮັກສາ vertex, ຈາກທີ່ພວກເຮົາໄດ້ໄປເຖິງຈຸດຫມາຍປາຍທາງ: i ⭢ k ⭢ j (ນີ້ພວກເຮົາໄປເຖິງ j ໂດຍກົງຈາກ k ).

ປັດຈຸບັນນີ້ແມ່ນສໍາຄັນ. ເນື່ອງຈາກວ່າການຮູ້ຈຸດສູງສຸດທີ່ພວກເຮົາມາຈາກເຮັດໃຫ້ພວກເຮົາສາມາດສ້າງເສັ້ນທາງຄືນໃຫມ່ໄດ້ໂດຍການຍ້າຍກັບຄືນໄປບ່ອນ (ເຊັ່ນ: lobster) ຈາກ vertex j ("ເຖິງ") ກັບ vertex i ("ຈາກ").

ນີ້ແມ່ນຄໍາອະທິບາຍຂໍ້ຄວາມຂອງ algorithm ເພື່ອສ້າງເສັ້ນທາງຈາກ i ຫາ j :

1. ກະກຽມອະເຣ Dynamic X ຫວ່າງເປົ່າ.
2. ເລີ່ມໂດຍການອ່ານຄ່າ z ຈາກເຊລ R[i,j] .
3. ຖ້າ z ແມ່ນ NO_EDGE , ເສັ້ນທາງຈາກ i ຫາ j ແມ່ນພົບແລະພວກເຮົາຄວນຈະດໍາເນີນຂັ້ນຕອນ #7.
4. Prepend z ກັບ dynamic array X .
5. ອ່ານຄ່າຂອງເຊລ R[i,z] ເປັນ z .
6. ເຮັດຊ້ໍາຂັ້ນຕອນ #3, #4, ແລະ #5 ຈົນກ່ວາເງື່ອນໄຂທາງອອກໃນ #3 ບັນລຸໄດ້.
7. Prepend i ກັບ X.
8. ຕື່ມ j ກັບ X .
9. ໃນປັດຈຸບັນ dynamic array X ມີເສັ້ນທາງຈາກ i ຫາ j .

ໃນລະຫັດ pseudo, ມັນເບິ່ງຄືວ່າງ່າຍດາຍກວ່າ:

 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 . ອີງຕາມສູດການຄິດໄລ່, ນີ້ຫມາຍຄວາມວ່າເສັ້ນທາງໄປສູ່ຈຸດສູງສຸດ 4 ຈາກຈຸດສູງສຸດ 3 (ສະແດງເປັນສີຟ້າ).

   
   

2. ເນື່ອງຈາກວ່າຄ່າຂອງ R[0,4] ບໍ່ແມ່ນ NO_EDGE , ພວກເຮົາດໍາເນີນການຕໍ່ໄປແລະອ່ານຄ່າຂອງ R[0,3] ເຊິ່ງຜົນໄດ້ຮັບໃນ 2 (ສະແດງຢູ່ໃນສີຂຽວ).

   
   

3. ອີກເທື່ອຫນຶ່ງ, ເນື່ອງຈາກວ່າຄ່າຂອງ R[0,3] ບໍ່ແມ່ນ NO_EDGE , ພວກເຮົາດໍາເນີນການຕໍ່ໄປແລະອ່ານຄ່າຂອງ R[0,2] ເຊິ່ງຜົນໄດ້ຮັບໃນ 1 (ສະແດງຢູ່ໃນ RED).

   
   

4. ໃນທີ່ສຸດ, ພວກເຮົາອ່ານຄ່າຂອງ R[0,1] , ເຊິ່ງສົ່ງຜົນໃຫ້ຄ່າ NO_EDGE , ຊຶ່ງຫມາຍຄວາມວ່າ, ບໍ່ມີຈຸດສູງສຸດຍົກເວັ້ນ 0 ແລະ 4 ທີ່ປະກອບສ່ວນເຂົ້າໃນເສັ້ນທາງ. ດັ່ງນັ້ນ, ເສັ້ນທາງທີ່ໄດ້ຮັບຜົນແມ່ນ: 0 ⭢ 1 ⭢ 2 ⭢ 3 ⭢ 4 ເຊິ່ງຖ້າທ່ານເບິ່ງເສັ້ນສະແດງຕົວຈິງແມ່ນກົງກັບເສັ້ນທາງທີ່ສັ້ນທີ່ສຸດຈາກຈຸດສູງສຸດ 0 ຫາຈຸດສູງສຸດ 4 .

ຜູ້ອ່ານທີ່ຄິດຈະຖາມວ່າ:

ມັນເປັນຄໍາຖາມທີ່ດີຫຼາຍ. ພວກເຮົາແນ່ໃຈວ່າຍ້ອນວ່າພວກເຮົາປັບປຸງ matrix R ດ້ວຍຄ່າໃຫມ່ເມື່ອພວກເຮົາປັບປຸງຄ່າເສັ້ນທາງທີ່ສັ້ນທີ່ສຸດໃນ matrix W . ດັ່ງນັ້ນໃນທີ່ສຸດ, ທຸກໆແຖວຂອງ matrix R ມີຂໍ້ມູນທີ່ກ່ຽວຂ້ອງກັບເສັ້ນທາງທີ່ສັ້ນທີ່ສຸດ. ບໍ່ມີຫຼາຍ, ບໍ່ຫນ້ອຍ.

ໃນປັດຈຸບັນ, ພວກເຮົາເຮັດກັບທິດສະດີ, ມັນແມ່ນເວລາປະຕິບັດ.

ການ​ປະ​ຕິ​ບັດ​ໃນ C#

ໃນ ບົດຂຽນທີ່ຜ່ານມາ , ນອກເຫນືອຈາກການຈັດຕັ້ງປະຕິບັດຕົ້ນສະບັບຂອງ Floyd-Warshall algorithm, ພວກເຮົາຍັງໄດ້ປະສົມປະສານການເພີ່ມປະສິດທິພາບຕ່າງໆ: ການສະຫນັບສະຫນູນເສັ້ນສະແດງ, ຂະຫນານ, ແລະ vectorization, ແລະໃນທີ່ສຸດ, ພວກເຮົາຍັງໄດ້ລວມເອົາພວກມັນທັງຫມົດ.

ບໍ່ມີເຫດຜົນທີ່ຈະເຮັດຊ້ໍາສິ່ງທັງຫມົດນີ້ໃນມື້ນີ້. ຢ່າງໃດກໍຕາມ, ຂ້າພະເຈົ້າຢາກຈະສະແດງໃຫ້ທ່ານເຫັນວິທີການປະສົມປະສານການທ່ອງຈໍາເສັ້ນທາງເຂົ້າໄປໃນຕົ້ນສະບັບແລະ vectorized (ໂດຍສະຫນັບສະຫນູນສໍາລັບກາຟ sparse) ສະບັບຂອງ algorithm.

ການປະສົມປະສານເຂົ້າໃນລະບົບສູດການຄິດໄລ່ຕົ້ນສະບັບ

ມັນອາດຈະເປັນການຍາກທີ່ຈະເຊື່ອແຕ່ເພື່ອປະສົມປະສານການຈື່ເສັ້ນທາງເຂົ້າໄປໃນສະບັບຕົ້ນສະບັບຂອງ algorithms, ທັງຫມົດທີ່ພວກເຮົາຕ້ອງເຮັດຄື:

1. ຂະຫຍາຍລາຍເຊັນຟັງຊັນເພື່ອລວມເອົາ R matrix ເປັນພາລາມິເຕີແຍກຕ່າງຫາກ – int[] routes .

   
   

2. ບັນທຶກ k ໄປຫາ routes ທຸກຄັ້ງທີ່ເສັ້ນທາງສັ້ນທີ່ສຸດມີການປ່ຽນແປງ (ເສັ້ນ: 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; } } } } }

ການປະສົມປະສານເຂົ້າໄປໃນ Vectorized Algorithm

ການລວມເຂົ້າກັນເປັນ vectorized (ໂດຍສະຫນັບສະຫນູນກຣາຟ sparse) ສະບັບໃຊ້ຄວາມພະຍາຍາມຫຼາຍເລັກນ້ອຍເພື່ອໃຫ້ສໍາເລັດ, ຢ່າງໃດກໍຕາມ, ຂັ້ນຕອນແນວຄວາມຄິດແມ່ນຄືກັນ:

1. ຂະຫຍາຍລາຍເຊັນຟັງຊັນເພື່ອລວມເອົາ R matrix ເປັນພາລາມິເຕີແຍກຕ່າງຫາກ – int[] routes .

   
   

2. ໃນແຕ່ລະ iteration, ເລີ່ມຕົ້ນ vector ໃຫມ່ຂອງຄ່າ k (ເສັ້ນ: 6).

   
   

3. ບັນທຶກ k ຄ່າ vector ໄປຫາ routes ທຸກຄັ້ງທີ່ເສັ້ນທາງສັ້ນທີ່ສຸດຖືກປ່ຽນ (ເສັ້ນ: 31-32).

   
   

4. ປັບປຸງສ່ວນທີ່ບໍ່ແມ່ນ vectorized ຂອງ algorithm ໃນລັກສະນະດຽວກັນທີ່ພວກເຮົາໄດ້ປັບປຸງ algorithm ຕົ້ນສະບັບ (ເສັ້ນ: 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

ການ​ເກັບ​ກໍາ​ຂໍ້​ມູນ​ເສັ້ນ​ທາງ​ເບິ່ງ​ຄື​ວ່າ​ສົມ​ເຫດ​ສົມ​ຜົນ​ພຽງ​ພໍ​ເນື່ອງ​ຈາກ​ວ່າ ... ດີ​ເປັນ​ຫຍັງ​ບໍ່​? ໂດຍ​ສະ​ເພາະ​ແມ່ນ​ໃນ​ເວ​ລາ​ທີ່​ມັນ​ເປັນ​ສະ​ນັ້ນ​ງ່າຍ​ທີ່​ຈະ​ເຊື່ອມ​ໂຍງ​ເຂົ້າ​ກັບ​ວິ​ທີ​ການ​ທີ່​ມີ​ຢູ່​ແລ້ວ​. ຢ່າງໃດກໍຕາມ, ໃຫ້ເບິ່ງວິທີການປະຕິບັດການລວມມັນໂດຍຄ່າເລີ່ມຕົ້ນ.

ນີ້ແມ່ນສອງຊຸດຂອງມາດຕະຖານ: ມີ ແລະບໍ່ມີ (ທັງສອງປະຕິບັດສະບັບຕົ້ນສະບັບ ແລະ vectorized ຂອງ algorithm). ມາດຕະຖານທັງໝົດຖືກປະຕິບັດໂດຍ BenchmarkDotNet v0.13.1 (.NET 6.0.4 x64) ໃນເຄື່ອງທີ່ຕິດຕັ້ງດ້ວຍໂປເຊດເຊີ Intel Core i5-6200U CPU 2.30GHz (Skylake) ແລະແລ່ນ Windows 10.

ການ​ທົດ​ລອງ​ທັງ​ຫມົດ​ແມ່ນ​ໄດ້​ຮັບ​ການ​ປະ​ຕິ​ບັດ​ກ່ຽວ​ກັບ​ການ​ກໍາ​ນົດ​ໄວ້​ລ່ວງ​ຫນ້າ​ຂອງ​ກາ​ຟ​ທີ່​ນໍາ​ໃຊ້​ໃນ ​ການ​ຕອບ​ທີ່​ຜ່ານ​ມາ ​: 300​, 600​, 1200​, 2400​, ແລະ 4800 vertexes​.

ຂ້າງລຸ່ມນີ້ແມ່ນຜົນໄດ້ຮັບ benchmark ທີ່ວິທີການ Baseline ແລະ BaselineWithRoutes ກົງກັນກັບສະບັບຕົ້ນສະບັບຂອງ algorithm ແລະ SpartialVectorOptimisations ແລະ SpartialVectorOptimisationsWithRoutes method ກົງກັບ vectorized (ສະຫນັບສະຫນູນສໍາລັບ sparse graphs) ສະບັບຂອງ algorithm.

ຜົນໄດ້ຮັບ Benchmark ບໍ່ງ່າຍດາຍທີ່ຈະຕີຄວາມຫມາຍ. ຖ້າທ່ານເບິ່ງໃກ້ຊິດ, ທ່ານຈະພົບເຫັນການປະສົມປະສານໃນເວລາທີ່ການເກັບກໍາເສັ້ນທາງຕົວຈິງເຮັດໃຫ້ algorithm ແລ່ນໄວຂຶ້ນຫຼືບໍ່ມີຜົນກະທົບທີ່ສໍາຄັນໃດໆ.

ນີ້ເບິ່ງຄືວ່າສັບສົນຫຼາຍ (ແລະຖ້າມັນເປັນ - ຂ້ອຍຂໍແນະນໍາໃຫ້ເຈົ້າຟັງ ລາຍການ ນີ້ກັບ Denis Bakhvalov ແລະ Andrey Akinshin ເພື່ອເຂົ້າໃຈດີຂຶ້ນວ່າສິ່ງທີ່ຫຍຸ້ງຍາກສາມາດສົ່ງຜົນກະທົບຕໍ່ການວັດແທກ). ການປະຕິບັດທີ່ດີທີ່ສຸດຂອງຂ້ອຍແມ່ນວ່າພຶດຕິກໍາ "ສັບສົນ" ແມ່ນເກີດມາຈາກການປະຕິບັດ cache ຂອງ CPU ທີ່ຍິ່ງໃຫຍ່ (ເພາະວ່າກາຟບໍ່ໃຫຍ່ພໍທີ່ຈະ saturate cache). ບາງສ່ວນ, ທິດສະດີນີ້ແມ່ນອີງໃສ່ຕົວຢ່າງ " ກ້າຫານ " ບ່ອນທີ່ພວກເຮົາສາມາດເຫັນການເຊື່ອມໂຊມທີ່ສໍາຄັນໃນກາຟທີ່ໃຫຍ່ທີ່ສຸດ. ຢ່າງໃດກໍຕາມ, ຂ້າພະເຈົ້າບໍ່ໄດ້ກວດສອບມັນ.

ໂດຍທົ່ວໄປ, benchmark ສະແດງໃຫ້ເຫັນວ່າຖ້າພວກເຮົາບໍ່ໄດ້ເວົ້າກ່ຽວກັບສະຖານະການທີ່ມີປະສິດທິພາບສູງແລະກາຟຂະຫນາດໃຫຍ່, ມັນເຫມາະສົມທີ່ຈະປະສົມປະສານການຈໍາແນກເສັ້ນທາງເຂົ້າໄປໃນທັງສອງ algorithms ໂດຍຄ່າເລີ່ມຕົ້ນ (ແຕ່ຈື່ໄວ້ວ່າມັນຈະບໍລິໂພກຄວາມຈໍາສອງເທົ່າເພາະວ່າພວກເຮົາຕ້ອງການ. ຈັດສັນສອງ matrices W ແລະ R ແທນທີ່ຈະເປັນຫນຶ່ງ).

ສິ່ງດຽວທີ່ເຫລືອແມ່ນການປະຕິບັດວິທີການສ້າງເສັ້ນທາງຄືນໃຫມ່.

ການປະຕິບັດວິທີການສ້າງເສັ້ນທາງຄືນໃຫມ່

ການປະຕິບັດວິທີການສ້າງເສັ້ນທາງໃຫມ່ໃນ C# ແມ່ນກົງໄປກົງມາແລະເກືອບທັງຫມົດສະທ້ອນໃຫ້ເຫັນເຖິງລະຫັດ pseudo-code ທີ່ສະແດງໃຫ້ເຫັນກ່ອນຫນ້ານີ້ (ພວກເຮົາໃຊ້ 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; }

ສູດການຄິດໄລ່ຂ້າງເທິງນີ້ບໍ່ສົມບູນແບບ ແລະແນ່ນອນສາມາດປັບປຸງໄດ້. ການປັບປຸງທີ່ງ່າຍດາຍທີ່ສຸດທີ່ພວກເຮົາສາມາດເຮັດໄດ້ແມ່ນການຈັດສັນ array ຂອງຂະຫນາດ 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 , ພວກເຮົາສະເຫມີຈະຕ້ອງ "ກັບຄືນ" ຂໍ້ມູນທີ່ພວກເຮົາດຶງມາຈາກ matrix 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.

ຮູ້ສຶກວ່າບໍ່ເສຍຄ່າເພື່ອທົດລອງ! ຄວາມເປັນໄປໄດ້ເກືອບບໍ່ຈຳກັດ!

ສະຫຼຸບ

ໃນບົດຂຽນນີ້, ພວກເຮົາໄດ້ເຈາະເລິກເຂົ້າໄປໃນທິດສະດີທີ່ຢູ່ເບື້ອງຫຼັງຂອງ Floyd-Warshall algorithm ແລະໄດ້ຂະຫຍາຍມັນດ້ວຍຄວາມເປັນໄປໄດ້ຂອງການຈື່ຈໍາເສັ້ນທາງທີ່ສັ້ນທີ່ສຸດ "ເສັ້ນທາງ." ຫຼັງຈາກນັ້ນ, ພວກເຮົາໄດ້ປັບປຸງການປະຕິບັດ C # (ຕົ້ນສະບັບແລະ vectorized) ຈາກ ຂໍ້ຄວາມທີ່ຜ່ານມາ . ໃນທີ່ສຸດ, ພວກເຮົາໄດ້ປະຕິບັດສອງສາມສະບັບຂອງສູດການຄິດໄລ່ເພື່ອສ້າງ "ເສັ້ນທາງ".

ພວກເຮົາໄດ້ເຮັດຊ້ໍາອີກຫຼາຍ, ແຕ່ໃນເວລາດຽວກັນ, ຂ້ອຍຫວັງວ່າເຈົ້າຈະພົບເຫັນສິ່ງໃຫມ່ແລະຫນ້າສົນໃຈໃນອັນນີ້. ນີ້ບໍ່ແມ່ນຈຸດຈົບຂອງບັນຫາເສັ້ນທາງສັ້ນທີ່ສຸດຄູ່ທັງໝົດ. ນີ້ແມ່ນພຽງແຕ່ການເລີ່ມຕົ້ນ.

ຂ້າ​ພະ​ເຈົ້າ​ຫວັງ​ວ່າ​ທ່ານ​ຈະ​ມີ​ຄວາມ​ສຸກ​ການ​ອ່ານ​, ແລະ​ພົບ​ທ່ານ​ໃນ​ຄັ້ງ​ຕໍ່​ໄປ​!