4.2. Список хорошо решаемых задач (полиномиальные алгоритмы)

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

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

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

Вначале напомним две последние задачи:

- Рассортировать множество из чисел. (Сложность порядка

- Найти эйлеров цикл на графе из ребер. (Сложность порядка

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

- Обнаружить в тексте длиной некоторое слово. (Сложность

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

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

- Построить покрывающее дерево минимальной стоимости — число ребер) и сложностью O(mlogm) (Kruskal, 1956; Prim, 1957; Tarjan, 1977).

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

Многие другие задачи из теории графов также решаются за полиномиальное число шагов. Перечислим главные из них.

- Кратчайший путь на графе, состоящем из вершин и дуг. (Сложность 0{mn).) (Ford, 1965; Dijkstra, 1959; Dantzig, 1960; Floid, 1962.)

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

- Связанные компоненты. (Сложность 0(п2).) (Tremaux, 1882; Tarjan 1972.)

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

- Транзитивное замыкание. (Сложность 0(п2).) (Nolin, 1964; Warshal, 1965; Roy, 1965.)

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

- Максимальное пароеочетание. (Сложность .) (Веrge, 1962; Edmonds, 1965; Gabow, 1973; Bartnik 1978.)

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

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

- Максимальный поток. (Сложность и Fulkerson, 1950; Gondran и Minoux 1978.)

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

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

- Проверка планарности графа. (Сложность

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

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

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

задачам этого класса. Именно таким статусом долгое время обладало линейное программирование.

- Линейное программирование.

Речь идет о решении в пространстве К” системы линейных уравнений вида

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

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

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

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

Итак, вот уже в течение 20 лет симплекс-метод, постоянно дополняемый и улучшаемый, используется — и весьма эффективно! — во всем мире. Даже для задач большой размерности (например, при теоретической сложности порядка на практике отмечалась сложность порядка

Затем в 1979 г. Хачиян предложил для задачи линейного программирования полиномиальный алгоритм, существенно отличающийся от симплекс-алгоритма. И хотя он объясняет экспериментальный успех симплекс-метода, у него мало шансов “свергнуть” его с трона окончательно: при решении реальных задач симплекс-метод вполне пригоден.

Основное достоинство алгоритма Хачияна состоит в следующем: наконец, установлено, что некоторое семейство алгоритмов

вычислительной математики сходится с заданной точностью за полиномиальное число этапов.

Кроме того, алгоритм Хачияна завершает список полиномиальных, т. е. хорошо решаемых, задач: ведь в действительности они очень немногочисленны!

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

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