Сложность алгоритмов

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

Однако одновременно с этим возникли и новые проблемы, связанные с практической возможностью реализации алгоритмов на ЭВМ. Иначе говоря, встал вопрос: до каких значений можно увеличивать размерность задачи, чтобы её решение могло быть получено за приемлемое время и при этом хватало бы памяти машины для размещения в ней исходных, промежуточных и результирующих данных. В связи с этим встал вопрос разработки не любых алгоритмов, а наиболее эффективных, что обусловило появление нового направления в теории алгоритмов, важнейшей задачей которого стал анализ сложности алгоритмов. Начало развития этого направления связано с именами американских исследователей Кобхэма, Эдмондса (60-годы ХХ века), Кука и Карпа (70-годы ХХ века).

Обычно эффективность алгоритмов понимается в двух аспектах: по времени решения задачи и по объему требуемой для ее решения памяти. Поэтому говорят о временной сложности алгоритма (ВСА) и сложности в смысле требуемой памяти, иначе, пространственной сложности алгоритма (ПСА). Однако обычно под “самым эффективным” алгоритмом понимается самый быстрый, поскольку именно ограничение по времени является доминирующим фактором, определяющим пригодность конкретного алгоритма для практики.

Как уже отмечалось в начале данного раздела, одной из характерных черт алгоритма является его массовость, т.е. он должен быть применим для множества исходных данных некоторой задачи. В этом случае говорят о массовой задаче. Если исходные данные принимают некоторые конкретные значения, то задача называется индивидуальной. Размерность каждой индивидуальной задачи определяется объемом исходных данных (для ЭВМ эти исходные данные будут входными), требуемых для описания задачи. Обычно входные данные задаются в виде последовательности символов некоторого алфавита, число которых определяет входную длину индивидуальной задачи. Зависимость времени работы алгоритма от числа его шагов и представляет собой ВСА. Таким образом, ВСА – это функция, которая каждой входной длине n ставит в соответствие максимальное по всем индивидуальным задачам длины (наихудший случай) время, затрачиваемое алгоритмом на решение индивидуальных задач этой длины.

Надо отметить, что абсолютное время работы алгоритма не является объективной оценкой его временной сложности, так как оно зависит от быстродействия реализующей его ЭВМ. Чтобы оценка временной сложности различных алгоритмов была объективной, сравнивают не абсолютное время, а число шагов, за которое алгоритм решает индивидуальную задачу на некоторой абстрактной модели вычислительной машины. В качестве такой универсальной абстрактной модели обычно используется машина Тьюринга или одна из ее разновидностей, а ВСА представляют как оценку функции временной сложности где – некоторая функция, а n – входная длина.

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

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

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

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

Экспоненциальные алгоритмы получили свое название из-за того, что их временная сложность оценивается показательными функциями вида , а частным случаем показательной функции есть экспонента . К экспоненциальным относят и алгоритмы с функциями роста и некоторые другие, скорости роста которых так же велики, как у экспоненты.

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

n f(n)
n	0,00001 с	0,00002 с	0,00003 с	0,00004 с	0,00005 с	0,00006 с
n 2	0,0001 с	0,0004 с	0,0009 с	0,0016 с	0,0025 с	0,0036 с
n 3	0,001 с	0,008 с	0,027 с	0,064 с	0,125 с	0,216 с
n 5	0,1 с	3,2 с	24,3 с	1,7 мин	5,2 мин	13,0 мин
2 n	0,001 с	1,0 с	17,9 мин	12,7 дней	35,7 лет	столетий
3 n	0,059 с	мин	6,5 лет	столетий	2 108 столетий	1,3 1013 столетий

Из приведенной таблицы видно, что различие между полиномиальными и экспоненциальными алгоритмами особенно сильно проявляется при увеличении размерности задачи. При малых же размерностях экспоненциальные алгоритмы могут быть даже более эффективными. Так, экспоненциальная функция ведет себя лучше, чем полиномиальная функция при . Но при увеличении размерности n функция быстро “обгоняет” функцию . Это явление образно называют “проклятием размерности” или “тиранией размерности”. Оно подтверждает тот факт, что при малых размерностях различие между экспоненциальными и полиномиальными алгоритмами незначительны и, более того, экспоненциальные алгоритмы могут быть более эффективными, чем полиномиальные.

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

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

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

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

В качестве класса особых задач, которые мы назвали эталонными, Куком в 1971 году был выделен класс так называемых задач распознавания свойств. Эти задачи могут быть решены за полиномиальное время на НДВУ. Задачей распознавания свойств называется такая задача, решением которой может быть двоичный ответ: либо “1”, либо “0”, что соответствует утверждениям: “существует” либо “не существует”; “да” либо “нет”. Куком было также доказано, что одна конкретная задача из того же класса, называемая задачей о выполнимости, обладает тем удивительным свойством, что всякая другая задача из того же класса может быть сведена к ней за полиномиальное время.

Отсюда следует, что если задача о выполнимости может быть решена за полиномиальное время, то и любая задача из того же класса полиномиально разрешима. Если же какая-то задача, относящаяся к тому же классу, что и задача о выполнимости, труднорешаема, то и задача о выполнимости также должна быть труднорешаемой. Таким образом, задача о выполнимости в некотором смысле является “самой трудной” в классе задач, который назвали классом NP.

Аббревиатура NP происходит от английских слов nondeterministic (N) и polinomial (P) и означает класс всех задач распознавания, которые могут быть решены НДВУ за полиномиальное время. В отличие от этих задач класс задач, полиномиально разрешимых на детерминированной одноленточной машине Тьюринга (ДМТ), стали называть классом P (от слова polinomial).

