Wicipedia

Algorithm Dijkstra

Algorithm Dijkstra (neu algorithm Llwybr Lleiaf Cyntaf Dijkstra)[1] yw algorithm gyfer canfod llwybrau byrraf rhwng fertigau mewn graff. Gall cael ei ddefnyddio, er enghraifft, canfod llwybrau lleiaf mewn rhwydweithiau ffyrdd. Fe’i crëwyd gan y gwyddonydd cyfrifiadurol Edsger W. Dijkstra ym 1956 a’i gyhoeddi tair blynedd yn ddiweddarach.[2][3][4]

Animeiddiad yn dangos algorithm Dijkstra ar ei waith.

Ar gyfer fertig ffynhonnell benodol yn y graff, mae'r algorithm yn dod o hyd i'r llwybr byrraf rhwng y fertig hwnnw a phob un arall,[5] gan gynhyrchu coeden llwybr byrraf. Gellir ei ddefnyddio hefyd ar gyfer dod o hyd i'r llwybrau byrraf o fertig sengl i fertig cyrchfan sengl trwy stopio'r yr algorithm unwaith y bydd y llwybr byrraf i'r fertig cyrchfan wedi'i ganfod. Dyma oedd fersiwn gwreiddiol Dijkstra.[4]

Er enghraifft, os yw nodau'r graff yn cynrychioli dinasoedd a chostau llwybr ymyl yn cynrychioli pellteroedd gyrru rhwng parau o ddinasoedd wedi'u cysylltu gan ffordd uniongyrchol (er symlrwydd, anwybyddu goleuadau coch a rhwystrau eraill), gellir defnyddio algorithm Dijkstra i ddod o hyd i'r llwybr byrraf rhwng un ddinas a'r holl ddinasoedd eraill.

Hanes

golygu

Meddyliodd Dijkstra am y broblem llwybr byrraf wrth weithio yn y Ganolfan Fathemategol yn Amsterdam ym 1956 fel rhaglennydd i arddangos galluoedd cyfrifiadur newydd o'r enw ARMAC.[6] Ei amcan oedd dewis problem ac ateb (a fyddai'n cael ei gynhyrchu gan gyfrifiadur) y gallai pobl nad ydynt yn gyfrifiaduron ei ddeall. Dyluniodd yr algorithm llwybr byrraf a'i weithredu yn ddiweddarach ar gyfer ARMAC ar gyfer map o 64 o ddinasoedd yn yr Iseldiroedd (64, fel y byddai 6 did yn ddigonol i amgodio rhif y ddinas).[3]

Blwyddyn yn ddiweddarach, daeth ar draws problem arall gan beirianwyr caledwedd a oedd yn gweithio ar gyfrifiadur nesaf y sefydliad: y broblem o leihau faint o wifren sydd ei angen i gysylltu'r pinnau ar banel cefn y peiriant. Fel ateb, fe wnaeth ail-ddarganfod yr algorithm Prim i ganfod coed rhychwantu lleiaf.[7][8] Cyhoeddodd Dijkstra yr algorithm ym 1959, ddwy flynedd ar ôl Prim a 29 mlynedd ar ôl y darganfyddwr gwreiddiol Jarník.[9][10]

Algorithm

golygu
 
Darlun o algorithm Dijkstra yn dod o hyd i lwybr o fertig cychwyn (chwith isaf, coch) i fertig amcan (dde uchaf, gwyrdd). Mae cylchoedd gwag yn cynrychioli'r set heb eu hymweld eto. Y cylchoedd lliw i'r fertigau sydd wedi eu hymweld, gyda lliw yn cynrychioli'r pellter: y gwyrddach, yr agosaf.

Caiff y fertig yr ydym yn dechrau arno ei alw'r fertig cychwynnol. Gadewch i bellter fertig Y fod y pellter o'r fertig cychwynnol i Y. Mae algorithm Dijkstra yn aseinio rhai gwerthoedd pellter cychwynnol i'r fertigau, ac yn ceisio eu gwella gam wrth gam.

  1. Marciwch bob fertig fel heb eu hymweld. Creu set o'r holl nodau heb eu hymweld, o'r enw'r set heb eu hymweld.
  2. Aseiniwch werth pellter petrus i bob fertig: gosodwch ef i sero ar gyfer ein fertig cychwynnol ac i anfeidredd ar gyfer pob fertig arall. Gosodwch y fertig cychwynnol fel y fertig presennol.[11]
  3. Ar gyfer y fertig presennol, ystyriwch ei holl gymdogion heb eu hymweld, a chyfrifwch eu pellteroedd petrus trwy'r fertig presennol. Cymharwch y pellter petrus newydd ei gyfrifo â'r gwerth pellter cyfredol, a aseiniwch iddo'r un lleiaf. Er enghraifft, os yw'r fertig cyfredol A wedi'i farcio â phellter o 6, a bod gan yr ymyl sy'n ei gysylltu â chymydog B hyd 2, yna'r pellter i B trwy A fydd 6 + 2 = 8. Os oedd B wedi'i farcio o'r blaen gyda phellter mwy nag 8 yna newidiwch ef i 8. Fel arall, cadwch y gwerth pellter cyfredol.
  4. Pan fyddwn wedi gorffen ystyried holl gymdogion y fertig presennol sydd heb eu hymweld, marciwch y fertig presennol fel wedi ei ymweld, a'i dynnu o'r set heb eu hymweld. Ni fydd fertig sydd wedi ei ymweld byth yn cael ei wirio eto.
  5. Os yw'r fertig cyrchfan wedi'i farcio fel wedi ei ymweld (wrth gynllunio llwybr rhwng dau nod penodol), neu os yw'r pellter petrus lleiaf ymhlith y nodau yn y set heb eu hymweld yn anfeidredd (wrth gynhyrchu coeden pellter lleiaf), yna stopiwch. Mae'r algorithm wedi gorffen.
  6. Fel arall, dewiswch y nod heb ei ymweld sydd wedi'i farcio â'r pellter petrus lleiaf, gosodwch fel y "fertig presennol" newydd, ac ewch yn ôl i gam 3.

