Размещено на http://www.allbest.ru/

Классы сложности задач

Под задачей понимается некоторый вопрос, на который нужно найти (вычислить) ответ. Задачи бывают общие (массовые - сравните со свойством алгоритма) и частные (индивидуальные). Общая задача определяется:

· списком параметров - свободных переменных, конкретные значения которых не определены;

· формулировкой условий - свойств, которыми должен обладать ответ (решение задачи).

Частная задача получается из общей задачи, если всем параметрам общей задачи придать конкретные значения (задать исходные данные). Для алгоритма сказали бы: на место формальных параметров подставить фактические.

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

Тем не менее, сложность задачи (чисто математической или естественнонаучной, выраженной с помощью некоторого формального языка) представляется одной из фундаментальных характеристик в познании той Вселенной, в которой мы существуем. Характеристикой не менее значимой, чем физические константы - скорость света в вакууме, постоянная Хаббла (значение плотности вещества во Вселенной, разделяющее замкнутую и открытую космогонические модели); чем известные математические константы и др.

Компьютерные науки делают пока только первые шаги в классификации задач по сложности. Естественно, что начинаем с дихотомии: попытки разделить все задачи на два класса - легкие и трудные. Границу между ними можно проводить по-разному, но все сошлись во мнении, что задачи, для решения которых требуется выполнить O (n), O (n²), O (n³),. операций - это легкие задачи (здесь n - параметр сложности исходных данных). Задачи же с оценкой сложности O (2ⁿ) и более - сложные. Первую группу задач называют задачами полиномиальной сложности, поскольку их временная сложность ограничивается сверху некоторым полиномом (быть может, очень большой, но конечной степени n). Обозначим множество таких задач Р. Вторую группу называют задачами экспоненциальной сложности, поскольку в общем случае (т.е. для исходных данных, наиболее "неудобных" для любого из алгоритмов, решающих задачу) требуется количество операций, увеличивающееся с ростом n, по крайней мере, экспоненциально. Обозначим множество этих задач ЕХР.

Такое разграничение практически оправдано. Представим себе, что на самом быстром из доступных нам компьютеров решаем две задачи, полиномиальную Р₁ с параметром сложности исходных данных и, и экспоненциальную Р₂ с параметром n₂. Эти две задачи решаются примерно одинаковое время T и находятся на грани того, чтобы испытывать наше терпение: согласны ждать время T, но ни секунды больше! И вот, наконец, мы получили новый компьютер, работающий в несколько (k) раз быстрее, чем старый. Вопрос: насколько более сложные задачи можно решать на новом компьютере (как изменятся n и n²?), если наши возможности ожидания решения не изменились?

Простой анализ показывает, что доступная сложность полиномиальной задачи увеличилась В несколько раз, стала равной m*n₁, а доступная сложность экспоненциальной задачи увеличилась на несколько единиц, стала равной n₂+l. Здесь m и l вычисляются через k. Например, если первая задача имеет линейную сложность, а вторая - 2ⁿ, то ускорение компьютера в два раза (k=2) приводит к значениям 2n₁ и n₂+l. Это действительно качественно различные результаты.

Известны многие представители класса задач полиномиальной сложности:

o вычисление скалярного произведения векторов,

o произведение матриц,

o решение системы линейных уравнений,

o сортировка массива чисел,

o вычисление наибольшего общего делителя,

o вычисление факториала,.

Хотелось бы, чтобы все задачи были легкими, но сегодня для ряда задач известны только экспоненциальные алгоритмы! В связи с попыткой классификации сразу возникает много вопросов. Существуют ли неполиномиальные задачи или для любой задачи может быть построен полиномиальный алгоритм? Если существуют, то где проходит граница между полиномиальными и неполиномиальными задачами, как ее описать (иными словами, найти легко вычислимую характеристическую функцию множества Р)?

Для ответа на эти и другие вопросы нужно навести порядок в множестве задач, выделить некоторые полезные типы задач (так называемые переборные задачи) и ввести хотя бы минимальную формализацию. Кроме этого понадобится:

1. Понятие сложности исходных данных. Нам необходим универсальный подход, не зависящий от семантики той или иной задачи. За универсальность приходится платить и плата состоит в том, что не будем получать точные оценки сложности задач, а лишь делать утверждения о виде зависимости (линейная, квадратичная и т.д.).

