Алгоритм - сложность
Cтраница 2
Таким образом, в процессе оперативного принятия решений в системе управления необходимо сначала по подготовленным исходным данным определить алгоритм ограниченной сложности, а затем с помощью выбранного алгоритма принять оптимальное решение. [16]
Из теоремы 2.1 вытекает, что разбиение задачи размера я ( за линейное время) на две подзадачи размера я / 2 дает алгоритм сложности О ( п log п) / Если бы подзадач было 3, 4 или 8, то получился бы алгоритм сложности порядка я 8 3, п2 или я3 соответственно. [17]
В результате установлено, что многие классические задачи комбинаторики, такие как задача покрытия множества семейством подмножеств, задача о коммивояжере, задача целочисленного линейного программирования, эквивалентны в том смысле, что если бы для одной из них существовал алгоритм полиноминальной сложности, то такие алгоритмы существовали бы и для других задач. [18]
Из теоремы 2.1 вытекает, что разбиение задачи размера я ( за линейное время) на две подзадачи размера я / 2 дает алгоритм сложности О ( п log п) / Если бы подзадач было 3, 4 или 8, то получился бы алгоритм сложности порядка я 8 3, п2 или я3 соответственно. [19]
Задачи, для решения которых разработаны алгоритмы полиномиальной сложности ( так называемые эффективные алгоритмы), относятся к классу Р - сложных задач. Задачи, которые в настоящее время можно решить только с помощью алгоритмов экспоненциальной сложности, относятся к классу NP-сложных задач. Очевидно, что класс задач Р - сложности является подклассом NP-сложных задач. [20]
Основным экспериментальным материалом, на котором развивалась и апробировалась теория вычислительной сложности, были и являются экстремальные задачи комбинаторного типа и задачи теории графов. С тех пор основные усилия в теории вычислительной сложности были направлены на поиски алгоритмов полиномиальной сложности для задач экспоненциальной сложности и на доказательство сводимости или несводимости конкретных задач к задачам полиномиальной сложности. [21]
R выполняется за один шаг. Однако если и - степень числа 2, то можно сделать это быстрее: известен алгоритм сложности Од ( п log n), вычисляющий преобразование Фурье или обратное к нему, и мы думаем, что эта оценка неулучшаема. Приведем только алгоритм прямого преобразования Фурье. Алгоритм обратного преобразования аналогичен и предоставляется читателю. [22]
 |
Ориентированный граф и его представления. а - ориентированный граф. б - матрица смежностей. в - списки смежностей. г - табличное представление. [23] |
Основной недостаток применения матрицы смежностей заключается в том, что она занимает память объема V2 - даже тогда, когда граф содержит только 0 ( У) ребер. Уже начальное заполнение матрицы смежностей посредством естественной процедуры требует времени 0 ( VJ 2), что сводит на нет алгоритмы сложности 0 ( V) при работе с графами, содержащими лишь 0 ( V) ребер. Хотя разработаны методы для преодоления этой трудности ( см. упр. О ( F), основанные на работе с матрицей смежностей, встречаются редко. [24]
Эйлеровым циклом в неориентированном графе называется путь, который начинается и кончается в одном и том же узле и проходит по каждому ребру точно один раз. Связный неориентированный граф G имеет эйлеров цикл тогда и только тогда, когда степень каждого узла четна. Постройте алгоритм сложности 0 ( е) для нахождения эйлерова цикла в графе с е ребрами при условии, что такой цикл существует. [25]
 |
Алгоритм Дейкстры. [26] |
В задаче нахождения кратчайших путей из одного источника ситуация иная. Хотя нет причин предполагать, что для ее решения понадобится более 0 ( е) времени, ни один такой алгоритм не известен. Мы обсудим алгоритм сложности О ( я2), работа которого основана на построении множества S узлов, кратчайшие расстояния до которых от источника известны. На каждом шаге к S добавляется тот из оставшихся узлов, скажем v, расстояние до которого от источника меньше всех других оставшихся узлов. Если стоимости всех ребер неотрицательны, то можно быть уверенным, что путь из источника в v проходит только через узлы из S. Поэтому достаточно найти для каждого узла v кратчайшее расстояние до него от источника вдоль пути, проходящего только через узлы из S. [27]
Этот факт позволяет вычислять произведение (3.10), поочередно возводя матрицу А в квадрат и тем самым заменяя я - 1 умножение матрицы [ log я. Таким образом, мы получаем алгоритм сложности О ( я3 log я), отыскивающий расстояния между всеми парами вершин в графе без контуров отрицательной длины. [28]
Сколько вычислений должна требовать задача, чтобы мы сочли ее действительно трудной. Общепринято, что если задачу нельзя решить быстрее, чем за экспоненциальное время, то ее следует рассматривать как безусловно трудно разрешимую. В этой схеме классификации задачи, решаемые алгоритмами полиномиальной сложности, будут легко разрешимыми. Но нужно иметь в виду, что, хотя экспоненциальная функция ( такая, как 2) растет быстрее любой полиномиальной функции от п, для небольших значений п алгоритм, требующий 0 ( 2) времени, может оказаться эффективнее многих алгоритмов с полиномиально ограниченным временем работы. Тем не менее скорость роста экспоненциальной функции столь стремительна, что мы будем называть задачу трудно разрешимой, если у всех алгоритмов, решающих ее, сложность по меньшей мере экспоненциальна. [29]
Примерами таких задач служат задачи синтеза топологии БИС и СБИС, где препятствие для полной автоматизации - не отсутствие формализации задач, а их чрезмерно большая размерность. Большинство задач синтеза третьего уровня сложности относится к классу так называемых АФ-полных задач. В практических задачах проектирования размерности N таковы, что алгоритмы экспоненциальной сложности неприменимы. Поэтому актуальна задача разработки эффективных приближенных алгоритмов, предназначенных для решения широкого круга комбинаторных задач и имеющих полиномиальную зависимость L от N. [30]
Страницы: 1 2 3