Способы снижения вычислительной сложности алгоритмов …
УДК 004.051+519.6
Способы снижения вычислительной сложности
алгоритмов, вытекающие из принципа
формирования решений
© В.А. Овчинников
МГТУ им. <...> Н.Э. Баумана, Москва, 105005, Россия
Анализируется класс способов снижения вычислительной сложности комбинаторно-оптимизационных алгоритмов на графах и множествах. <...> Рассмотренные
способы основаны на использовании пошагового принципа формирования решения. <...> Рассмотрены примеры
выполнения оптимизирующих преобразований в итерационном алгоритме улучшения разрезания гиперграфа и последовательном алгоритме его начального разрезания. <...> Для этих алгоритмов рассмотрены процессы и приведены формулы определения значений критериальных оценок и множества вершин-кандидатов. <...> Ключевые слова: алгоритм, вычислительная сложность, граф, множество, оптимизирующие преобразования, пошаговый принцип, формирование решения, рекуррентные формулы. <...> Большинство задач проектирования структур сложных
систем имеет большую размерность входа — миллионы и более компонент. <...> В связи с этим даже для полиномиальных алгоритмов актуальной является проблема сокращения времени работы за счет использования способов снижения их вычислительной сложности, т. е.
выполнения оптимизирующих преобразований. <...> Этот принцип широко используется в комбинаторно-оптимизационных алгоритмах и определяет, например, метод вычисления значений
критериальных оценок и формирования состава «рабочих» подмножеств. <...> Снижение вычислительной сложности алгоритмов при применении способов данной группы достигается за счет сокращения количества операций или замены их на более эффективные. <...> Само преобразование алгоритма заключается в замещении его
части, неэффективно выполняющей необходимые действия, — заменяемый фрагмент — на заменяющий фрагмент, обеспечивающий получение результата с меньшей вычислительной сложностью. <...> Предлагаемые автором способы <...>