Search academic texts

Information × Registration Number 2125U004499, Article popup.category Стаття, Опубліковано, Рецензована стаття Title ESTIMATIONS OF THE ASYMPTOTIC COMPLEXITY OF APPLIED MULTIPLE TRANSPORT ALGORITHMS WHEN DIVISIONING THEM INTO CLUSTERS popup.author Karlov VolodymyrKolomiitsev OleksiiKuznietsov OleksandrBiesova OksanaBiesova AnnaKarlov VolodymyrKolomiitsev OleksiiKuznietsov OleksandrBiesova OksanaBiesova Anna popup.publication 02-12-2025 popup.source_user Національний університет «Полтавська політехніка імені Юрія Кондратюка» popup.source https://journals.nupp.edu.ua/sunz/article/view/4108 popup.publisher Національний університет «Полтавська політехніка імені Юрія Кондратюка» Description Прикладні множинні транспортні алгоритми, як правило, є евристичними та надскладними. За обраною евристикою алгоритму, реальний час на програмну реалізацію залежить від мови програмування, структури представлення вхідних даних та алгоритмічної складності рішення. Дослідження базуються на використанні положень дискретної математики та теорії графів. Показано, що шляхом аналізу асимптотичної складності можливо визначити ефективну евристику. Уточнення моделей прикладних завдань, також, сприяють зменшенню складності. Оскільки, множинність транспортних завдань міститися у дискретному покритті або у функціоналі множинних транспортних засобів, то можливим є спрощення алгоритму шляхом їх декомпозиції на кластери для яких діють умови та обмеження стандартного транспортного завдання. Наведено особливості геометрично та комбінаторного розкладання на кластери. Надано формалізацію алгоритмів побудови кластерів для множинних транспортних завдань. Проведено порівняльний аналіз оптимальних та евристичних алгоритмів вирішення множинних транспортних завдань. Визначено ієрархію асимптотичної складності евристичних алгоритмів та проаналізовано можливості їх декомпозицій на кластери за якими досягається спрощення вирішення множинних прикладних транспортних завдань. Надано нотації складності рішення та можливості їх оцінки за цільовою функцією обраного алгоритму або за її апроксимацією. Здійснено аналіз асимптотичної складності евристичних алгоритмів для Big-O нотації. Показано, що придатними для реалізації є алгоритми, складності яких не перевищують поліноміальної, а застосування алгоритмів, які мають експонентну оцінку складності та вище є не бажаним. Зазначено, що асимптотичні оцінки складності алгоритму придатні для великих за розмірністю завдань, а для завдань невеликої розмірності доцільними є контрольні прогони. popup.nrat_date 2026-04-19 Close