Дата публикации: 2017

Дата публикации в реестре: 2020-03-03T21:01:50Z

Аннотация:

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

Тип: Article

Права: open access