Меню
Главная
Авторизация/Регистрация
 
Главная arrow Информатика arrow Алгоритмы и структуры данных

КЛАССЫ СЛОЖНОСТИ

i>Предварительные замечания

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

Помимо выделения частных групп осуществляется классификация задач — выделение непересекающихся совокупностей задач с целью фиксации закономерных связей между этими совокупностями. Можно указать общую и частную классификации. Общая классификация категорирует все возможные задачи. Частная классификация используется в теории вычислительной сложности и подразделяет на классы только одну частную категорию — распознавательные задачи.

Общая классификация задач

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

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

  • 1) перечень исходных данных — переменных без учета их конкретных значений, поэтому иногда называемых свободными переменными; в программах для ЭВМ эти переменные называются формальными параметрами;
  • 2) свойства, которыми должно обладать решение задачи.

Частная задача формируется из массовой задачи путем присвоения всем свободным переменным конкретных значений.

Массовые задачи, имеющие решение в форме алгоритмов, называются алгоритмически разрешимыми. В общем случае, для любой алгоритмически разрешимой задачи существует несколько разрешающих алгоритмов. Цель теоретического исследования задачи имеет две составляющие:

  • 1) доказательство алгоритмической разрешимости;
  • 2) отыскание наиболее простого (наименее трудоемкого) алгоритма решения.

Если задача не разрешима алгоритмически, то для ее решения используют процедуры, называемые эвристическими алгоритмами, которые используют знания — опыт интуитивного решения подобных задач специалистами конкретной предметной области и (или) некоторую формализацию таких субъективных понятий как «рационально» и «целесообразно». Формально такие процедуры алгоритмами не являются. Они могут не обладать свойством массовости, и обеспечивать получение результата только для некоторых частных наборов исходных данных. Они могут не обладать свойством конечности, и не гарантировать получение решения за конечное время. Они могут не обладать даже свойством результативности, — вообще, не гарантировать получение ответа за какое бы то ни было время.

Так же, как и для алгоритма, для задачи определяется понятие сложности. Сложность задачи — это минимальная из сложностей всех возможных алгоритмов решения этой задачи. Другими словами: если х, Л2,..., Ак } — множество алгоритмов решения задачи Z , каждый из которых характеризуется асимптотически точной верхней оценкой функции трудоемкости g(n) , g2(n) ,..., gk(n), то сложность g{n) задачи Z определяется так: g(n) = min(gl(n),g2(n),...,gk(n)), поэтому g(n) < g| (п) < g2 (л) < gk (л).

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

  • 1) можно ли доказать существование алгоритма минимальной сложности для заданной задачи?
  • 2) можно ли доказать, что предложенный алгоритм является минимальным или не минимальным?

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

Алгоритмически разрешимые задачи делятся еще на две группы: практически разрешимые, или полиномиальные и трудноразрешимые.

Для первой группы задач разработаны алгоритмы, трудоемкость которых полиномиально зависит от количества входных переменных (длины входа) п, и поэтому может решаться за полиномиальное время. По этой причине практически разрешимые задачи имеют дополнительное название — полиноминально разрешимые задачи. Они могут успешно решаться на ЭВМ даже в тех случаях, когда имеют «большую размерность».

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

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

Некоторые задачи не могут решаться иначе, как путем полного перебора вариантов, причем с экспоненциальной трудоемкостью. Такие задачи, как и алгоритмически не разрешимые, представляют интерес для теории искусственного интеллекта, поскольку являются стимулом для разработки и предметом приложения методов четкого и нечеткого логического вывода, генетических алгоритмов, иммунных сетей и иных эвристических алгоритмов, обеспечивающих сокращение времени решения за счет отказа от гарантии получения точного решения. Выдаваемый ответ может быть весьма близким к точному решению, а часто и совпадает с ним. Но могут наблюдаться и неудачи, — когда ответ оказывается далеким от точного решения или вовсе сводится к заключению аналогичному следующему: «Решение не может быть найдено. Попробуйте изменить начальные приближения».

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

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

Исторически первой распознавательной задачей, детально исследованной в теории алгоритмов, является задача о выполнимости булевой функции. С позиции математической логики сама распознавательная задача может интерпретироваться как некоторый предикат Р(х) — логическая функция п входных переменных задачи, объединенных в вектор Х = Хр Х2, Хп.

