4.2 Модификация программы

Перейдём к программным изменениям. За основу возьмём программу, написанную Александром Побежимовым [12].

В неё нужно внести незначительные изменения: заменить тропическое сложение всех элементов строки на тропическое сложение трёх элементов. Для строки с номером i будет рассчитываться сумма элементов i-1, i, i+1. Это должно быть внесено во все части программы, где идёт работа с конкретной строкой. Код новых функций приведён в приложении А.

П осмотрим, как меняется фактическое время работы.

Рисунок 4.1 – Результат работы преобразованной программы

На основе рис. 4.1 построим графики для наглядности сравнения времени: логарифмическое представление (рис. 4.2) и нелогарифмическое (рис. 4.3).

Р исунок 4.2 – Сравнение времени работы, логарифмическая шкала

Рисунок 4.3 – Сравнение времени работы

Видно, что модификация заметно повышает скорость работы алгоритма. Далее попробуем оптимизировать проверку совместности системы. Как уже говорилось в разделе 4.1, формула 4.1 позволяет только вычислить минимум, а на существование решения влияет, строгим он является или нет. В связи с этим был реализован следующий алгоритм проверки системы на наличие решений: в цикле по всем возможным перестановкам чисел от 0 до m-1 используем текущую перестановку как номера столбцов элементов соответствующих строк, тропическое произведение которых мы и будем искать – это определение тропического перманента, представленное в формулах (1.2) и (1.3). Далее для каждого набора элементов будет найдено тропическое произведение – сумма, затем эта сумма будет сравниваться с минимумом по всем предыдущим перестановкам. Параллельно будет осуществлён подсчёт количества равных ему сумм. При этом, если будет найдено значение, меньшее локального минимума, имеющегося на i-ой итерации, счётчик обнулится и минимум будет переопределён.

Особенность для трёхдиагональных матриц заключается только в том, что при поиске значения тропического произведения для каждой перестановки будет учитываться модуль разности значения элемента перестановки с его индексом. Если они различаются на единицу, то в матрице системы этот элемент равен тропическому нулю – бесконечности, что следует из определения трёхдиагональной матрицы. Такие перестановки сразу удаляются из рассмотрения (расчёты для них не производятся до конца), что даёт некоторый выигрыш во времени.

Код с проверкой системы на решаемость представлен в приложении Б.

Вывод

Удалось реализовать спецификацию алгоритма Григорьева для трёхдиагональных матриц, которая работает эффективно по времени и по памяти. В качестве дальнейшей разработки можно заменить массив типа bool для проверки принадлежности столбца к множеству J на машинные слова и битовые операции.

5 Экономическое обоснование

В данном разделе производится расчёт себестоимости исследования в соответствии с [15].

5.1 Обоснование целесообразности исследования

Так как тропическая математика в некоторых сферах позволяет значительно упрощать решение задач как в плане необходимых вычислительных мощностей, так и в затрачиваемом времени, данная исследовательская работа имеет прикладное значение.

На некоторых матрицах алгоритм Григорьева имеет сложность, близкую к полиномиальной, и этот результат лучше, чем сложность алгоритма Гаусса в классической математике. Соответственно, разрабатываемая модернизация алгоритма Григорьева на трёхдиагональные матрицы может быть использована для получения выгоды в скорости решения ряда задач, напрямую связанных с дифференциальными уравнениями (например, приближение функций сплайнами) и физических задач (для которых переход в min-plus-алгебру даёт наиболее ярко выраженную выгоду).

Данная работа не имеет аналогов, несмотря на то, что современные математики активно изучают тропические системы для получения алгоритмов с полиномиальной сложностью. Соответственно, результат исследования либо покажет необходимость дальнейшего рассмотрения темы, либо, по меньшей мере, обозначит направления его движения.