2. Понятие сведения одной задачи к другой. Положим, у нас есть решающий некоторую задачу алгоритм; можно ли его использовать для решения другой задачи, а если можно, то как? Как при этом связаны сложности этих двух задач? В качестве примера такого сведения можно привести задачи вычисления обратной матрицы и решения системы линейных уравнений. Алгоритм решения первой задачи может быть использован для решения второй задачи, но при этом потребуются некоторые дополнительные вычисления. Как известно, обе задачи имеют полиномиальную сложность. Сведение одной задачи к другой - это тоже задача! И в данном случае она также имеет полиномиальную сложность. Эту ситуацию обозначают следующей фразой: первая задача полиномиально сводима ко второй задаче. Позже будут даны более точные определения.

3. Понятие инвариантности вычислителя (компьютера) к классу задач. Хотелось бы, чтобы вычислитель, в терминах команд которого оценивается сложность, не влиял на результаты классификации задач. Изменение (в разумных пределах) архитектуры, системы команд, способов представления данных не должно перемещать задачу из одного класса в другой, хотя временные функции сложности будут, конечно, различными.

4. Два понятия, относящиеся к процессу решения задачи: детерминированное вычисление и недетерминированное вычисление. Детерминированное вычисление - обычный, классический способ (это понятие входит в определение алгоритма как одно из свойств). Недетерминированное вычисление имеет более общий характер: обычно оно ведет себя как детерминированное, но на некоторых шагах вдруг "размножается" и начинает существовать в двух или более параллельно работающих экземплярах, т.е. имитирует исполнение на многопроцессорной вычислительной машине с неограниченным количеством процессоров. Ясно, что распараллеливание работы может уменьшать время вычислений. Но насколько? Может ли распараллеливание перевести задачу из одного класса сложности в другой? Ответ не очевиден. Возьмем в качестве примера задачу поиска элемента в бинарном дереве, причем в множестве ключей поиска не определено никакого отношения порядка. Это означает, что в худшем случае нужно посетить все n вершин. Если просмотр распараллелить, начиная с корня, одновременно просматривая левое и правое поддеревья, а внутри каждого из поддеревьев процессы вновь распараллелить и т.д., перемещаясь по ссылкам к концевым вершинам, то нам потребуется время, пропорциональное log₂ (n) и количество процессоров, пропорциональное n. Таким образом, соотношение времен детерминированного и недетерминированного вычислений такое же, как и соотношение экспоненциального и линейного алгоритмов (если считать параметром сложности исходных данных количество уровней дерева), т.е. при распараллеливании задача переходит из одного класса в другой. Известно, что существуют плохо распараллеливаемые задачи, для которых увеличение количества процессоров сверх некоторой константы не приводит к уменьшению времени вычислений. Такие задачи, очевидно, останутся в своем классе при изменении способа вычисления.

Понятие переборной задачи (задачи решаемой с помощью полного перебора).

Положим, у нас имеется множество S из n элементов. Нам требуется отыскать какое-либо его подмножество, обладающее определенным свойством. Это можно сформулировать так: дан предикат (утверждение) P (A), определенный на множестве 2^S всех подмножеств множества S, т.е. A?2^S, истинный на одних подмножествах (быть может, только на одном) и ложный на других (быть может, на всех). Пример: множество S состоит из и различных целых чисел {1, 3, 4, 7, 8, 14, 20, 23, 25, 28}; предикат P (A) = {множество A содержит только четные числа}. В этом случае P ({3, 7, 14}) = false, P ({4, 20, 28}) = true.

Утверждение P называют еще свойством множества A. Для конкретного множества A легко выяснить, обладает ли оно свойством P. Не найти множество, обладающее свойством P зачастую можно только, проверив для всех A?2^S, выполняется ли P (A). Например, для упомянутого множества S целых чисел можно написать уравнение P₁ (Х) = true, где P₁ (Х) = {сумма чисел, входящих в X, равна 32}. Это известная задача о рюкзаке, в которой требуется найти подмножество заданного множества натуральных чисел, причем сумма чисел, входящих в подмножество, должна быть равна другому заданному числу m. Найти решение этого уравнения, т.е. найти подходящее множество X можно в общем случае только перебором и проверкой вариантов. Каждое подмножество может быть описано характеристической функцией c: S - > {0,1} так, что с_i = 1, если i-й элемент множества S принадлежит X и c_i = 0 в противном случае. Для решения задачи в худшем случае перебрать нужно все варианты, а их 2ⁿ. В настоящее время не известно никакого способа вычисления X (под термином "вычисление" мы понимаем альтернативу перебору).