Существуют задачи, которые изначально, подобно задаче о выполнимости булевой функции, имеют распознавательную форму. Например, следующая задача явно распознавательная: являются ли два графа изоморфными? Одновременно с этим, многие задачи, имеющие иную начальную формулировку, могут легко трансформироваться в распознавательную задачу. Показателен следующий пример: задача «найти к — хроматическое число заданного графа» трансформируется в задачу итерации распознавательной задачи «является ли истинным утверждение о том, что заданный граф является ^-раскрашиваемым, где к — заданное натуральное число»; указанная распознавательная задача решается многократно — до достижения истинности утверждения. Таким образом, получена новая задача, решаемая перебором.

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

Схема общей классификации задач показана на рис. 7.1.

Классификация распознавательных задач

Базовым классом в классификации распознавательных задач является класс с названием NP . Название представляет собой сокращение (аббревиатуру) от словосочетания «Nondeterministic Polynomial time» — недетерминированное (случайное) время. В этот класс входят подклассы с названиями Р — от Polynomial time —

Общая классификация задач

Рис. 7.1. Общая классификация задач

и NPC — от Non-deterministic Polynomial-time Complete. В русскоязычных источниках задачи класса NPC часто называются NP -полными.

На рис. 7.2 показано отношение между указанными классами.

Классы сложности распознавательных задач

Рис. 7.2. Классы сложности распознавательных задач

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

Диаграмма классов сложности распознавательных

Рис. 7.3. Диаграмма классов сложности распознавательных

задач в форме подмножеств

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

Самым показательным примером ]МР задачи является задача о сумме: дано множество целых чисел А = {а{2, ...,я„} мощностью п и целое число V; можно ли из множества А выбрать такие числа, чтобы их сумма равнялась у ? Известно, что из множества мощностью п можно сформировать 2" подмножеств. Каждое из этих подмножеств можно представить конкретным значением вектора х = (х12,...,хп), у которого все элементы могут принимать значение

либо ноль, либо единица, т.е. х, е {0;1}, / = 1 ;п.

Процедура решения задачи состоит из последовательности проверок справедливости равенства ?ых/й/ = 1’ . Очевидно, что количество таких проверок равно 2" . Это означает, что верхняя точная асимптотическая трудоемкость задачи о сумме имеет вид /(п) = 0(2п), — поскольку для получения ответа на вопрос задачи может потребоваться выполнение всех возможных проверок. Нижняя точная асимптотическая трудоемкость: /(п) = ?2(1), — первая же проверка может дать утвердительный ответ на поставленный вопрос. Для проверки справедливости равенства требуется всего п умножений и «-1 сложений, следовательно, сложность этой проверки: 0(/7), т.е. является линейной (полиномиальной).

Класс Р образуют практически разрешимые распознавательные задачи, — для которых созданы алгоритмы с полиномиальной асимптотической трудоемкостью вида /(я) = &(пк) или /(л) = 0(пк).

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

Особым и чрезвычайно важным подклассом класса 1ЧР является подкласс 1ЧРС. Задачи 1ЧРС обладают следующими чрезвычайно интересными свойствами:

  • 1) все задачи этого класса сводятся к задачам этого же класса за полиномиальное время;
  • 2) все прочие задачи класса 1УР за полиномиальное время сводятся к задачам 1РС , но только в одну сторону — обратное сведение задачи 1ЧРС к произвольной 1ЧР задаче не возможно!

Во множестве задач существует дерево сведений задач друг к другу, фрагмент которого показан на рис. 7.4. На вершине этого дерева размещается исторически первая 1ЧРС задача — задача о выполнимости схемы. Позднее появилась частная форма этой задачи — задача о вычислимости логической функции, и еще позднее — задача о конъюнктивной форме. Исходная формулировка задачи такова:

  • 1) дана схема, состоящая из функциональных элементов «И», «ИЛИ», «НЕ», имеющая п битовых входов хх2,...,хп и один выход; количество элементов в схеме — не более чем 0(пк);
  • 2) выполняющим набором значений из множества {0; 1} на входе схемы, называется такой набор входов — значений хх2,...,хп , при котором на выходе схемы будет значение «1»;
  • 3) существует ли для данной схемы выполняющий набор значений входа?

Указанная задача принадлежит классу ^, поскольку проверка предъявленного выполняющего набора требует выполнения не более чем 0(пк) операций, т.е. может быть выполнена за полиномиальное время.

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

В худшем случае придется проверить все 2" возможные значения входа.

Указанные факты позволяют предполагать, что сложность данной задачи такова: /(п) = 0(пк -2п); /(п) = 0.(пк). Таким образом, у задачи о выполнимости схемы полиномиальна только нижняя асимптотически точная оценка трудоемкости. Верхняя оценка представляет собой произведение полиномиальной и показательной (экспоненциальной) оценок.

