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

ແນະນຳ

ໃນ ບົດຂຽນທີ່ຜ່ານມາ , ພວກເຮົາໄດ້ເຫັນວິທີການແກ້ໄຂບັນຫາເສັ້ນທາງສັ້ນທີ່ສຸດຄູ່ທັງຫມົດໂດຍໃຊ້ . ພວກເຮົາຍັງໄດ້ຄົ້ນຫາຫຼາຍວິທີເພື່ອປັບປຸງປະສິດທິພາບຂອງສູດການຄິດໄລ່ໂດຍໃຊ້ຂະໜານ ແລະ 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 .

ຂັ້ນຕອນ	ເສັ້ນທາງ	ຄໍາເຫັນ
1	0 ⭢ 1 ⭢ 2	ພົບເສັ້ນທາງ. ໄລຍະທາງ = 3 (ບໍ່ມີຫຍັງເລີຍ)
2	0 ⭢ 1 ⭢ 4	ພົບເສັ້ນທາງ. ໄລຍະຫ່າງ = 8 (ແມ່ນ 10).

ພວກເຮົາໄດ້ພົບເຫັນສອງເສັ້ນທາງ: ເສັ້ນທາງໃຫມ່ ( 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 .

ຂັ້ນຕອນ	ເສັ້ນທາງ	ຄໍາເຫັນ
1	0 ⭢ 2 ⭢ 3	ພົບເສັ້ນທາງ. ໄລຍະທາງ = 4 (ບໍ່ມີຫຍັງເລີຍ)
2	0 ⭢ 2 ⭢ 4	ພົບເສັ້ນທາງ. ໄລຍະທາງ = 6 (ເທົ່າກັບ 8)
3	1 ⭢ 2 ⭢ 3	ພົບເສັ້ນທາງ. ໄລຍະທາງ = 2 (ບໍ່ມີຫຍັງເລີຍ)
4	1 ⭢ 2 ⭢ 4	ພົບເສັ້ນທາງ. ໄລຍະທາງ = 4 (ເທົ່າກັບ 6)

ດັ່ງທີ່ພວກເຮົາໄດ້ເຮັດໃນເມື່ອກ່ອນ, ພວກເຮົາກໍາລັງປັບປຸງຈຸລັງ 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). ດັ່ງນັ້ນ, ພວກເຮົາມີເສັ້ນທາງການປຸງແຕ່ງດັ່ງຕໍ່ໄປນີ້:

ຂັ້ນຕອນ	ເສັ້ນທາງ	ຄໍາເຫັນ
1	0 ⭢ 3 ⭢ 4	ພົບເສັ້ນທາງ. ໄລຍະທາງ = 5 (ເທົ່າກັບ 6)
2	1 ⭢ 3 ⭢ 4	ພົບເສັ້ນທາງ. ໄລຍະທາງ = 3 (ເທົ່າກັບ 4)
3	2 ⭢ 3 ⭢ 4	ພົບເສັ້ນທາງ. ໄລຍະທາງ = 2 (ເທົ່າກັບ 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). ມາດຕະຖານທັງໝົດຖືກປະຕິບັດໂດຍ 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.

ວິທີການ	ຂະໜາດ	ສະເລ່ຍ (ms)	ຄວາມຜິດພາດ (ms)	StdDev (ms)
ພື້ນຖານ	300	40.233	0.0572	0.0477
BaselineWithRoutes	300	40.349	0.1284	0.1201
ການເພີ່ມປະສິດທິພາບ SpartialVector	300	4.472	0.0168	0.0140
SpartialVector Optimisations WithRoutes	300	4.517	0.0218	0.0193
ພື້ນຖານ	600	324.637	5.6161	4.6897
BaselineWithRoutes	600	321.173	1.4339	1.2711
ການເພີ່ມປະສິດທິພາບ SpartialVector	600	32.133	0.2151	0.1679
SpartialVector Optimisations WithRoutes	600	34.646	0.1286	0.1073
ພື້ນຖານ	1200	2,656.024	6.9640	5.8153
BaselineWithRoutes	1200	2,657.883	8.8814	7.4164
ການເພີ່ມປະສິດທິພາບ SpartialVector	1200	361.435	2.5877	2.2940
SpartialVector Optimisations WithRoutes	1200	381.625	3.6975	3.2777
ພື້ນຖານ	2400	21,059.519	38.2291	33.8891
BaselineWithRoutes	2400	20,954.852	56.4719	50.0609
ການເພີ່ມປະສິດທິພາບ SpartialVector	2400	3,029.488	໑໒.໑໕໒໘	11.3677
SpartialVector Optimisations WithRoutes	2400	3,079.006	8.6125	7.1918
ພື້ນຖານ	4800	164,869.803	547.6675	427.5828
BaselineWithRoutes	4800	184,305. 980	210.9535	164.6986
ການເພີ່ມປະສິດທິພາບ SpartialVector	4800	21,882.379	200.2820	177.5448
SpartialVector Optimisations WithRoutes	4800	21,004.612	79.8752	70.8073

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

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

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

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