Теперь можно дать более формальное определение задачи, решаемой методом перебора.

Переборная задача - это задача с параметром сложности исходных данных n, решение которой может быть выражено в виде совокупности значений c₁, с₂,., c_n, параметров x₁, x₂,., x_n, каждый из которых может принимать только конечное число значений, причем формулировка задачи содержит явное указание на то, как вычислить (проверить), является ли данный набор {c_i} удовлетворительным (допустимым) решением задачи, но не известно (или не существует) никакого способа вычислить значения {c_i} по формуле или с помощью алгоритма полиномиальной сложности.

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

Понятие полиномиальной сводимости.

Будем говорить, что задача Q сводится к задаче P за полиномиальное время, если существует детерминированный полиномиальный алгоритм, преобразующий произвольный частный случай задачи Q (частную задачу, полученную подстановкой значений вместо параметров общей задачи Q) в некоторый частный случай задачи P, и второй детерминированный полиномиальный алгоритм, преобразующий решение задачи P в решение задачи Q.

Это понятие может быть проиллюстрировано рисунком 1.

Рис.1. Сведение задачи Q к задаче P

Для задач распознавания понятие полиномиальной сводимости формулируется чуть проще: задача Q сводится к задаче P за полиномиальное время, если существует детерминированный полиномиальный алгоритм, преобразующий произвольный частный случай задачи Q в некоторый частный случай задачи P так, что ответом для данного случая задачи Q является "да" тогда и только тогда, когда ответом на соответствующий случай задачи P также является "да".

Рассмотрим пример полиномиального сведения. Пусть требуется решить систему линейных уравнений Ax = b с квадратной матрицей А размером n*n, имеющей отличный от нуля определитель det А <> 0. Это задача Q с исходными данными A и b. Вторая задача (Р) формулируется следующим образом: дана квадратная матрица A; требуется найти обратную матрицу C = A^-1.

Пример полиномиального сведения можно увидеть на рисунке 2.

Рис.2. Пример полиномиального сведения

Здесь вектор b, несущественный для задачи P, напрямую передается во второе (заключительное) полиномиальное преобразование.

класс сложности задач NP.

Изобразим условно взаимоотношение классов задач полиномиальной и экспоненциальной сложностей (рисунок 3).

Рис.3. Сложность некоторых задач

Здесь каждая точка области, ограниченной прямоугольником, представляет некоторую задачу. Две точки - это примеры задач из разных классов. Выше было выяснено, что для переноса "Ханойской башни" требуется O (2ⁿ) операций, а для перемножения матриц не более, чем O (n³) операций. Где проходит граница между классами задач полиномиальной сложности P и экспоненциальной сложности ЕХР? Ответ на этот вопрос, т.е. описание границы (например, задачи с такими-то свойствами входят в класс P, а все остальные входят в класс ЕХР) в настоящее время не известен. Чтобы разведать границу, математики придумали еще один класс задач - NP. Интуитивно предполагается, что он может оказаться "нарушителем границы". Это класс задач, которые можно решить за полиномиальное время (P), но на машине, более мощной, чем обычная однопроцессорная машина - на недетерминированном (N) вычислителе. Недетерминированный вычислитель исполняет так называемые недетерминированные алгоритмы. Напомним свойство детерминированности: определенность (детерминированность) алгоритма означает, что для каждого шага могут быть по набору исходных для шага данных однозначно вычислены результаты выполнения шага, и эти результаты не зависят ни от каких случайных факторов. Соответственно этому и алгоритм в целом по окончании работы исполнителя выдает вполне определенный результат.

оптимизация алгоритм сложность задача

Недетерминированный алгоритм лишен этого свойства. Разрешаем шаги с неоднозначным результатом - шаги, вырабатывающие сразу несколько значений для одной и той же переменной. Эти несколько значений далее могут быть использованы одним из двух способов.

Первый способ. Создать несколько параллельно выполняющихся процессов (по процессу для каждого значения) для продолжения вычислений. Это возможно на многопроцессорной машине с неограниченно большим количеством параллельно работающих процессоров.

Насколько серьезно может помочь распараллеливание в ускорении решения задачи? Является ли многопроцессорная машина панацеей? Может быть, не стоит тратить силы на совершенствование технологий микроэлектроники и пытаться увеличивать скорость работы процессора, может быть, остановиться на тех процессорах, которые уже разработаны, и пойти по пути увеличения количества процессоров в вычислительной системе?

