Оцінки асимптотичної складності прикладних множинних транспортних алгоритмів при поділі їх на кластери

Abstract

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