Личный кабинет
Подробное описание документа
Овчинников В. А.
Способы снижения вычислительной сложности алгоритмов, вытекающие из принципа формирования решений / Овчинников В. А. - DOI 10.18698/2308-6033-2013-11-1046 // Инженерный журнал: наука и инновации. - 2013. - № 11. -
Скачать документ
Анализируется класс способов снижения вычислительной сложности комбинаторно-оптимизационных алгоритмов на графах и множествах. Рассмотренные способы основаны на использовании пошагового принципа формирования решения. Приведена классификация способов указанного класса. Рассмотрены примеры выполнения оптимизирующих преобразований в итерационном алгоритме улучшения разрезания гиперграфа и последовательном алгоритме его начального разрезания. Для этих алгоритмов рассмотрены процессы и приведены формулы определения значений критериальных оценок и множества вершин-кандидатов. Получены оценки вычислительной сложности выполнения указанных действий для случаев без и с использованием способов снижения вычислительной сложности. Выполнена оценка эффективности применения этих способов. Определена возможность формализации рассматриваемых оптимизирующих преобразований.
Статья опубликована в следующих изданиях
№ 11. - 2013.
