Dextra algoritmas ir jo įgyvendinimas
Matematikos ir kompiuterių mokslo srityje yraAtskira kryptis, vadinama grafikos teorija. Savo ruožtu nustatyti ir išspręsti įvairias užduotis, pavyzdžiui, rasti trumpiausią kelią tarp viršūnių. Vienas iš labiausiai paplitusių šios problemos sprendimo būdų tarp matematikų jau seniai yra Dijkstra algoritmas.
Manoma, kad į grafiką buvo įtraukta sąvokaLeonardo Eulerio naudojimas XVIII a. Būtent jis išreiškė vienos iš šios teorijos klasikinių problemų formulavimą ir sprendimą - apie septynis Koenigsbergo tiltus. Siekiant paaiškinti šios teorijos objektą, dažniausiai naudojama tokia analogija kaip judėjimas tarp skirtingų miestų. Tada plokštumos grafikas atspindės visą maršrutų schemą, kur viršūnės bus konkrečios taško (pvz., Miestų), o kraštai - kelias nuo vieno piko iki kito (panašus į kelių tarp miestų). Dijkstra algoritmas, be kitų metodų, gali padėti išspręsti šį klausimą.
Viena iš standartinių teorijos grafikos problemų yrakur reikia nustatyti sąnaudų atžvilgiu optimalų kelią tarp dviejų taškų. Jis gali būti sumažintas plokštumoje į grafiko, kuriame viršūnės-miestai, sprendimus sujungiami kraštais, kurie yra galimi keliai. Ir kiekvienas kelias turi savo ilgį, todėl per jį turėsite išleisti tam tikras lėšas. Ši suma yra lygi diagramos krašto svoriui. Tada praktiškai problema gali būti suformuluota taip: kaip nutiesti kelią iš vieno miesto į kitą, išleisti keliu minimalias lėšas.
Sprendimai
Norėdami išspręsti šią problemą, kai kuriealgoritmai, kurie tapo plačiai žinomi moksliniame pasaulyje. Pavyzdžiui, algoritmas Floyd - Warshell, Ford - Bellman. Dijkstra algoritmas taip pat yra klasikinis būdas rasti sprendimą. Jis taip pat gali būti naudojamas svoriui (žinomas kiekvieno krašto svoris), o atskirai. Norėdami rasti galutinį kelią, turite atlikti keletą žingsnių.
Dijkstra algoritmas
Šio metodo prasmė yra tokiavisi viršūniai yra apeinami, pradedant nuo nurodytosios, kiekvienai iš jų priskirta etiketė su tam tikra reikšme. Tada rezultatas bus tie viršūnių, kurių etiketės yra minimalios. Ant pirmojo pradinio žingsnio bus pažymėti vertės 0. Tada visi šių viršūnių yra laikomi, tai yra, tie, kurie gali būti pasiektas iš šaltinio. Jie priskiriami etiketėms, kurių vertė apibrėžiama kaip šaltinio suma ir kelio svoris. Nuo sekančio žingsnio viršuje, pasirinkite vieną, kuris turi mažiausią vertę etiketės ir studijavo visus, kad iš jo mes galime eiti nenaudojant tarpinių mazgų viršūnių. Nustatyta nauja etiketės vertė, lygi šaltinio viršūnės etiketei ir kelio svoriui. Jei gautoji vertė yra mažesnė už viršūnės etiketę, etiketė pasikeičia. Priešingu atveju pradinė vertė išlieka. Tuo pačiu metu į atskirą masyvą, kurio dimensija yra lygi viršūnių skaičius, ji saugo optimizavimo rezultatą, kurioje ir ryžtingai. Kad būtų įgyvendintas toks metodas kaip Dijkstra algoritmas, Pascal siūlo labai patogius įrankius. Algoritmas turi tą privalumą, kad jis gali būti lengvai programą, kuri turi mažą dydį. Tokių programinės įrangos pavyzdžių yra lengva rasti internete.
