Способы снижения вычислительной сложности алгоритмов, вытекающие из принципа формирования решений

алгоритм вычислительная сложность граф множество оптимизирующие преобразования пошаговый принцип формирование решения рекуррентные формулы

Проблемы параметризованной верификации протоколов когерентности памяти, Анализ и оценка возможных подходов к решению проблемы повышения эффективности функционирования сложных информационно-технических систем, ...

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

• Похожие документы из РУАЭСТ
• |
• Похожие документы из Руконт