Trafodaeth

golygu

Nid yw'r algorithm hwn yn gwneud unrhyw ymdrech i "archwilio" yn uniongyrchol tuag at y gyrchfan. Yn hytrach, yr unig ystyriaeth wrth bennu'r fertig "presennol" nesaf yw ei bellter o'r fertig cychwyn. Felly mae'r algorithm hwn yn ehangu tuag allan o'r man cychwyn, gan ystyried ar y pryd pob nod sy'n agosach o ran pellter llwybr byrraf nes iddo gyrraedd y gyrchfan. Wrth ddeall yr algorithm fel hyn, mae'n amlwg sut mae'r algorithm bendant yn dod o hyd i'r llwybr byrraf. Fodd bynnag, mae hefyd yn datgelu un o wendidau'r algorithm: mae'n araf mewn rhai topolegau.

Cymwysiadau

golygu

Mae llwybrau cost leiaf yn cael eu cyfrifo er enghraifft er mwyn sefydlu traciau llinellau trydan neu bibellau olew. Defnyddiwyd yr algorithm hefyd i gyfrifo'r llwybrau troed pellter hir gorau posibl yn Ethiopia a'u cyferbynnu â beth ddigwyddir mewn gwirionedd.[12]

Cyfeiriadau

golygu
  1. ↑ "OSPF Incremental SPF". Cisco. Archifwyd o'r gwreiddiol ar 2019-04-19. Cyrchwyd 2020-11-03.
  2. ↑ Richards, Hamilton. "Edsger Wybe Dijkstra". A.M. Turing Award. Association for Computing Machinery. Cyrchwyd 16 October 2017. At the Mathematical Centre a major project was building the ARMAC computer. For its official inauguration in 1956, Dijkstra devised a program to solve a problem interesting to a nontechnical audience: Given a network of roads connecting cities, what is the shortest route between two designated cities?
  3. ↑ 3.0 3.1 Frana, Phil (August 2010). "An Interview with Edsger W. Dijkstra". Communications of the ACM 53 (8): 41–47. doi:10.1145/1787234.1787249.
  4. ↑ 4.0 4.1 Dijkstra, E. W. (1959). "A note on two problems in connexion with graphs". Numerische Mathematik 1: 269–271. doi:10.1007/BF01386390. http://www-m3.ma.tum.de/twiki/pub/MN0506/WebHome/dijkstra.pdf.
  5. ↑ Mehlhorn, Kurt; Sanders, Peter (2008). "Chapter 10. Shortest Paths". Algorithms and Data Structures: The Basic Toolbox. Springer. doi:10.1007/978-3-540-77978-0. ISBN 978-3-540-77977-3.
  6. ↑ "ARMAC". Unsung Heroes in Dutch Computing History. 2007. Archifwyd o'r gwreiddiol ar 13 November 2013.
  7. ↑ Dijkstra, Edsger W., Reflections on "A note on two problems in connexion with graphs, https://www.cs.utexas.edu/users/EWD/ewd08xx/EWD841a.PDF
  8. ↑ Tarjan, Robert Endre (1983), Data Structures and Network Algorithms, CBMS_NSF Regional Conference Series in Applied Mathematics, 44, Society for Industrial and Applied Mathematics, p. 75, "The third classical minimum spanning tree algorithm was discovered by Jarník and rediscovered by Prim and Dikstra; it is commonly known as Prim's algorithm."
  9. ↑ Prim, R.C. (1957). "Shortest connection networks and some generalizations". Bell System Technical Journal 36 (6): 1389–1401. Bibcode 1957BSTJ...36.1389P. doi:10.1002/j.1538-7305.1957.tb01515.x. http://bioinfo.ict.ac.cn/~dbu/AlgorithmCourses/Lectures/Prim1957.pdf. Adalwyd 18 July 2017.
  10. ↑ V. Jarník: O jistém problému minimálním [About a certain minimal problem], Práce Moravské Přírodovědecké Společnosti, 6, 1930, pp. 57–63. (in Czech)
  11. ↑ Gass, Saul; Fu, Michael (2013). Gass, Saul I; Fu, Michael C. eds. "Dijkstra's Algorithm". Encyclopedia of Operations Research and Management Science (Springer) 1. doi:10.1007/978-1-4419-1153-7. ISBN 978-1-4419-1137-7.
  12. ↑ Nyssen, J., Tesfaalem Ghebreyohannes, Hailemariam Meaza, Dondeyne, S., 2020. Exploration of a medieval African map (Aksum, Ethiopia) – How do historical maps fit with topography? In: De Ryck, M., Nyssen, J., Van Acker, K., Van Roy, W., Liber Amicorum: Philippe De Maeyer In Kaart. Wachtebeke (Belgium): University Press: 165-178.
Wedi dod o "https://cy.wikipedia.org/w/index.php?title=Algorithm_Dijkstra&oldid=12082707"