Рассмотрим в качестве примера задачу вычисления суммы n чисел a_i. На однопроцессорной машине для ее решения потребуется выполнить (n-1) операций сложения. Если у нас имеется неограниченное количество процессоров, то на первом шаге можем параллельно выполнить попарные сложения a₁ + a₂, a₃ + a₄,. Затем результаты первого шага снова подвергнуть попарному сложению и т.д. На каждом шаге количество слагаемых будет уменьшаться в два раза по отношению к предыдущему шагу (при четном количестве слагаемых на предыдущем шаге) пока не дойдет до одного слагаемого. Это и будет результатом. Нетрудно подсчитать, что нам потребуется порядка log₂n шагов. Существенное ускорение за счет распараллеливания, но все-таки не 100% - все не было сведено к одному шагу.

Второй способ. Угадать, какое из нескольких значений, полученных на данном шаге, является правильным (задающим искомое решение) и использовать в дальнейшем только его, игнорируя все остальные. В этом случае требуется только один процессор, но дополненный угадывающим устройством.

С точки зрения теории сложности не важно, каким именно из двух способов производить вычисление (временная сложность одинакова). Первый способ соответствует дереву возможностей и параллельному движению по всем ветвям дерева, а второй способ состоит в угадывании того, по какой ветви нужно двигаться и в движении по угаданной ветви. В дальнейшем будут продемонстрированы в доказательствах теорем оба варианта недетерминированного вычислителя.

Связь между классами P и NP.

Задача о переносе "Ханойской башни" по самой постановке не может быть распараллелена, так как в один момент времени только один диск переносится с иглы на иглу. Поэтому, даже при появлении такой мощной техники как недетерминированные машины эта задача остается в классе ЕХР.

Задача, решаемая за полиномиальное время на обычной машине, может быть решена за полиномиальное время и на недетерминированной машине, т.е.

PНNP

Верно ли обратное (и тогда p=NP) или существуют задачи, решаемые за полиномиальное время на недетерминированной машине, но требующие экспоненциального времени на однопроцессорной машине (тогда p М NP, NP\P №--Ж)?

В первом случае ничего нового в классификации задач от введения класса NP не получим. Но появляется много надежд. Дело в том, что для некоторых задач из класса NP известны только экспоненциальные алгоритмы для их решения на однопроцессорной машине. Если P = NP, т.е. надежда разработать и полиномиальные алгоритмы. Вопрос этот не праздный. На карту поставлено не только машинное время. В криптографии (науке о шифровании информации) существует целое направление - шифрование с открытым ключом. В его основе использование математических задач, решаемых алгоритмами экспоненциальной сложности. Если вдруг для них найдутся эффективные полиномиальные алгоритмы, то многие секреты перестанут быть секретами.

Но и во втором случае появляется много вопросов. Что собой представляет класс NP\P? Чем задачи из этого класса отличаются от других задач из ЕХР? В настоящее время развита довольно большая теория задач класса NP в предположении, что NP № Р. Кому-то может показаться, что это сродни теории привидений. Не известно, есть ли привидения, а уже обсуждается их одежда, вкусы, походка и любимый род занятий.

Однако такой взгляд не верен. Нерешенная проблема не должна тормозить развитие науки. В математике, в компьютерных науках существует несколько недоказанных (или недоказуемых) фундаментальных утверждений-гипотез, принятие которых позволило получить большое количество важных результатов. Достаточно вспомнить тезис Тьюринга, тезис Черча, аксиому Цермело. Поэтому дальше будет обсуждаться строение класса NP.

Классы сложности P, NP, NPI, NPC.

IF NP № P then NP: = PИNPCИфPI

Введем еще один класс задач - NP-полные (NPC) задачи (проблемы). Проблема Т называется NP-полной, если она удовлетворяет двум условиям:

Т О NP,

Если R О NP, то R сводится к T за полиномиальное время.

NP-полные проблемы являются своего рода универсальными. Не нужно придумывать алгоритмы для других задач, достаточно свести эти задачи к какой-либо NP-полной проблеме и воспользоваться алгоритмом ее решения. Представим на секунду, что для какой-то NP-полной проблемы. два программиста, работая в старом заброшенном гараже. (так обычно начинаются байки про гениальных программистов и гениальные программы) написали алгоритм полиномиальной сложности. Это будет означать, что P = NP!

