ОЦІНКИ АСИМПТОТИЧНОЇ СКЛАДНОСТІ ПРИКЛАДНИХ МНОЖИННИХ ТРАНСПОРТНИХ АЛГОРИТМІВ ПРИ ПОДІЛІ ЇХ НА КЛАСТЕРИ

Анотація

Прикладні множинні транспортні алгоритми, як правило, є евристичними та надскладними. За обраною евристикою алгоритму, реальний час на програмну реалізацію залежить від мови програмування, структури представлення вхідних даних та алгоритмічної складності рішення. Дослідження базуються на використанні положень дискретної математики та теорії графів. Показано, що шляхом аналізу асимптотичної складності можливо визначити ефективну евристику. Уточнення моделей прикладних завдань, також, сприяють зменшенню складності. Оскільки, множинність транспортних завдань міститися у дискретному покритті або у функціоналі множинних транспортних засобів, то можливим є спрощення алгоритму шляхом їх декомпозиції на кластери для яких діють умови та обмеження стандартного транспортного завдання. Наведено особливості геометрично та комбінаторного розкладання на кластери. Надано формалізацію алгоритмів побудови кластерів для множинних транспортних завдань. Проведено порівняльний аналіз оптимальних та евристичних алгоритмів вирішення множинних транспортних завдань. Визначено ієрархію асимптотичної складності евристичних алгоритмів та проаналізовано можливості їх декомпозицій на кластери за якими досягається спрощення вирішення множинних прикладних транспортних завдань. Надано нотації складності рішення та можливості їх оцінки за цільовою функцією обраного алгоритму або за її апроксимацією. Здійснено аналіз асимптотичної складності евристичних алгоритмів для Big-O нотації. Показано, що придатними для реалізації є алгоритми, складності яких не перевищують поліноміальної, а застосування алгоритмів, які мають експонентну оцінку складності та вище є не бажаним. Зазначено, що асимптотичні оцінки складності алгоритму придатні для великих за розмірністю завдань, а для завдань невеликої розмірності доцільними є контрольні прогони.