Способы снижения вычислительной сложности алгоритмов, вытекающие из принципа формирования решений
Авторы: Овчинников В.А.
Опубликовано в выпуске: #11(23)/2013
DOI: 10.18698/2308-6033-2013-11-1046
Раздел: Информационные технологии
Анализируется класс способов снижения вычислительной сложности комбинаторно-оптимизационных алгоритмов на графах и множествах. Рассмотренные способы основаны на использовании пошагового принципа формирования решения. Приведена классификация способов указанного класса. Рассмотрены примеры выполнения оптимизирующих преобразований в итерационном алгоритме улучшения разрезания гиперграфа и последовательном алгоритме его начального разрезания. Для этих алгоритмов рассмотрены процессы и приведены формулы определения значений критериальных оценок и множества вершин-кандидатов. Получены оценки вычислительной сложности выполнения указанных действий для случаев без и с использованием способов снижения вычислительной сложности. Выполнена оценка эффективности применения этих способов. Определена возможность формализации рассматриваемых оптимизирующих преобразований.
Литература
[1] Овчинников В.А. Математические модели объектов задач структурного синтеза. Наука и образование, 2009, № 3. URL: http://technomag.bmstu.ru/doc/115712.html
[2] Овчинников В.А. Алгоритмизация комбинаторно-оптимизационных задач при проектировании ЭВМ и систем. Москва, Изд-во МГТУ им. Н.Э. Баумана, 2001
[3] Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. Санкт-Петербург, БХВ-Петербург, 2003
[4] Овчинников В.А., Иванова Г.С. Информационно-логическая модель алгоритма. Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение, 2005, № 2 (59), с. 109-121
[5] Иванова Г. С. Методология и средства разработки алгоритмов решения задач анализа и синтеза структур программного обеспечения и устройств вычислительной техники. Дис. ... д-ра техн. наук. Москва, 2007