С тех пор как С. Кук доказал в 1971 г., что проблема выполнимости для пропозиционального исчисления является NP-полной, множество NPC пополнилось сотнями проблем.

NP-полные проблемы, как следует из определения, являются наиболее трудными в классе NP.

Значение класса NP-полных проблем состоит еще и в том, что ему принадлежат очень многие известные и важные в прикладном отношении задачи. Перечислим некоторые из них.

1. Задача изоморфизма подграфу.

Даны два графа G₁ и G₂. Множество вершин первого графа обозначим V₁, а второго - V₂. Пусть |V1|>|V2|=n. Требуется ответить на вопрос: найдется ли в графе G₁ подграф Н, изоморфный графу G₂?

2. Задача о клике.

Дан граф G с m вершинами и целое положительное число n. Граф называется кликой, если каждая вершина в нем связана ребром с каждой. Количество вершин в клике назовем ее мощностью. Верно ли, что в данном графе G имеется клика мощности не менее, чем n?

3. Гамильтонов цикл.

Дан граф G с n вершинами. Существует ли в графе простой цикл, проходящий через все вершины графа? Простым называется цикл, в котором вершины не повторяются. Таким образом, гамильтонов цикл - это последовательность вершин и дуг (ребер) графа, содержащая все вершины графа G по одному разу, но, может быть, содержащая не все дуги.

4. Задача коммивояжера.

Дан граф G с n вершинами. Каждому ребру графа приписано положительное целое число d_i, задающее длину ребра. Кроме этого, задано некоторое положительное целое число L. Требуется ответить на вопрос: найдется ли в графе G маршрут, проходящий через все вершины графа G такой, что его длина не превышает L?

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

5. Вершинное покрытие.

Дан граф G с m вершинами и целое положительное число n. Вершинным покрытием называется подмножество U Н V множества V вершин графа такое, что любое ребро графа G инцидентно хотя бы одной из вершин множества U (вторая вершина ребра может либо принадлежать, либо не принадлежать множеству U). Существует ли вершинное покрытие не более, чем из n вершин?

6. Разбиение.

Дано множество положительных целых чисел x₁, x₂,., x_n. Можно ли разбить его на два подмножества так, чтобы суммы чисел в обоих подмножествах были равны?

7. Трехмерное сочетание.

Даны три множества: A, B, C. Мощности их равны: |А| = |В| = |С| = m, но множества не пересекаются. Зафиксировано некоторое множество троек NНAґBґC, |N|=n. Трехмерным сочетанием называется подмножество MНN, |M| = m, в котором ни какие две разных тройки не имеют ни одной равной координаты.

Кроме класса NP-полных проблем рассматривают еще и класс NP-трудных проблем.

Проблема Т называется NP-трудной, если она удовлетворяет условию: если R?NP, то R сводится к T за полиномиальное время.

Заметим, что это условие совпадает со вторым условием для NP-полных проблем. Следовательно, NP-полная проблема - это NP-трудная задача, принадлежащая классу NP.

Классы сложности NPC и NPI

Напомним утверждение IF NP № P then NP: = PИNPCИNPI. В соответствии с ним класс NP не исчерпывается (при условии NP№Р) простыми полиномиальными задачами и сложными NP-полными задачами. В него входят еще и задачи промежуточной сложности, класс которых обозначен здесь как NPI. Утверждение это доказано как теорема существования, не конструктивно, т.е. без построения задачи класса NPI.

В отличие от класса NPC, в котором находиться очень много известных и практически важных задач, в "промежуточном" классе такие представители неизвестны. Возможно одна из них "задача изоморфизма двух графов".

Оптимизация алгоритмов

Одна из задач, которая обычно ставится при разработке алгоритмов и программ - минимизация требуемых программой ресурсов. Особенно это касается системного программного обеспечения: программ операционной системы, трансляторов, систем управления базами данных и знаний и т.д., т.е. программ, имеющих большое количество пользователей и испытывающих как товар, большую конкуренцию на рынке программных средств.

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

