Neidio i'r cynnwys

Algorithm Dijkstra

Oddi ar Wicipedia
Fersiwn a roddwyd ar gadw am 18:59, 3 Tachwedd 2020 gan Gerian2 (sgwrs | cyfraniadau)
(gwahan) ← Fersiwn hŷn | Fersiwn diweddaraf (gwahan) | Fersiwn diweddarach → (gwahan)
Animeiddiad yn dangos algorithm Dijkstra ar ei waith.

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 crewyd gan y gwyddonydd cyfrifiadurol Edsger W. Dijkstra ym 1956 a’i gyhoeddi dair blynedd yn ddiweddarach.[2][3][4]


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 goeden 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 canfod. 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.


Mae algorithm Dijkstra yn defnyddio strwythur data ar gyfer storio a chwestiynu datrysiadau rhannol wedi'u didoli yn ôl pellter o'r cychwyn cyntaf. Er bod yr algorithm gwreiddiol yn defnyddio ciw min-flaenoriaeth ac yn rhedeg mewn amser (lle yw nifer y nodau a yw nifer yr ymylon), gellir ei weithredu hefyd yn defnyddio arae. Rhoddir syniad yr algorithm hwn hefyd yn Leyzorek et al. 1957 . Fredman & Tarjan 1984 cynnig defnyddio ciw min-flaenoriaeth domen Fibonacci i wneud y gorau o'r cymhlethdod amser rhedeg i . Dyma'n anghymesur yr algorithm llwybr byrraf un ffynhonnell cyflymaf y gwyddys amdano ar gyfer graffiau cyfeiriedig mympwyol gyda phwysau an-negyddol heb eu rhwymo. Fodd bynnag, yn wir gellir gwella achosion arbenigol (megis pwysau wedi'u ffinio / cyfanrif, graffiau acyclic dan gyfarwyddyd ac ati) ymhellach fel y manylir mewn amrywiadau Arbenigol .

Hanes

Meddyliodd Dijkstra am y broblem llwybr fyrraf 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

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 y 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 presenol. 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

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 deall 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 ddatgelu un o wendidau'r algorithm: mae'n araf mewn rhai topolegau.

Cymwysiadau

Mae llwybrau cost lleiaf yn cael eu cyfrifo er enghraifft ier mwyn sefydlu traciau llinellau trydan neu biblinellau 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

  1. ↑ "OSPF Incremental SPF". Cisco.
  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=10788110"