Сортировка зубчатых массивов для оценки решений транспортных задач

Abstract

This article explores the ways of sorting the jagged arrays for ordering rows in descending order by two criteria. A jagged array is a representation of the solutions of the problem of finding the optimal path, in which each row is one of the solutions. The purpose of sorting is to select the most significant solutions and then reduce the number of objects stored in the reachability matrix. Reducing the number of objects does not affect the dimensionality of the reachability matrix, but reduces the amount of memory needed to store the cells of the matrix. The task is described on the example of assessing the solutions to the transport task of cargo delivery. In the article, when sorting rows of jagged arrays, the priority of some cells of the array row is assumed over the others, that is, the first cell exerts a greater value on the result than the second, and the second cell has more than the third, etc. The result of the study is the formalization of the rules of eight different approaches to sorting – by the number of variants of combining the two sorting criteria, the algorithm is given and the estimation of computational complexity is given. The criteria for sorting are the key length and key value. All eight approaches provide different sorting results. For each approach, the operations necessary to achieve the desired result are described and analyzed with provided examples. In each case, a problem is formulated and formalized. The algorithm for sorting the jagged arrays is based on generating a text representation of the row key. The article only considers sorting rows, sorting columns in the article is not considered. Conclusions are drawn about which of the described approaches provide the best sorting speed and why. On the example of the problem of cargo transportation, it is described to what effect the choice of this or that approach to sorting will result.

В статье исследуются способы сортировки зубчатых массивов для упорядочивания строк по убыванию значимости по двум критериям. Зубчатый массив является представлением решений задачи нахождения оптимального пути, в котором каждая строка – одно из решений. Цель сортировки – выбор наиболее значимых решений и последующее сокращение количества объектов, хранимых в матрице достижимости. Сокращение количества объектов не влияет на размерность матрицы достижимости, но сокращает объем памяти, необходимый для хранения ячеек матрицы. Задача описана на примере оценки решений транспортной задачи доставки грузов. В статье при сортировке строк зубчатых массивов подразумевается приоритет одних ячеек строки массива над другими, т. е. первая ячейка оказывает на результат большее значение, чем вторая, а вторая ячейка большее, чем третья, и так далее. Результатом исследования является формализация правил восьми различных подходов к сортировке – по количеству вариантов комбинирования двух критериев сортировки, приведен алгоритм и дана оценка вычислительной сложности. Критериями сортировки являются длина ключа и значение ключа. Все восемь подходов обеспечивают разные результаты сортировки. Для каждого подхода описаны и разобраны на примерах операции, необходимые для достижения требуемого результата. Для каждого подхода сформулирована и формализована задача. Алгоритм сортировки зубчатых массивов основан на генерации текстового представления ключа строки. В статье рассмотрена только сортировка строк, сортировка столбцов в статье не рассматривается. Сделаны выводы о том, какие из описанных подходов обеспечивают наилучшую скорость сортировки и почему. На примере задачи транспортировки грузов описано – к какому результату приведет выбор того или иного подхода к сортировке.