Во-первых, сложно сформулировать критерий оптимизации, имеющий одновременно и бесспорное практическое значение и однозначно определенный в математическом плане. Например, можно поставить задачу минимизации числа команд машины Тьюринга - критерий, хорошо определенный математически; но совсем неясно его практическое значение, поскольку вряд ли реальная программа на реальном компьютере будет моделировать машину Тьюринга. Можно поставить задачу минимизации времени выполнения программы на реальной машине - ясный с практической точки зрения критерий. Однако невозможно будет решить задачу оптимизации математическими методами, так как время выполнения зависит (иногда значительно) от архитектуры ЭВМ, а архитектуру современных компьютеров не опишешь небольшим числом параметров. Важно также, что программа, работающая быстрее других на одном компьютере, может оказаться не самой быстрой на другом. Существуют даже специальные программы с общим названием benchmark, предназначенные для оценки архитектур.

Во-вторых, не совсем ясно, что такое сложность задачи. Ее можно было бы определить как минимальную из сложностей алгоритмов, решающих эту задачу. Но существует ли алгоритм минимальной сложности (как убедиться, что найденный алгоритм действительно минимальный или, напротив, не минимальный)? Есть ли к чему стремиться? И насколько труден поиск этого минимума? Эти вопросы связаны с нижней оценкой сложности алгоритмов (а не верхней, как в предыдущих шагах).

Можно ли для рассматриваемой задачи доказать, что никакой решающий ее алгоритм не может быть проще этой нижней оценки? Возьмем уже решавшуюся задачу перемножения квадратных матриц. Приведен алгоритм сложности Тa (n) = 3n³ + n². Вероятно это не лучший алгоритм, но какова оценка снизу? Результирующая матрица имеет n² элементов. Для вычисления любого элемента нужна хотя бы одна операция однопроцессорной машины - два элемента за одну операцию найти нельзя. Таким образом, для минимального алгоритма мы получаем неравенства

n² <= Ta, min (n) <= 3n³+n²

Вряд ли n² - хорошая нижняя оценка, но уже известно, что n³ нижней оценкой не является, так как найдены более быстрые алгоритмы (в частности, алгоритм Штрассена).

Имея в виду сказанное, можно отступить от математической традиции и под оптимизацией алгоритмов понимать просто изменение алгоритма или поиск нового с меньшей сложностью.

Существует несколько самостоятельных аспектов оптимизации программ, из которых выделим два:

· оптимизация, связанная с выбором метода построения алгоритма;

· оптимизация, связанная с выбором методов представления данных в программе.

Первый вид оптимизации имеет глобальный характер и (при удачной оптимизации) ведет к уменьшению порядка функции сложности - например, замена алгоритма с Тa (V) = O (F^S) на алгоритм с Ta (V) = O (V⁴). Он зависит от того, как задача разбивается на подзадачи, насколько это разбиение свойственно самой задаче или является только искусственным приемом.

Общим руководящим подходом здесь может быть последовательность действий, обратная анализу алгоритмов. При анализе по рекурсивному алгоритму строится уравнение, которое затем решается. При оптимизации реализуется цепочка:

Формула, задающая желаемую сложность - >

Соответствующее уравнение (одно из возможных) - >

Метод разбиения задачи на подзадачи.

Второй вид оптимизации, не меняя структуры программы в целом, ведет к экономии памяти и/или упрощению работы со структурами данных, повышению эффективности вспомогательных процедур, обеспечивающих "интерфейс" между прикладным уровнем (на котором мыслим в терминах высокоуровневых объектов - графов, матриц, текстов и т.д.) и машинным уровнем, поддерживающим простейшие типы данных (числа, символы, указатели). Результатом этого обычно является уменьшение коэффициентов при некоторых слагаемых в функции сложности (при удачной оптимизации - при наиболее значимом слагаемом), но порядок функции сложности остается тем же.

Оба вида оптимизации дополняют друг друга и могут применяться совместно. По-видимому, трудно дать какие-либо рекомендации универсального характера по методам оптимизации. Вместо этого приведем несколько успешных примеров оптимизации и попытаемся сделать на их основе некоторые выводы. Для каждой задачи будут проанализированы по два алгоритма: наиболее часто употребляемый или решающий задачу "в лоб", и усовершенствованный.

Рекурсивный алгоритм умножения матриц

Классический итеративный алгоритм перемножения квадратных матриц размера n*n имеет сложность O (n³), а нижняя оценка сложности не менее O (n²). Следовательно, оптимальный алгоритм имеет сложность, заключенную в этом узком коридоре. Отыскивая алгоритм в классе алгоритмов, разбивающих задачу на a подзадач в c раз меньшего размера с уравнением для функции сложности:

Т (n) = а Т (n/с) + bn^k, T (1) = b,

вспоминаем возможные оценки сложности O (n^k), O (n^klоg_cn), O (n^lоg_cⁿ). Эти оценки были получены в предположении, что на один шаг разбиения задачи на a подзадач (без решения самих подзадач) требуется bn^k операций. Три оценки отражают три варианта соотношений между а и c^k: a < c^k, a = c^k, a > c^k.

Поскольку хотим получить алгоритм с показателем функции сложности меньше трех, то не можем допустить в алгоритме ни одного шага со сложностью O (n³) или более. Следовательно, k может быть равно только единице или двум. При k = 1 отпадают два первых варианта (а < с¹, а = с¹), так как в этом случае получались бы оценки сложности ниже нижней границы O (n²). В третьем варианте с учетом нижней границы требуется, чтобы 2 <= log_cа < 3 или c² <= а < с³.

Сделаем попытку применить рекурсию с использованием известного в теории матриц блочного представления:

Здесь A_ij - матрицы размера (n/2) * (n/2).

Аналогично представим блоками матрицы В и С. Тогда произведение С=АВ можно найти в четыре этапа, вычислив блоки С₁₁, С₁₂, С₂₁, С₂₂ матрицы C по формулам C_ij = A_i,1B_1,j + A_i,2B_2,j.

Рекурсивная процедура Перемножить вызывается с координатами левого верхнего угла (r_A - номер строки, c_A - номер столбца) матрицы A и с аналогичными координатами матриц В и С (при первом вызове все координаты равны единице), размером матриц n. В процессе выполнения процедура вызывает себя для перемножения блоков половинного размера. Для суммирования частных произведений она вызывает вспомогательную процедуру Сложить и использует вспомогательные матрицы XI и Х2 для хранения промежуточных результатов.

Если размеры матриц n=1, то производится обычное умножение скалярных значений (элементов матриц).

процедура Перемножить (А, В: матрица;

переменная C: матрица; rА, сА, rВ, сВ, rС, сС: индекс; n: размер);

переменная X1, X2: матрица;

начало

если n > 1 то

начало

{Вычислить 1-й блок: }

Перемножить (A, В, XI, rА, сА, rВ, сВ, 1, 1, nil);

Перемножить (A, В, X2, rА, сA+n/2, rВ+n/2, сB, 1, 1, n/2);

Сложить (Х1, Х2, С, rС, cC, n/2);

{Вычислить 2-й блок: }

Перемножить (A, В, XI, rА, сА, rВ, сВ+n/2, 1, 1, n/2);

Перемножить (A, В, Х2, rА, сA+n/2, rВ+n/2, сB+n/2,1,1,n/2);

Сложить (Х1, Х2, С, rС, сC+n/2, n/2);

{Вычислить 3-й блок: }

Перемножить (A, В, XI, rА+n/2, сA, rВ, cВ,1,1, n/2);

Перемножить (A, В, Х2, rА+n/2, сA+n/2, rВ+n/2, сB,1,1,n/2);

Сложить (Х1, Х2, С, rС+n/2, cС, n/2);

{Вычислить 4-й блок: }

Перемножить (A, В, XI, rА+n/2, cА, rВ, cВ+n/2,1,1,n/2);

Перемножить (A, В, Х2, rА+n/2, cА+n/2, rВ+n/2, cВ+n/2,1,1, n/2);

Сложить (Х1, Х2, С, rС+n/2, cC+n/2, n/2);

конец

иначе С [rС, cС]: = А [rА, cА] * В [rВ, cВ] {Умножение скаляров. }

конец

Легко видеть, что для этой процедуры k=2, c=2, т.е. с^k = 4. Поскольку процедура вызывает себя восемь раз (a=8), то мы имеем вариант а > с^k и решение уравнения для функции сложности имеет вид O (n^log_c^a) = O (n³).

К сожалению, улучшения результата по сравнению с классическим алгоритмом не произошло. Улучшение возможно, если, оставаясь в рамках данного подхода, сумеем организовать вычисления таким образом, чтобы значение a было меньше восьми.

Это удалось сделать в 1969 г. немецкому ученому Ф. Штрассену (Volker Strassen). В его методе а=7, т.е. сложность O (n^2,81).Ф. Штрассен предложил вычислять блоки матрицы-произведения следующим образом:

В этих равенствах только семь умножений матриц, следовательно, рекурсивная процедура содержит в своем теле семь рекурсивных вызовов. Кроме того, имеется 18 аддитивных (сложений и вычитаний) матричных операций, но они не рекурсивны и имеют квадратичную сложность.

