Выпуск:
2017. Том 3. №2Об авторах:
Ткаченко Иван Николаевич, ведущий программист ООО «Техноком» (г. Тюмень); tkachenko@technocom.techАннотация:
В статье исследуются способы сортировки зубчатых массивов для упорядочивания строк по убыванию значимости по двум критериям. Зубчатый массив является представлением решений задачи нахождения оптимального пути, в котором каждая строка — одно из решений. Цель сортировки — выбор наиболее значимых решений и последующее сокращение количества объектов, хранимых в матрице достижимости. Сокращение количества объектов не влияет на размерность матрицы достижимости, но сокращает объем памяти, необходимый для хранения ячеек матрицы. Задача описана на примере оценки решений транспортной задачи доставки грузов.
В статье при сортировке строк зубчатых массивов подразумевается приоритет одних ячеек строки массива над другими, т. е. первая ячейка оказывает на результат большее значение, чем вторая, а вторая ячейка большее, чем третья, и так далее.
Результатом исследования является формализация правил восьми различных подходов к сортировке — по количеству вариантов комбинирования двух критериев сортировки, приведен алгоритм и дана оценка вычислительной сложности. Критериями сортировки являются длина ключа и значение ключа. Все восемь подходов обеспечивают разные результаты сортировки. Для каждого подхода описаны и разобраны на примерах операции, необходимые для достижения требуемого результата. Для каждого подхода сформулирована и формализована задача.
Алгоритм сортировки зубчатых массивов основан на генерации текстового представления ключа строки. В статье рассмотрена только сортировка строк, сортировка столбцов в статье не рассматривается.
Сделаны выводы о том, какие из описанных подходов обеспечивают наилучшую скорость сортировки и почему. На примере задачи транспортировки грузов описано — к какому результату приведет выбор того или иного подхода к сортировке.
Ключевые слова:
Список литературы:
