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