Конечно, практическое значение алгоритм Штрассена вряд ли имеет, так как зависимость и 2,81 дает выигрыш против n³ только при очень больших размерностях задачи, а накладные расходы на организацию рекурсии и на дополнительные аддитивные матричные операции (в классическом алгоритме их четыре) велики. Но с теоретической точки зрения результат очень важен: он помогает продвинуться к пониманию того, какова сложность задачи.

Задача перемножения длинных целых чисел без знака

Длинные целые числа используются в арифметике высокой точности (Д. Кнут. Т.2), криптографическом кодировании сообщений (шифровании). При этом длина чисел (т.е. количество цифр в записи числа) может достигать нескольких сотен и более. Арифметические операции (сложение, вычитание, умножение, деление) над длинными числами не могут выполняться компьютером за один шаг. Любая такая операция должна реализовываться специально написанной процедурой.

Представление длинных целых чисел

Наиболее естественным является простое расширение стандартного формата: если для записи числа требуется n цифр, то память для них выделяется в виде непрерывной области соответствующего размера.

Предположим, что перемножается два числа U = u_nu_n-1u_n-2. u₃u₂u₁ и V = v_nv_n-1v_n-2. v₃v₂v₁. Результат имеет суммарную длину W = w_nw_n-1w_n-2. w₃w₂w₁. Числа записаны в позиционной системе счисления с основанием (базой) b: 0 <= u_i, v_i, w_i < b. При этом индекс единица соответствует младшей цифре в записи числа.

Алгоритм умножения 1 (классический)

Этот алгоритм работает подобно тому, как производится умножение на бумаге. Числа представлены массивами цифр. Основание системы счисления b может быть как двоичным, b = 2, так и сколь угодно большим, например, занимающим машинное слово. Важно, чтобы перемножить или сложить цифры можно было одной машинной операцией (или малым их числом). Для представления цифр процедура использует некоторый тип Digit.

procedure SimpleMultiplication (U, V: superlongpositive;

var W: superlongpositive; n, m: integer);

var

i, j: integer;

S: DoubleDigit; {Место для формирования двух цифр. }

C: Digit; {Разряд переноса. }

begin

for i: = 1 to n do

W [i]: = 0; {Подготовка места для результата. }

for j: = 1 to m do {Пo цифрам числа V. }

begin

С: = 0; {Сначала переноса нет. }

for i: = 1 to n do {Пo цифрам числа U. }

begin

S: = U [i] *V [j] +W [i+j-1] +C;

W [i+j-1]: = S mod P; {Временное значение очередной цифры. }

С: = S div P; {Формирование разряда переноса. }

end;

W [j + n]: = С; {Старшая цифра частичного произведения. }

end;

end;

Непосредственно видно, что сложность этого алгоритма равна O (n^m) или в случае сомножителей одинаковой длины - O (n²).

Алгоритм умножения 2 (оптимизированный по времени). Разделим задачу на подзадачи, разделив запись каждого из сомножителей на две части: U= U₂U₁, V=V₂V₁. При n-разрядных сомножителях длины U_i, V_i будут равны n/2. Индексу 1 соответствует младшая половина, а индексу 2 - старшая. Иначе можно записать U = U₂00.00 + U₁ = U₂b^n/2 + U₁.

Произведение UV = (U₂b^n/2 + U₁) (V₂b^n/2 + V₁) = UVbⁿ + U₂V₁b^n/2 + U₁V₂b^n/2 + U₁V₁.

Вычисление произведения предлагаемым способом требует четырех умножений чисел половинной длины, трех сложений и трех умножений на величину b^q. Умножения на степень b равносильны сдвигу и требуют времени O (n). То же можно сказать о сложности аддитивных операций.

Четырех умножений чисел оказывается слишком много: log₂4 = 2, сложность рекурсивного алгоритма будет равна O (n²).

Но можно немного преобразовать расчетную формулу:

UV = U₂V₂ (bⁿ + b^n/2) + (U₂ - U₁) (V₁-V₂) b^n/2 + U₁V₁ (b^n/2+1)

Она содержит только три умножения. Очевидный алгоритм, строящийся по этой формуле, описывается уравнением для функции сложности:

Т (n) = 3Т (n/2) + вⁿ,

его решение Т (n) = O (n^log3) = O (n^1,58), что значительно лучше классического алгоритма.

Возведение целого числа без знака в положительную целую степень