Определение: задача распознавания Z является задачей ,

если она удовлетворяет следующим условиям:

  • 1 ^является ^ задачей;
  • 2) любая задача № может быть сведена к задаче Zза полиномиальное время.

Если первое условие проверяется легко — достаточно показать проверяемость решения задачи за полиномиальное время, — то второе является, скорее, чисто формальным — использовать его для квалификации задачи практически невозможно. Для выяснения факта принадлежности задачи Z к классу используется следующий признак:

задача распознавания Z является задачей , если какая-либо

задача может быть сведена к задаче Z за полиномиальное

время.

Недетерминированная машина Тьюринга

В основах теории алгоритмов излагаются сведения о машине Тьюринга, схематично показанной на рис. 7.5 [14], — исторически первом формализме понятия алгоритма.

Лента

Головка

#

о

Л

И

М I П 1 И

а

д

а

#

Управление

Программа

Состояние

Рис. 7.5. Условная схема машины Тьюринга

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

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

В более поздних исследованиях, связанных с алгоритмически неразрешимыми задачами и оценками сложности алгоритмов и задач, было введено понятие недетерминированной (случайной) машины Тьюринга [15]. Различие между указанными вариантами машины состоит в том, что в детерминированной машине, каждой комбинации текущего символа под головкой и текущего состояния управляющего устройства соответствует единственная команда, определяющая записываемый на ленту символ и направление перемещения головки. В недетерминированной машине существует хотя бы одна пара <Символ под головкой Ccurrent'•>Текущее состояние Scurrent >, для которой задано две или более команды вида: <3аписать символ Cnew ; Перейти в состояние Snew; Переместиться на шаг влево|вправо|остаться>.

Естественно возникают два вопроса: 1) как же работает такая машина с элементами неопределенности? 2) зачем она нужна?

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

  • 1) машина наделяется волшебными способностями: при наступлении ситуации неопределенности — наличия нескольких возможных команд для исполнения — она всегда угадывает команду, наиболее быстро ведущую к попаданию в одно из конечных (допускающих) состояний (final or accepting states); для обычного компьютера это соответствует угадыванию команды, наиболее быстро ведущей к получению искомого результата;
  • 2) в каждой ситуации неопределенности происходит разветвление вычислительного процесса путем клонирования ленты и управляющих устройств; количество ветвей при этом, естественно, равно количеству команд, которые можно начать выполнять; образуется множество параллельных процессов; считается, что исходный вычислительный процесс закончился, если хотя бы в одной ветви достигнуто конечное состояние.

Применяется недетерминированная машина Тьюринга для воображаемой реализации алгоритмов решения трудноразрешимых задач, в том числе NP задач. Считается, что NP задачи разрешимы на недетерминированной машине Тьюринга за полиномиальное время. Таким образом, если бы недетерминированная машина Тьюринга могла бы эмулироваться на современных реальных компьютерах, то проблемы полиномиальной разрешимости NP задач просто бы не существовало. Действительно, представим, что задача о разрешимости схемы решается на ЭВМ, реализующей одновременно 2п процессов вычисления выходного значения схемы, — естественно, каждый процесс использует собственный набор исходных данных, и проверяет, не является ли этот набор выполняющим. После выполнения 0(пк) операций (по числу элементов в схеме) в каждом процессе искомый ответ будет получен. Очевидно, что временная сложность теперь стала полиномиальной, а именно / Гте{п) = 0(пк), хотя операционная сложность, конечно же, осталась прежней:

т=о(пк-2п).

В современных компьютерах распараллеливание вычислительных процессов применяется широко. Однако, в подавляющем большинстве случаев это не подлинное распараллеливание, а поочередное выделение промежутков процессорного времени различным процессам. Подлинное распараллеливание предполагает наличие в ЭВМ количества процессоров, равного числу одновременно выполняемых процессов. При экспоненциальном возрастании количества экземпляров решаемой задачи подлинное распараллеливание процессов становится технически не возможным. В настоящее время даже суперкомпьютеры способны решать за полиномиальное время задачу о разрешимости схемы для числа входов п не более 10—14. В то же время суперкомпьютеры имеют исключительно высокую производительность и способны решать в «последовательном» режиме задачи с экспоненциально растущим временем. Число входов п при этом находится как решение уравнения пк - 2п = Р, где Р — производительность вычислителя, т.е. количество актуальных операций, выполняемых в единицу времени. Производительность ЭВМ в количестве актуальных операций оценить можно только косвенно, — явно время вычисления отдельных логических операций в технических параметрах ЭВМ не указывается. Косвенная оценка количества логических операций, выполняемых за одну секунду отечественным суперкомпьютером Ломоносов, составляет примерно 7,125-Ю17. Несложно установить, что при к = 2 за одну секунду на Ломоносове можно решить задачу о выполнимости схемы только для п- 45 . За сутки положение дел улучшается не на много: число входов увеличивается только до п = 56. За год можно решить эту же задачу для п = 64 — всего на 19 входов больше по сравнению с односекундным решением. Вот, что такое экспоненциальное время решения задачи!

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

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

