4.3. Классификация задач по степени сложности

Как показывает опыт, любое более или менее близкое знакомство с той или иной областью формирует у каждого из нас “интуитивное представление” о том, что одна задача является “более трудной”, чем другая. Это чисто субъективное понятие не может нас удовлетворить. Однако можем ли мы определить истинную сложность задачи?

Понятию сложности и классификации вытекающих из него задач посвящен этот раздел.

Сначала поговорим о различии между математикой и информатикой: в информатике недостаточно высказать утверждение о существовании некоторого объекта в теории и даже недостаточно найти конструктивное доказательство этого факта, т. е. алгоритм. Мы должны учитывать противоречия пространства и времени, навязываемые нам миром, в котором мы живем: необходимо, чтобы решение можно было вычислить, используя объем памяти и время, приемлемые для человека или машины.

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

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

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

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

1. До какого состояния можно улучшать данный алгоритм? Известны ли для отдельных случаев методы оптимальной сложности? Каково число задач, которые хорошо решаются, т. е. задач невысокой степени сложности (например, или где — размерность входных данных)?

2. Приводит учет степени сложности к иной классификации задач и предлагаются ли какие-нибудь методы для перехода из одного класса в другой, от “трудной” задачи к более “простой”?

Ниже будут даны ответы на эти два вопроса. Они показывают, что для решения многих задач “классических” алгоритмических методов явно недостаточно и что перспективными являются исследования в области искусственного интеллекта.

4.3.1. Три класса задач

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

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

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

Другие хорошо известные алгоритмы — деление, извлечение квадратного корня, решение уравнений второй степени

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

Класс Р: полиномиальные алгоритмы

Мы называем “хорошей”, или принадлежащей классу Р, задачу, для которой известен алгоритм, сложность которого составляет полином заданной, постоянной и не зависящей от размерности входной величины степени.

Класс Е: задачи, экспоненциальные по природе

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

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

где — размерность входной величины, т. е. зависит от данных.

К ним относятся задачи распознавания правильных выражений на языках, имеющих относительно несложные алфавиты и правила построения единиц.

Заметим, что при небольших значениях экспоненциальный алгоритм может быть более быстрым, чем полиномиальный.

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

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

Задачи, не попадающие ни в класс Р, ни в класс Е

К этому классу относятся следующие задачи:

• Решение систем уравнений с целыми переменными (Dio-phante, 410).

• Определение цикла, проходящего через все вершины некоторого графа (цикл Гамильтона) (Hamilton. 1870).

• Существование среди заданных подмножеств некоторого избранного семейства, покрывающего данное множество.

• Составление расписаний (и соответственно раскрасок), учитывающих определенные условия (и соответственно бинарные отношения).

• Существование множества значений логических переменных, которые позволяют сделать значение произвольного заданного логического выражения ИСТИННЫМ (Cook, 1971).

• Оптимизация пути коммивояжера через сеть городов.

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

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

• Оптимальная загрузка емкости (рюкзак, поезд, корабль, самолет) при наименьшей стоимости.

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

• Диагностика (болезни, поломки, дефекты печатных схем).

Этот список можно продолжить.

Проблема состоит в следующем: можем ли мы надеяться, что какие-либо из этих задач попадут в класс Р?

К сожалению, в настоящее время ни для одной из этих задач не найдено полиномиального алгоритма.

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

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

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

хорошим алгоритмом, опять приводит к неполиномиальной сложности.