После того как было введено понятие класса задач NP,было доказано, что многие хорошо известные комбинаторные задачи, будучи сформулированы как задачи распознавания, оказываются эквивалентными по трудности задаче о выполнимости. Этот класс эквивалентности, состоящий из “самых трудных” задач, принадлежащих к классу NP, получил название класса NP - полных задач. Иногда его называют классом универсальных задач, которые упрощенно понимают как задачи, для которых не найдены полиномиальные алгоритмы. Однако и не доказано, что таких алгоритмов вообще не существует.

Выше мы отметили, что класс P определятся через модель ДВУ, в качестве которой чаще всего принимается ДМТ, детально рассмотренная в подразд. 4.4. Класс же NP определяется через модель НДВУ, в качестве которой используется недетерминированная одноленточная машина Тьюринга (НДМТ). Это понятие мы еще не рассматривали, поэтому его следует уточнить.

НДМТ имеет почти такую же структуру, как и ДМТ, но отличается от последней лишь тем, что она дополнена угадывающим блоком со своей записывающей головкой W (write) – рис.2

Рис.2. Схематичное изображение НДМТ

На рис.2 обозначено: УУ − устройство управления; УБ − угадывающий блок; УГ − угадывающая головка; RW − головка чтения/записи; Л − бесконечная в обе стороны лента.

Назначение УБсостоит в том, чтобы записывать на ленту информацию о “догадке”. Работа НДМТ в отличие от ДМТ состоит из двух стадий. На первой стадии происходит “угадывание” решения, которое заключается в том, что угадывающая головка, двигаясь вдоль ленты, в каждый дискретный момент времени либо пишет в находящуюся под ней клетку одну из букв внешнего алфавита, либо останавливается. В первом случае угадывающий блок решает, продолжить ли работу, т.е. записывание букв в клетки ленты, или перейти в пассивное состояние, передав управление УУ. Причем делает это совершенно произвольно (случайно) до тех пор, пока не запишет на ленту слово-догадку.

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

Во втором случае УБпереходит в пассивное состояние, а УУ− в активное, начиная свою работу с состояния . С этого момента и начинается вторая стадия работы НДМТ − проверка. При этом головка чтения/записи совершенно аналогично тому, как это делается в ДМТ, проверяет записанное УГслово на соответствие его условиям задачи. Если соответствие будет установлено, то НДМТ переходит в состояние , в противном случае поиск решения продолжается.

Как с практической, так и с теоретической точек зрения важным является вопрос о взаимоотношении классов P и NP. Иначе говоря, является ли множество задач класса Р подмножеством задач класса NP, т.е. P ≠ NP?Этот вопрос был поставлен в 1971 г. и является сейчас одним из основных открытых вопросов современной математики и теоретической кибернетики. Среди специалистов широко распространено мнение, что P ≠ NP, хотя доказательство этой гипотезы пока отсутствует. Схематически гипотетическое взаимоотношение между классами P и NP представлено на рис.3

Рис.3. Гипотетическое взаимоотношение Рис.4. Уточненная картина классов Pи NP класса NP .

Как было отмечено выше, среди задач класса NP имеются “самые трудные”, которые отнесены к классу NP- полных задач. С учетом этого замечания, уточненная картина класса NP будет выглядеть так, как показано на рис.4.

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

Именно путем разработки и использования эвристических алгоритмов решается в действительности большинство практических задач. Особенно это ярко проявляется в области систем автоматизированного проектирования (САПР), где фактор “проклятия размерности” (например, современные микропроцессоры на кристалле площадью в несколько десятков мм² содержат от нескольких миллионов до сотен миллионов транзисторов, число которых и определяет размерность задачи) является основным стимулятором появления САПР.

В чем же смысл эвристических алгоритмов? Сначала несколько слов о происхождении широко сейчас распространенного слова эвристика (с греч. языка − находить, изобретать, выдумывать). Известная легенда приписывает восклицание “Эврика!” (“Я нашел!”) греческому математику и механику Архимеду, когда тот нашел способ определения количества вещества в некотором предмете, найдя соответствие между объемом и весом вытесненной жидкости при погружении в нее этого предмета.

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

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

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

Теоретически оценить погрешность эвристического алгоритма часто бывает затруднительно. В таких случаях используют метод статистического оценивания. Сущность этого метода заключается в автоматической генерации “случайных” индивидуальных задач с характеристиками, подчиняющимися заданному закону распределения вероятностей, прогонке этого множества задач через исследуемый алгоритм и статистической оценке результатов решений. Этот метод оценки точности эвристических алгоритмов считается многообещающим и можно ожидать получения с его помощью новых результатов.

Вопросы для самоконтроля

1. Дайте интуитивное определение понятию алгоритм.

2. Какими свойствами характеризуется алгоритм?

3. Сформулируйте тезис Черча.

4. Какие функции называются частично-рекурсивными, общерекурсивными?

5. Поясните операцию суперпозиции функций.

6. Поясните операцию примитивной рекурсии.

7. Поясните операцию минимизации.

8. Как устроена машина Тьюринга?

9. Сформулируйте тезис Тьюринга.

10. Как работает машина Тьюринга?

11. Дайте понятие о нормальных алгоритмах Маркова.

12. В чем суть алгоритмически неразрешимых проблем?

13. Что означает полиномиальная и экспоненциальная ВСА?

14. Что понимают под трудно решаемой задачей?

15. Какие задачи относят к классам P, NP и NP-полным?

16. Как соотносятся задачи классов P, NP и NP-полных?

Ответы и решения