ДОСЛІДЖЕННЯ АЛГОРИТМІВ ПОШУКУ ОПТИМАЛЬНОГО ШЛЯХУ
Ключові слова:
алгоритм, програмування, розподіл ресурсів, граф, оптимальний шлях
Анотація
Обширні області застосування алгоритмів пошуку оптимального шляху призводить до необхідності ретельного їх дослідження. Метою даної роботи є проведення дослідження існуючих методів пошуку оптимального шляху в залежності від особливостей вхідних даних та цілей оптимізації. У статі розглядаються такі види алгоритмів як: алгоритми на основі графів та на основі евристики. У роботі було проведений аналів сфери застосування наведених алгоритмів. Визначені переваги та недоліки використання алгоритмів в залежності від області використання. Досліджено складності застосування в залежності від обчислювальних потужностей та часу обробки вхідних даних. Представлені дослідження дають змогу отримати інформацію про достовірність результатів роботи алгоритмів що розглядаються в залежності від вхідної сукупності параметрів для обчислення.Завантаження
Дані про завантаження поки що недоступні.
Посилання
1. 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.
2. Коваленко А. А., Кучук Г. А. Методи синтезу інформаційної та технічної структур системи управління об’єктом критичного застосування. Сучасні інформаційні системи. 2018. Т. 2, № 1. С. 22–27. DOI: https://doi.org/10.20998/2522-9052.2018.1.04
3. Свиридов А. C., Коваленко А. А., Кучук Г. А. Метод перерозподілу пропускної здатності критичної ділянки мережі на основі удосконалення ON/OFF-моделі трафіку. Сучасні інформаційні системи. 2018. Т. 2, № 2. С. 139–144. DOI: https://doi.org/10.20998/2522-9052.2018.2.24
4. Главчева Ю. М., Главчев М. І., Каніщева О. В., Кучук Г. А. Розробка підходу для ранжування академічних установ за показниками наукової діяльності. Сучасні інформаційні системи. 2019. Т. 3, № 1. С. 63–70.
5. 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
6. 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
7. 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
8. 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
9. Кучук Г.А. Мінімізація завантаження каналів зв'язку обчислювальної мережі / Г.А. Кучук // Системи обробки інформації. – Х.: НАНУ, ПАНМ, ХВУ, 1998. – Вип. 1(5). – С. 149-154.
10. 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.
11. 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.
12. 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.
13. Timothy M. Chan. More algorithms for all-pairs shortest paths in weightedgraphs. In STOC07, pages 590–598, 2007.
14. Seth Pettie. A new approach to all-pairs shortest paths on real-weightedgraphs. Theoretical Computer Science, 312:47–74, 2004.
15. Edward M. Reingold, Jurg Nievergelt, and Narsingh Deo. CombinatorialAlgorithms: Theory and Practice. Prentice-Hall, Inc., 1977.
2. Коваленко А. А., Кучук Г. А. Методи синтезу інформаційної та технічної структур системи управління об’єктом критичного застосування. Сучасні інформаційні системи. 2018. Т. 2, № 1. С. 22–27. DOI: https://doi.org/10.20998/2522-9052.2018.1.04
3. Свиридов А. C., Коваленко А. А., Кучук Г. А. Метод перерозподілу пропускної здатності критичної ділянки мережі на основі удосконалення ON/OFF-моделі трафіку. Сучасні інформаційні системи. 2018. Т. 2, № 2. С. 139–144. DOI: https://doi.org/10.20998/2522-9052.2018.2.24
4. Главчева Ю. М., Главчев М. І., Каніщева О. В., Кучук Г. А. Розробка підходу для ранжування академічних установ за показниками наукової діяльності. Сучасні інформаційні системи. 2019. Т. 3, № 1. С. 63–70.
5. 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
6. 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
7. 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
8. 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
9. Кучук Г.А. Мінімізація завантаження каналів зв'язку обчислювальної мережі / Г.А. Кучук // Системи обробки інформації. – Х.: НАНУ, ПАНМ, ХВУ, 1998. – Вип. 1(5). – С. 149-154.
10. 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.
11. 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.
12. 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.
13. Timothy M. Chan. More algorithms for all-pairs shortest paths in weightedgraphs. In STOC07, pages 590–598, 2007.
14. Seth Pettie. A new approach to all-pairs shortest paths on real-weightedgraphs. Theoretical Computer Science, 312:47–74, 2004.
15. Edward M. Reingold, Jurg Nievergelt, and Narsingh Deo. CombinatorialAlgorithms: Theory and Practice. Prentice-Hall, Inc., 1977.
Опубліковано
2024-04-30
Як цитувати
Bulba S. Дослідження алгоритмів пошуку оптимального шляху / S. Bulba, O. Solovyova, Y. Semerenko // Системи управління, навігації та зв’язку. Збірник наукових праць. – Полтава: ПНТУ, 2024. – Т. 2 (76). – С. 67-69. – doi:https://doi.org/10.26906/SUNZ.2024.2.067.
Розділ
Інформаційні технології
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
