STUDY OF ALGORITHMS FOR SEARCHING THE OPTIMAL PATH
DOI:
https://doi.org/10.26906/SUNZ.2024.2.067Keywords:
аlgorithm, programming, distribution, graph, optimal path, artificial intelligenceAbstract
Extensive areas of application of optimal path search algorithms lead to the need for their thorough research. The purpose of this work is to conduct a study of existing methods of finding the optimal path depending on the characteristics of input data and optimization goals. The article considers such types of algorithms as: algorithms based on graphs and based on heuristics. In the work, an analysis of the scope of application of the above algorithms was carried out. The advantages and disadvantages of using algorithms are defined depending on the area of use. The complexity of the application, depending on the computing power and the time of processing the input data, was studied. The presented studies make it possible to obtain information about the reliability of the results of the considered algorithms depending on the input set of parameters for calculation.Downloads
References
Barnes E. R. An algorithm for partitioning the nodes of a graph // SIAM J. Algebraic Discrete Methods. – 1982. – Vol. 4, no. 3. – P. 541-550.
Коваленко А. А., Кучук Г. А. Методи синтезу інформаційної та технічної структур системи управління об’єктом критичного застосування. Сучасні інформаційні системи. 2018. Т. 2, № 1. С. 22–27. DOI: https://doi.org/10.20998/2522-9052.2018.1.04
Свиридов А. C., Коваленко А. А., Кучук Г. А. Метод перерозподілу пропускної здатності критичної ділянки мережі на основі удосконалення ON/OFF-моделі трафіку. Сучасні інформаційні системи. 2018. Т. 2, № 2. С. 139–144. DOI: https://doi.org/10.20998/2522-9052.2018.2.24
Главчева Ю. М., Главчев М. І., Каніщева О. В., Кучук Г. А. Розробка підходу для ранжування академічних установ за показниками наукової діяльності. Сучасні інформаційні системи. 2019. Т. 3, № 1. С. 63–70.
Dun, B., Zakovorotnyi, O. and Kuchuk, N. (2023), “Generating currency exchange rate data based on Quant-Gan model”, Advanced Information Systems, Vol. 7, no. 2, pp. 68–74, doi: https://doi.org/10.20998/2522-9052.2023.2.10
Datsenko, S. and Kuchuk, H. (2023), “Biometric authentication utilizing convolutional neural networks”, Advanced Information Systems, Vol. 7, no. 2, pp. 87–91, doi: https://doi.org/10.20998/2522-9052.2023.2.12
Petrovska, I. and Kuchuk, H. (2023), “Adaptive resource allocation method for data processing and security in cloud environment”, Advanced Information Systems, Vol. 7, No. 3, pp. 67–73, doi: https://doi.org/10.20998/2522-9052.2023.3.10
Krepych, S., & Spivak, I. (2021). Improvement of svd algorithm to increase the efficiency of recommendation systems. Advanced Information Systems, 5(4), 55–59. https://doi.org/10.20998/2522-9052.2021.4.08
Кучук Г.А. Мінімізація завантаження каналів зв'язку обчислювальної мережі / Г.А. Кучук // Системи обробки інформації. – Х.: НАНУ, ПАНМ, ХВУ, 1998. – Вип. 1(5). – С. 149-154.
Shmatko, O., Kolomiitsev, O., Rekova, N., Kuchuk, N. and Matvieiev, O. (2023), “Designing and evaluating dl-model for vulnerability detection in smart contracts”, Advanced Information Systems, vol. 7, no. 4, pp. 41–51. doi: https://doi.org/10.20998/2522-9052.2023.4.05.
Fakcharoenphol J., Rao S. Planar graphs, negative weight edges, shortest paths, and near linear time // Proc. 42nd IEEE Symp. Foundations of Computer Science. – 2001. – P. 232-241.
Goldberg A. V., Harrelson C. Computing the shortest path: A∗-search meets graph theory // Proc. Sixteenth Annual ACM–SIAM Symp. on Discrete Algorithms, January 23-25, Vancouver, BC (2005). – P. 156-165.
Timothy M. Chan. More algorithms for all-pairs shortest paths in weightedgraphs. In STOC07, pages 590–598, 2007.
Seth Pettie. A new approach to all-pairs shortest paths on real-weightedgraphs. Theoretical Computer Science, 312:47–74, 2004.
Edward M. Reingold, Jurg Nievergelt, and Narsingh Deo. CombinatorialAlgorithms: Theory and Practice. Prentice-Hall, Inc., 1977.
