Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
PAGE 1
Понятие о сложности
Ранее рассматривались проблемы принципиальной возможности вычислений и были исследованы различные подходы к понятию вычислимости. При этом не обращалось внимания на ресурсы времени и памяти. Однако существуют задачи, которые теоретически разрешимы, но при практической реализации требуют столь больших вычислений, что их решение практически неосуществимо.
Следовательно, принципиальная алгоритмическая разрешимость ещё не означает практическую реализуемость. Рассмотрим некоторые характеристики вычислений.
Считаем, что при вычислении мы используем алгоритм.
Различают сложность описания алгоритма и исходных данных, и сложность применения алгоритма к исходным данным.
Сложность описания алгоритма зависит от выбора того или иного способа задания алгоритма. Если такой способ выбран (машина Тьюринга, нормальный алгоритм или рекурсивное задание и т.д.), то под сложностью алгоритма может быть введена как длина записи алгоритма, так и длина встречающихся выражений и т.д. Например, для машины Тьюринга её сложность может быть введена как число букв внешнего и внутреннего алфавитов.
Введем следующее определение. Говорят, что неотрицательная функция g(n) есть 0(f(n)) если существует такая постоянная c, что g(n)≤cf(n) для всех, кроме конечного (возможно пустого) множества значений n, {1, 2, 3,…}. В этом случае записываем: g(n)=0(f(n)).
Сложность исходных данных понимается как длина (размер) их записи. Что такое размер входа? Всё зависит от того, что является входом. Размером входа, в общем случае, считают число символов, с помощью которых записан вход.
Пусть входом является целое число. Считаем, что число представлено в системе счисления с некоторым фиксированным основанием. В этих системах число символов, необходимых для представления целого числа n равно ]logAn[, где – основание системы, а ]х[ обозначает наименьшее целое q, такое, что . Известно, что , здесь log2B является константой при фиксированном В. Таким образом, число символов, необходимых для представления целого числа n есть 0(log2n).
Рассмотрим второй пример. Пусть требуется перемножить квадратные n×n матрицы А и В. Ясно, что подходящей мерой сложности исходных данных будет число пропорциональное l= n2, имея в виду, что для запоминания отдельного числа (элемента матрицы) выделен определенный объем памяти.
Во многих задачах входом является граф. Граф G=(V,X) можно, например, задать его матрицей смежностей АG=(aij) размера , где aij=1, если ребро и aij=0 в противном случае. Ясно, что максимальное число возможных ребер равно Однако многие графы являются разреженными, т. е. число их ребер много меньше М. В этом случае лучше задать граф перечислением его ребер, с помощью списков смежностей.
При задании списков смежностей для каждой вершины , выписывается множество вершин, смежных с v,
Размер этого представления зависит от суммы длин списков. Каждое ребро вносит вершину в два списка, поэтому сумма длин списков содержит элементов. Но для различения вершин, как правило, вводятся числовые индексы. Так как имеется вершин, то для индексов потребуется двоичных или десятичных разрядов. Следовательно, при таком представлении графа G=(V,X) потребуется символов.
Более экономной записью информации в ячейках памяти ЭВМ (выделенного для одного числа) можно добиться, что для задания графа G=(V,X) требуется ячеек памяти.
Сложность вычислений с помощью алгоритма понимается как функция от размера входа алгоритма. Для оценки сложности вычислений существует много критериев. Важными критериями являются: временная сложность, характеризующая время, затраченное на вычисление, и ёмкостная (ленточная) сложность, характеризующая необходимую для вычисления память, используемую для хранения промежуточных результатов.
Кроме того, сложность вычислений зависит от способа формулировки задачи. В качестве примера рассмотрим следующую задачу. Требуется узнать, является ли натуральное число n простым или составным. Чтобы анализировать сложность задачи надо выяснить, как задано число n. Если n задано как произведение своих простых делителей: , то задачи нет вообще; если n задано в унарной форме, т.е. n=11…1, то сложность записи равна (числу единиц), а сложность задачи, как можно показать, равна = (если использовать известный способ решения этой задачи – решето Эратосфена, состоящий в том, что число N последовательно делят на простые числа p1,p2,…, . Если ни на одно из этих чисел N не делится, то оно простое, иначе составное). Если число n записано в десятичной форме, то сложность записи числа (длина записи) равна l=log10n, а сложность решения в этом случае равна =2l/2, т.е. сложность решения представляет собой экспоненту от длины записи числа n.
Следует обратить внимание на то обстоятельство, что одной и той же задаче могут соответствовать разные языки, представляющие условия или входные данные задачи. Это связано со способами кодировки данных. Из всех языков представляющих исходную задачу, выбирается «разумный язык» или разумный способ кодировки её условий. Таким образом, каждой задаче соответствует “разумный язык” её представляющий.
Временная сложность вычислений (алгоритма)
Временная сложность вычислений (алгоритма) характеризует число операций для решения задачи заданного размера.
При решении однотипных задач с одинаковым размером входа может потребоваться различное число итераций для решения отдельных задач (этого типа), следовательно, и различное число операций.
Определим временную сложность алгоритма как число операций в худшем случае по всем входам размера (длины) n. Иначе временная сложность алгоритма это функция, которая каждому входу размера n ставит в соответствие максимальное (по всем индивидуальным задачам размера n) число операций, затрачиваемых алгоритмом на решение индивидуальной задачи этого размера.
Кроме меры сложности в наихудшем случае вводят временную сложность алгоритма А в среднем на входе размера n:
здесь p(ai) – вероятность появления задачи ai; µ(A(ai)) - число операций, затрачиваемых алгоритмом на решение индивидуальной задачи ai; Рn – множество рассматриваемых задач размера n, Рn={ ai}
При изучении сложности алгоритма, в основном интересуются его поведением при применении его к очень большим входам. Различие между сложностями 10n3 и 9n3 считаются несущественными, более важен показатель степени, а не коэффициент. Сложность алгоритма оценивается асимптотической сложностью, т.е. порядком роста числа операций при неограниченном росте размера входа. Например, если вход размера n обрабатывается за время cn2, где с – некоторая постоянная, то сложность этого алгоритма есть 0(n2), т.е. постоянная с не содержится в оценке. Для практических задач величина этого коэффициента может быть важна, если они различаются существенно. Если время работы алгоритмов А1 и А2 пропорционально, например, 1010n2 и 9n2 соответственно, то практическое использование алгоритма А1 проблематично.
Для решения выбранной задачи иногда можно использовать различные алгоритмы.
Под временной сложностью задачи понимается временная сложность наилучшего алгоритма, известного для ее решения.
Выясним как изменяется эффективность различных алгоритмов с ростом быстродействия ЭВМ на которых реализуются эти алгоритмы.
Пусть имеем 5 алгоритмов различной сложности для решения одной и той же задачи. Положим. что каждое действие алгоритма осуществляется за 1 млс. Характеристики алгоритмов приведены в следующей таблице .
Из этой таблицы видно, что увеличение времени решения задачи, например с 1-ой секунды до одного часа позволяет для алгоритма А1 увеличить размер решаемой задачи в 3600 раз, а для алгоритма А5 только в 2,33 раза.
Предположим, что быстродействие ЭВМ возросло в 10 раз. В нижеследующей таблице показано, как при этом возрастут размеры входов [29].
Из таблицы видно, что увеличение быстродействия в 10 раз даёт возможность для алгоритма А1 увеличить размер входа в 10 раз, а для алгоритма А5 увеличение размера входа практически не произошло. Таким образом, чем большую временную сложность имеет алгоритм, тем меньшее улучшение даёт увеличение быстродействия.
Полиномиальные алгоритмы и задачи. Класс Р
Считается, что алгоритм – полиномиальный или имеет полиномиальную временную сложность, если существует полином p(x) такой, что на любом входном слове длины n алгоритм завершает вычисления после выполнения не более чем p(n) операций.
Ясно, что, алгоритмы А1 и А2, временные сложности которых равны, например, будет считаться полиномиальными, ибо их сложности ограничены полиномами, т.е. имеют порядок не выше, чем и соответственно.
Говорят, что задача разрешима за полиномиальное время или полиномиально разрешима, если для неё существует полиномиальный алгоритм. При этом считается, что задача является «хорошей».
Множество всех задач, для каждой из которых существует полиномиальный алгоритм, называется классом Р.
Среди полиномиальных алгоритмов быстрыми являются линейные алгоритмы, которые обладают сложностью порядка n, где n – размерность входных данных. К линейным алгоритмам относится школьный алгоритм нахождения суммы десятичных чисел, каждое из которых состоит из n цифр. Сложность этого алгоритма – 0(n).
В класс Р кроме линейных задач попадают, например, следующие задачи.
Умножение целых чисел. Школьный метод умножения 2-х n-разрядных чисел имеет временную сложность порядка . Существует алгоритм Шёнхаге-Штрассена умножения чисел (заданных в двоичной системе счисления) с меньшей сложностью, именно со сложностью порядка .
Умножение матриц. Обычный метод имеет порядок сложности 0(n3). Существует более быстрый алгоритм умножения матриц - алгоритм Штрассена [2] который имеет сложность порядка .
Найти кратчайший путь на графе состоящем из n вершин и m рёбер. Сложность алгоритма 0(mn) .
Быстрое преобразование Фурье требует арифметических операций.
Задача Прима – Краскала – Кэли. Дано n городов. Нужно соединить все города телефонным кабелем так, чтобы общая длина кабеля была минимальной. Эта задача решается с помощью жадного алгоритма сложности .].
Нахождение эйлерова цикла в графе с m рёбрами. Алгоритм нахождения эйлерова цикла имеет сложность порядка 0(m), см., например.
Задачи, для которых не существует полиномиального алгоритма, считаются трудно разрешимыми.
Рассмотрим пример определения сложности вычислений (алгоритма) на примерах.
Пусть задано множество S, содержащее n действительных чисел. Требуется найти наибольший и наименьший элементы из S. Положим, что каждое одно сравнение двух любых чисел осуществляется за одинаковое время.
Один из возможных методов состоит в поиске сначала наибольшего элемента из S, а затем – наименьшего. Наибольший элемент можно найти, проводя n-1 сравнений, например по следующему алгоритму.
В результате n-1 сравнений найдётся наибольший элемент. Заметим, что не учитывается время на выборку элемента. Далее начинается поиск наименьшего элемента по аналогичному алгоритму. Если считать эти процедуры независимыми, то вновь потребуется n-1 сравнений. В итоге для нахождения наибольшего и наименьшего элементов из S потребуется 2n-2 сравнений.
Число необходимых сравнений можно уменьшить, если использовать принцип «разделяй и властвуй», который в теории алгоритмов называют ещё стратегией дублирования.
Стратегия дублирования состоит в следующем. Пусть размер задачи (размер входных данных задачи) равен n. Разобьём задачу на две подзадачи размера n/2 той же структуры, что и исходная задача. Если решения этих задач можно скомбинировать в решение исходной задачи, то получится эффективный алгоритм.
Рассмотрим, как стратегия дублирования даёт ускорение для решения предыдущей задачи. Положим, что число элементов множества S является степенью числа 2, т.е. n=2k, для некоторого k, k≥1.
Реализуем рекурсивный поиск, при котором множество S разбивается последовательно на два подмножества по следующей процедуре MAXMIN.
В этой процедуре сравнения происходят только на 3-ем шаге, где сравниваются два элемента множества S из которых оно и состоит, и на шаге 7, где сравниваются max1 с max2 и min1 с min2. Пусть Т(n) – число сравнений элементов множества S. Ясно, что Т(2)=1. Если n>2, то Т(n) – общее число сравнений, произведённых в двух вызовах процедуры MAXMIN (строка 5 и 6), работающих на множествах размера n/2 и ещё два сравнения в строке 7. Таким образом,
Решением рекуррентных уравнений (7.1) служит функция Т(n)=(3/2)n-2. Таким образом, вместо 2n-2 сравнений получили (3/2)n-2 сравнений чисел, т.е на (n/2) сравнений меньше.
Рассмотрим второй пример. Пусть требуется умножить два n разрядных двоичных чисел. При традиционном (школьном) алгоритме требуется битовых операций. Применим стратегию дублирования и разобьем числа х и у на две равные части:
Считаем, что n есть степень числа 2. Тогда
Равенство даёт способ вычисления ху с помощью четырёх умножений (n/2) разрядных чисел и нескольких сложений и сдвигов (умножений на степень числа 2).
Можно получить, что вместо битовых операций нужно 0() ≈ битовых операций. Здесь число разбивалось на два блока. Разбивая эти числа на большее число блоков можно получить, что умножение двух чисел имеет сложность для алгоритма Шёнхаге-Штрассена
Абстрактной моделью полиномиального алгоритма является так называемая детерминированная машина Тьюринга. Эта машина в каждый данный момент времени находится в строго определённом состоянии, за один шаг она совершает одно из некоторого конечного множества действий. Затем она переходит в следующее состояние и всё начинается вновь, пока не придёт к ситуации останова.
NP класс
Наиболее простыми считаются полиномиальные задачи, т.е. задачи класса Р.
Другим, возможно более широким, «сложностным классом» является класс NP. Эта аббревиатура обозначает выражение «разрешимых на недетерминированной машине Тьюринга за полиномиальное время». Оказалось, что многие известные задачи принадлежат к NP классу.
В обычных машинах Тьюринга (их называют детерминированными, чтобы отличать от недетерминированных) новое состояние, в которое машина переходит на очередном шаге, полностью определяется текущим состоянием и тем символом, который обозревает головка на ленте.
В недетерминированных машинах Тьюринга для каждого состояния может быть несколько следующих состояний, в соответствии с функцией перехода. И в каждом следующем состоянии запускается новая копия данной машины Тьюринга.
Недетерминированность лучше всего понять, рассматривая алгоритм, который производит вычисления до тех пор, пока не доходит до места, в котором должен быть сделан выбор из нескольких альтернатив. Детерминированный алгоритм исследовал бы сначала одну альтернативу, а потом вернулся для рассмотрения следующей альтернативы. Недетерминированный алгоритм может исследовать все альтернативы одновременно, «копируя», в сущности, самого себя для каждой альтернативы. Все копии работают независимо. Если копия обнаруживает, что данный путь безрезультатный, то она прекращает выполняться. Если копия находит требуемое решение, она объявляет об этом, и все копии прекращают работать.
Определим NP класс как класс задач, которые можно решить недетерминированными алгоритмами, работающими в течение полиномиального времени.
Чтобы доказать, что некоторая задача принадлежит классу NP, достаточно построить недетерминированный алгоритм (алгоритм недетерминированной машины Тьюринга), который решает эту задачу за полиномиальное время.
Пусть имеем, например, задачу выяснения существования в ориентированном графе гамильтонового цикла, длина которого меньше или равна M.
Рассмотрим следующий алгоритм.
В этом алгоритме рассмотрение каждого варианта, т.е. последовательности соединённых дугами вершин требует n шагов. Следовательно, каждая процедура ВЫБОР (иначе каждая копия алгоритма просмотра одного пути) работает не более, чем полиномиальное время, точнее имеет сложность порядка . Таким образом, задача выяснения существования в ориентированном графе гамильтонового цикла, длина которого меньше или равна M, является NP задачей.
Детерминированная машина Тьюринга является частным случаем недетерминированной машины Тьюринга (которая не имеет копий), поэтому имеем, что .
Вопрос о том, будет ли P=NP является открытой проблемой теории сложности. Широко распространено мнение, что , следовательно, .
Примеры задач из класса NP:
1) выяснение выполнимости формулы логики высказываний, записанной в к.н.ф.;
2) нахождение целочисленных решений системы линейных уравнений;
3) задача распознавания простого числа;
4) выяснение гамильтоновости графа;
5) задача коммивояжёра;
6) размещение обслуживающих центров (телефон, телевидение, срочные службы) для максимального числа клиентов при минимальном числе центров;
7) оптимальный раскрой (бумага, стальной прокат, отливка), оптимизация маршрутов в воздушном пространстве, инвестиций, станочного парка;
8) составление расписаний, учитывающих определённые условия;
9) оптимальная загрузка ёмкости (рюкзак, поезд, корабль, самолёт) при некоторых условиях;
10) динамическое распределение памяти. Раскроем эту проблему. Пусть заданы А – множество элементов данных, размер , каждого элемента данных , время поступления , и время окончания работы с элементом данных , положительное целое число D – размер области памяти. Вопрос. Существует ли для множества элементов данных допустимое распределение памяти? Иначе говоря, существует ли такая функция σ: А→{1,2,3,…}, что для каждого элемента интервал
содержится в [1, D], причём для любых , если , то либо , либо .
В случае, когда размеры всех элементов данных одинаковы, то задача решается за полиномиальное время ;
NP-полные и NP-трудные задачи
Рассмотрим сводимость задач. Говорят, что задача Z1 сводится к задаче Z2 , если метод решения задачи Z2 можно преобразовать в метод решения задачи Z1. Сводимость называется полиномиальной если указанное преобразование можно осуществить за полиномиальное время.
Если одновременно задача Z1 полиномиально сводится к задаче Z2 и Z2 полиномиально сводится к задаче Z1, то задачи Z1 и Z2 полиномиально эквивалентны.
Задача называется NP-трудной если каждая задача из NP полиномиально сводится к ней.
NP-трудная задача имеет тот смысл, что эта задача не проще, чем «самая трудная в NP».
В классе NP выделяются NP-полные задачи. Задача называется NP-полной, если она входит в NP и каждая задача из NP полиномиально сводится к ней (т.е. является NP-трудной). NP-полные задачи понимаются как самые трудные задачи из класса NP.
Класс NP- полных задач обладает следующими свойствами.
1. Никакую NP-полную задачу нельзя решить никаким известным полиномиальным алгоритмом, несмотря на настойчивые усилия многих блестящих исследователей.
2. Если бы удалось построить полиномиальный алгоритм для какой-нибудь NP-полной задачи, то это бы означало полиномиальную разрешимость каждой NP-полной задачи.
Основываясь на этих двух свойствах, многие высказывают гипотезу, что PNP. Практическое значение понятия NP-полной задачи лежит именно в широко распространенном мнении, что такие задачи по существу труднорешаемы. Следовательно, при их решении в худшем случае потребуется экспоненциальное количество времени и не будет возможности решить на практике такие задачи, за исключением очень малого числа индивидуальных задач.
Первой задачей, для которой было доказано, что она является NP-полной, была проблема о выполнимости (см. задачу 1 в § 4), именно, имеет место следующая теорема.
Теорема 7.1 (теорема Кука). Задача выяснения выполнимости формулы логики высказываний, представленной в к.н.ф., является NP-полной.
Все приведённые ранее примеры NP-задач (задачи 1-12) являются NP-полными задачами. Список NP-полных задач в настоящее время содержит несколько сотен задач и продолжает пополняться. Многие вновь установленные NP-полные задачи печатаются в журнале Journal of Algorithms. В действительности о большей части задач комбинаторной оптимизации известна либо полиномиальная разрешимость, либо NP-полнота, что является ещё одним подтверждением гипотезы P≠NP.
Класс Е.
Считается, что алгоритм имеет полиномиальную временную сложность, если существует полином p(x) такой, что на любом входном слове длины n алгоритм завершает вычисления после выполнения не более чем p(n) операций. Если такого полинома не существует, временная сложность считается экспоненциальной. Таким образом для них число операций возрастает быстрее значений любого полинома.
Кроме этого определения существует и второе определение: алгоритм имеет экспоненциальную временную сложность если его временная сложность имеет порядок не меньше, чем , где - постоянные. Иначе, временная сложность является экспоненциальной, если существуют постоянные , что для всех, кроме конечного числа значений n.
При первом определении, например задача, имеющая сложность порядка будет отнесена к задаче с экспоненциальной временной сложностью, а по второму определению – нет. Отметим, что функция хотя и растет быстрее любого полинома, но растёт медленнее, чем, например .
Большинство экспоненциальных алгоритмов – это просто варианты полного перебора. Экспоненциальные алгоритмы не считаются «хорошими», в отличие от полиномиальных алгоритмов, которые, как уже указывалось, считаются «хорошими». К экспоненциальным задачам относятся задачи, в которых требуется построить множество всех подмножеств данного множества, все полные подграфы некоторого графа или же все поддеревья некоторого графа.
Некоторые экспоненциальные алгоритмы весьма хорошо зарекомендовали себя на практике. Дело в том, что временная сложность определяется для худшего случая, а многие задачи могут быть не так плохи.
Для решения задачи линейного программирования существует так называемый симплекс-метод (алгоритм), который хотя и экспоненциален в худшем случае – уверено работает на практике для задач достаточно большого размера. Отметим, что для решения задачи линейного программирования Хачиян Л. Г. в 1979 г. предложил алгоритм эллипсоидов, который имеет полиномиальную временную сложность.
Метод ветвей и границ успешно решает задачу о рюкзаке, хотя этот алгоритм имеет экспоненциальную временную сложность.
Примеров экспоненциальных алгоритмов успешно используемых на практике мало. Более того даже для полиномиальных алгоритмов представляют практический интерес алгоритмы сложность которых имеет порядок n2 или n3. Ясно, что алгоритмы со сложностью порядка n100 вряд ли будут практически используемы.
Интересно, что экспоненциальный алгоритм может оказаться при малом размере задачи более быстрым, чем полиномиальный, однако с ростом размера задачи полиномиальный становится более быстрым.
Экспоненциальная сложность задачи имеет следующие аспекты:
-для отыскания решения требуется экспоненциальное время;
-искомое решение может быть настолько велико, что не может быть представлено выражением, длина которого была бы ограничена полиномом от длины входа.
Вторая ситуация возникает, например, если в задаче коммивояжера требуется найти все маршруты длины, не превосходящей заданной величины L. Может оказаться, что имеется экспоненциальное число маршрутов длины не превосходящей L.
Ёмкостная (ленточная) сложность алгоритма
Ёмкостная или ленточная сложность алгоритма характеризует необходимую для вычисления память для хранения исходных данных, промежуточных результатов и окончательного результата. При применении машины Тьюринга как модели вычислений, ёмкостная сложность оценивается длиной части ленты используемой для записи исходных данных и вычислений.
Пусть машина Тьюринга вычисляет значение функции f.
Активной зоной ленты (машины Тьюринга) в данный момент времени t называется связанная часть ленты, содержащая обозреваемую ячейку и все ячейки в которых имеются символы из внешнего алфавита машины. Активной зоной при работе машины Тьюринга на числе n называется объединение всех активных зон за время вычисления.
Определим Sf(x) как длину активной зоны при работе машины Т на числе х, если f(x) определено. В противном случае значение Sf(x) будем считать неопределённым. Функцию Sf(x) назовём ленточной сложностью.
Отметим, что в настоящее время уделяется существенно больше внимания временным характеристикам и значительно меньше ёмкостным, хотя эта характеристика тоже существенна при использовании ЭВМ с ограниченной памятью.
Для задач вводятся понятия задач с полиномиальной потребной памятью, с NP-потребной памятью и т.д.
Имеет место следующая теорема:
Теорема. Для ленточной (ёмкостной) характеристики сложности вычисления функции f имеет место оценка
где -временная сложность вычисления f(x).
Доказательство. В начальный момент на ленте машины Тьюринга записано число х (в унарной системе), следовательно, занято х+1 клеток ленты. На каждом такте (шаге) активной становится не более одной новой клетки, поэтому получим указанную оценку для Sf (x).
Эта теорема показывает, что если известна временная сложность, то можно оценить сверху ленточную сложность.
Интересно, что нет пределов сложности вычислений. Можно доказать, что какую бы сложную задачу не взять, то существует ещё более сложная задача.