ESTIMATIONS OF THE ASYMPTOTIC COMPLEXITY OF APPLIED MULTIPLE TRANSPORT ALGORITHMS WHEN DIVISIONING THEM INTO CLUSTERS
ID елемента: 22416
2026/05/05
Цитування
eNUPPIR (). ESTIMATIONS OF THE ASYMPTOTIC COMPLEXITY OF APPLIED MULTIPLE TRANSPORT ALGORITHMS WHEN DIVISIONING THEM INTO CLUSTERS. https://enuppir.politeh.duckdns.org/item/22416
eNUPPIR. "ESTIMATIONS OF THE ASYMPTOTIC COMPLEXITY OF APPLIED MULTIPLE TRANSPORT ALGORITHMS WHEN DIVISIONING THEM INTO CLUSTERS." Web. . <https://enuppir.politeh.duckdns.org/item/22416>.
eNUPPIR. "ESTIMATIONS OF THE ASYMPTOTIC COMPLEXITY OF APPLIED MULTIPLE TRANSPORT ALGORITHMS WHEN DIVISIONING THEM INTO CLUSTERS." Accessed . https://enuppir.politeh.duckdns.org/item/22416.
Скопійовано в буфер обміну
Властивості
Назва
Англійська
ESTIMATIONS OF THE ASYMPTOTIC COMPLEXITY OF APPLIED MULTIPLE TRANSPORT ALGORITHMS WHEN DIVISIONING THEM INTO CLUSTERS
Російська
.
Українська
ОЦІНКИ АСИМПТОТИЧНОЇ СКЛАДНОСТІ ПРИКЛАДНИХ МНОЖИННИХ ТРАНСПОРТНИХ АЛГОРИТМІВ ПРИ ПОДІЛІ ЇХ НА КЛАСТЕРИ
Опис
Англійська
Applied multiple transport algorithms are usually heuristic and overly complex. Depending on the chosen heuristic of the algorithm, the real time of the software implementation depends on the programming language, the structure of the input data representation and the algorithmic complexity of the solution. The research is based on the use of the provisions of discrete mathematics and graph theory. It is shown that by analyzing asymptotic complexity it is possible to determine effective heuristics. Refinement of applied problem models also contributes to reducing complexity. Since the multiplicity of transport tasks is contained in a discrete coverage or in the functionality of multiple vehicles, it is possible to simplify the algorithm by decomposing them into clusters for which the conditions and constraints of the standard transport task apply. The features of geometric and combinatorial decomposition into clusters are presented. The formalization of cluster construction algorithms for multiple transport problems is provided. A comparative analysis of optimal and heuristic algorithms for solving multiple transport problems is carried out. The hierarchy of asymptotic complexity of heuristic algorithms is determined and the possibilities of their decomposition into clusters are analyzed, which simplify the solution of multiple applied transport problems. The notation of the complexity of the solution and the possibility of their evaluation by the objective function of the selected algorithm or by its approximation are provided. An analysis of the asymptotic complexity of heuristic algorithms for Big-O notation has been carried out. It has been shown that algorithms with a complexity not exceeding polynomial are suitable for implementation, and the use of algorithms with an exponential complexity estimate and higher is undesirable. It is noted that asymptotic estimates of algorithm complexity are suitable for large-dimensional tasks, and for tasks of small dimension, control runs are appropriate.
Українська
Прикладні множинні транспортні алгоритми, як правило, є евристичними та надскладними. За обраною евристикою алгоритму, реальний час на програмну реалізацію залежить від мови програмування, структури представлення вхідних даних та алгоритмічної складності рішення. Дослідження базуються на використанні положень дискретної математики та теорії графів. Показано, що шляхом аналізу асимптотичної складності можливо визначити ефективну евристику. Уточнення моделей прикладних завдань, також, сприяють зменшенню складності. Оскільки, множинність транспортних завдань міститися у дискретному покритті або у функціоналі множинних транспортних засобів, то можливим є спрощення алгоритму шляхом їх декомпозиції на кластери для яких діють умови та обмеження стандартного транспортного завдання. Наведено особливості геометрично та комбінаторного розкладання на кластери. Надано формалізацію алгоритмів побудови кластерів для множинних транспортних завдань. Проведено порівняльний аналіз оптимальних та евристичних алгоритмів вирішення множинних транспортних завдань. Визначено ієрархію асимптотичної складності евристичних алгоритмів та проаналізовано можливості їх декомпозицій на кластери за якими досягається спрощення вирішення множинних прикладних транспортних завдань. Надано нотації складності рішення та можливості їх оцінки за цільовою функцією обраного алгоритму або за її апроксимацією. Здійснено аналіз асимптотичної складності евристичних алгоритмів для Big-O нотації. Показано, що придатними для реалізації є алгоритми, складності яких не перевищують поліноміальної, а застосування алгоритмів, які мають експонентну оцінку складності та вище є не бажаним. Зазначено, що асимптотичні оцінки складності алгоритму придатні для великих за розмірністю завдань, а для завдань невеликої розмірності доцільними є контрольні прогони.
Автор
Українська
Karlov, Volodymyr
Українська
Kolomiitsev, Oleksii
Українська
Kuznietsov, Oleksandr
Українська
Biesova, Oksana
Українська
Biesova, Anna
Тематика
Англійська
asymptotic complexity
Англійська
heuristics
Англійська
clusters
Англійська
logistics
Англійська
multiple transportation tasks
Англійська
notations
Англійська
emergency care system
Англійська
vehicles
Англійська
objective function
Російська
17
Українська
асимптотична складність
Українська
евристика
Українська
кластери
Українська
логістичне забезпечення
Українська
множинні транспортні завдання
Українська
нотації
Українська
система невідкладної допомоги
Українська
транспортні засоби
Українська
цільова функція
Видавництво
Українська
Національний університет «Полтавська політехніка імені Юрія Кондратюка»
Тип
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion
Українська
Рецензована Стаття
Формат
application/pdf
Ідентифікатор
https://journals.nupp.edu.ua/sunz/article/view/4108
10.26906/SUNZ.2025.4.082
Джерело
Англійська
Control, Navigation and Communication Systems. Academic Journal; Vol. 4 No. 82 (2025): Control, Navigation and Communication Systems; 82-87
Російська
Системы управления, навигации и связи. Сборник научных трудов; Том 4 № 82 (2025): Системи управління, навігації та зв'язку; 82-87
Українська
Системи управління, навігації та зв’язку. Збірник наукових праць; Том 4 № 82 (2025): Системи управління, навігації та зв'язку; 82-87
2073-7394
10.26906/SUNZ.2025.4
2025. №4 (82)
Мова
uk
Відношення
https://journals.nupp.edu.ua/sunz/article/view/4108/3438
Права
Українська
Авторське право (c) 2025 Volodymyr Karlov, Oleksii Kolomiitsev, Oleksandr Kuznietsov, Oksana Biesova, Anna Biesova
Українська
http://creativecommons.org/licenses/by-nc/4.0
Інформація про метадані
Створено
2026-5-5 11:56
Остання зміна
2026-5-5 11:56
ID елемента
#22416