NP-трудные задачи

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

Имеет место следующее свойство: все задачи NPC сводимы к задачам NPH и, как следствие, транзитивно все NP задачи сводимы к задачам NPH . Примечателен следующий факт: очень часто задачи NPH определяются как задачи, к которым сводятся все задачи NP ; при этом задачи NPH , входящие в NP, называются задачами NPC. Такое определение пересекает NPH и NP по совокупности задач, что не представляется целесообразным.

Схематично взаиморасположение классов сложности P , NPC, NP и NPH показано на рис. 7.6, на котором использовано традиционное представление задач в виде точек плоскости. Овалы символизируют множества задач разных классов. Стрелки символизируют факт сводимости всех задач NP к задачам классов NPC и NPH : стрелка 1 показывает сводимость задач Р к задачам NPC ; стрелка 2 — сводимость промежуточных задач к задачам NPC , стрелка 3 — сводимость NPC к задачам этого же класса; стрелка 4 — сводимость всех задач NP к задачам NPH . Промежуточными называются задачи из множества задач NP, для которых пока не найдены полиномиальные алгоритмы решения, и, в то же время, не являющиеся задачами NPC — ни к одной из них невозможно свести ни одну из задач класса NPC. Совокупность промежуточных задач обычно обозначают аббревиатурой NPI ( I от слова intermediate — промежуточный). Очевидно равенство: NPI = NP P NPC .

Обратим внимание на наличие координатных осей на рис. 7.6. При этом ось абсцисс образно разделяет задачи по уровню сложности их решения: чем правее на плоскости расположена условная точка задачи, тем труднее ее решить. Ось ординат разделяет задачи по сложности проверки их решения. При этом принципиально выделение двух кардинально различных уровней сложности: на первом уровне размещаются задачи с легко (полиномиально) проверяемыми решениями; на втором — задачи, решения которых не могут быть проверены за полиномиальное время, т.е. это уровень труднопрове-ряемых задач. Из рисунка наглядно видно, что задачи класса NPH являются одновременно и труднорешаемыми, и труднопроверяемы-ми. Взаимное расположение овалов, изображающих задачи NP и NPH , по горизонтали отражает факт частичного пересечения задач классов NPC и NPH по сложности их решения.

Сложность решения задачи

Рис. 7.6. Условная схема соотношения степеней сложности

задач классов NP и NPH

Проблема Р = NР ?

Первые классы сложности задач были определены в работах Алана Кобхема (Alan Cobham) в 1964 г. и Жака Эдмондса (Jack Edmonds) в 1965 г. Проблема совпадения или различия классов Р и NP6buia сформулирована Эдмондсом в следующей форме: можно ли за полиномиальное время решить все те задачи, проверка решения которых имеет полиномиальную сложность?

Понятие NP-полноты предложил 1971 г. Стивен Кук (Stephen Cook) [16]. В том же году была доказана знаменитая теорема Кука-Левина, утверждающая, что задача о выполнимости булевой функции, представленной в КНФ (SAT) является NP -полной.

Как указывалось ранее, все прочие задачи NP сводимы к задачам NPC и все задачи NPC сводимы к задачам этого же класса за полиномиальное время. Этот факт означает следующее: если хотя бы для одной NPC задачи когда-либо будет найден алгоритм с полиномиальной операционной сложностью, то все задачи класса NP автоматически станут задачами класса Р. Доказательства отсутствия возможности нахождения полиномиального алгоритма для NPC задач нет. Поэтому проблема выяснения вопроса о совпадении или различии классов Р и NP в силу длительности своего существования отнесена к числу проблем века. Американский математический институт Клея (CMI) предлагает миллион долларов США тому, кто представит доказательство того, что Р = NP или Р Ф NP .

 
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Пред   СОДЕРЖАНИЕ   След >
 

Популярные страницы