|
|
|
||||||||||||||||||||||||||||
![]() |
ВведениеВ первой части этой статьи (см.[1]) было рассказано об основных идеях современной теории сложности дискретных задач - теории Кука- Карпа. Содержание этой теории в предельно сжатой форме можно охарактеризовать так. Рассматривается широкий класс NP дискретных задач, для решения которых может быть использован универсальный, но малоэффективный из-за высокой трудоемкости алгоритм прямого перебора. Для относительно небольшого числа задач из NP удалось придумать эффективные, то есть полиномиальные по трудоемкости, алгоритмы; эти задачи образуют класс P. Для другой, весьма значительной части задач показано, что они являются максимально сложными в NP; такие задачи названы NP-полными. NP-полные задачи объединяет то, что, во-первых, для каждой из них неизвестен полиномиальный алгоритм, и, во-вторых, из полиномиальной разрешимости любой из них следовала бы полиномиальная разрешимость остальных. С последним утверждением связана центральная проблема теории сложности, остающаяся до сих пор открытой: полиномиальные алгоритмы для NP-полных задач не удается придумать потому, что таковые принципиально невозможны, либо когда-нибудь кому-нибудь посчастливится построить полиномиальный алгоритм для какой-нибудь NP-полной задачи и тем самым будет установлена полиномиальная разрешимость всех задач из NP. Эта знаменитая проблема привлекает внимание многих исследователей и стимулирует поиск новых подходов к ее решению. Об одном из таких подходов идет речь ниже в этой части работы. 1. Постановка вопросаПоговорим немного о смысле проблемы. Итак, в NP есть две категории задач - задачи, для которых придуманы полиномиальные алгоритмы, и задачи, для которых такие алгоритмы не удается сконструировать. В таком виде различие между задачами выглядит субъективно, и проблему можно сформулировать так. Требуется выяснить, имеются ли для этого субъективного различия объективные основания. Выделим в этих фразах слова "различие между задачами", чтобы связать с ними дальнейший рассказ. Если согласиться с тем, что затронутая проблема исключительно трудна и важна, а так считают практически все специалисты, можно попытаться обнаружить признак, не обязательно характеризующий напрямую сложность задач, но отличающий полиномиально разрешимые задачи от NP-полных. Ясно, что этот признак следует искать в конструкциях, связанных с задачами. Одной из таких конструкций, попавших в поле зрения исследоваателей, является многогранник задачи. И прежде чем обратиться к ассоциированным с задачами многогранникам, поговорим немного о многомерных выпуклых многогранниках вообще. 2. Выпуклые многогранники
Обозначим, как обычно, через Rm евклидово m-мерное пространство,
элементы которого x = (x1,..., xm) называются точками, или векторами.
Операции сложения и умножения на число определяются в Rm
формулами:
x + y = (x1 + y1,... xm + ym ), αx = (αx1,..., αxm ),
а величина
(x,y) =
Любой выпуклый многогранник можно определить иначе - в виде
множества решений некоторой системы линейных неравенств:
M = {x
Пусть M - некоторый многогранник, X - множество его вершин. Две
вершины x,y
К изучению выпуклых многогранников приводят многие задачи, в
числе которых особенно важные в прикладном отношении задачи
линейного программирования. В случаях, когда размерность m
пространства мала: m Зададимся вопросом, сколько попарно смежных вершин может быть у выпуклого многогранника в Rm . При m, равных 2 и 3, ответ почти очевиден: не более трех в R2 и не более четырех в R3 (соответственно, для треугольника и для тетраэдра). Теорема 1. Для любого натурального n в R4 существует выпуклый многогранник с n попарно смежными вершинами.
Доказательство. Рассмотрим в R4 множество точек
? = {(t, t2, t3, t4) : t Пусть теперь n - произвольно выбранное натуральное число. Рассмотрим n различных точек кривой ? : x1,..., xn , и обозначим M = conv {x1,..., xn} . По доказанному, для любых двух вершин xi и xj этого многогранника найдется гиперплоскость H, в которой лежат эти вершины, а остальные находятся в H+. Так как H и H+ - выпуклые множества, не имеющие общих точек, отрезок [xi,xj] не пересекается с выпуклой оболочкой остальных вершин, то есть xi и xj - смежные вершины. Теорема доказана. Доказанное утверждение имеет любопытную историю. Впервые оно было установлено и опубликовано в 1907 году немецким математиком К.Каратеодори, но осталось незамеченным. Спустя много лет, в 1956 году этот результат появляется в статье американского математика Д.Гейла и приобретает широкую известность благодаря линейному программированию, которое в то время интенсивно развивалось. В дальнейшем на его основе были открыты фундаментальные факты современной теории выпуклых многогранников; подробнее об этом можно прочитать в книге [2]. 3. Многогранники задачМногие дискретные задачи естественным образом приводятся к геометрическому виду, и это дает возможность алгоритмические свойства задач интерпретировать в терминах понятий геометрии. Такая возможность в первую очередь характерна для дискретных задач оптимизации, их часто называют задачами комбинаторной оптимизации; именно о них будет идти речь далее. Большинство задач комбинаторной оптимизации объединяет то, что их можно рассматривать как задачи отыскания минимума (или максимума) линейной функции на конечном множестве точек в пространстве Rm. Как осуществляется этот переход, достаточно общим образом можно продемонстрировать на примере задачи коммивояжера.
Предположим, что расматривается задача коммивояжера для n
пунктов, которые занумерованы числами от 1 до n . Обозначим через m
количество пар этих пунктов: m = n(n-1)/2, и координаты точек x в
пространстве Rm поставим в соответствие парам пунктов:
x = (xji: 1
Предположим теперь, что заданы расстояния cij между пунктами; их
совокупность будем рассматривать в виде вектора из Rm: c = (cij:1 К описанному виду совершенно аналогично приводится задача задача о минимальном остовном дереве и многие другие. Пусть X - некоторая задача, X ? Rm. Рассмотрим две геометрические конструкции, связанные с X. Обозначим через M(X) выпуклую оболочку множества X : M(X) = conv X, и назовем ее многогранником задачи X . Без ограничения общности можно считать, что множество вершин многогранника M(X) совпадает с X .
Зафиксируем x
Для многогранника M(X) задачи и множества конусов K(x), x Теорема 2. Конусы K(x) и K(y) имеют общую гипергрань (то есть грань размерности m-1) в том и только том случае, если x и y - смежные вершины многогранника M(X).
Немного отвлекаясь от основной темы, заметим, что последнее
утверждение приводит к весьма неожиданному факту элементарной
геометрии. Пусть X - конечное множество точек циклической кривой ? в
R4. Из доказанной ранее теоремы 1 и из теоремы 2 вытекает, что любые
два конуса K(x) и K(y), где x,y В пространстве R3 можно построить произвольно много выпуклых многогранников без общих внутренних точек, каждые два из которых имеют общую плоскую грань. 4. Плотность полиэдрального графа задачиПродолжим разговор о геометрических конструкциях, связанных с задачами комбинаторной оптимизации. Обозначая, как и ранее, через X некоторую задачу, X ? Rm, рассмотрим граф G(X) многогранника M(X); множеством вершин этого графа служит X , а ребрами являются геометрические ребра многогранника. Граф G(X) называется полиэдральным графом задачи X . Обозначим через p(X) максимальное количество попарно смежных вершин графа G(X), эта характеристика графа называется его плотностью. Плотность полиэдрального графа задачи оказывается именно той величиной, поведение которой отражается на степени труднорешаемости задачи. В основе этой зависимости находится следующая интерпретация величины p(X), непосредственно вытекающая из теоремы 2. Теорема 3. Значение p(X) равно максимальному количеству таких точек из X, что для любых двух x и y из них соответствующие конусы K(x) и K(y) имеют общую гипергрань. Ниже, где речь пойдет о геометрических свойствах алгоритмов, роль теоремы 3 проявится более определенным образом. Сейчас же остановимся на результатах исследований, связанных с оценками плотности полиэдральных графов для известных задач.
До сих пор рассуждения проводились в предположении, что
размерность m пространства Rm фиксирована. Теперь обратим внимание
на то, что понятие "задача" приводит к рассмотрению последовательности
конечных множеств Xm ? Rm, где m может принимать как угодно большие
значения. Так, в примере с задачей коммивояжера m = n(n-1)/2 , а число
пунктов n - произвольное натуральное. Соответственно, и величина p(Xm)
является последовательностью, значения которой меняются в
зависимости от m. В большой серии работ, опубликованных в течение
последних десяти лет, изучалось поведение плотности p(Xm)
полиэдральных графов различных задач комбинаторной оптимизации. В
итоге обнаружилась весьма любопытная закономерность: для всех
полиномиально разрешимых задач плотность p(Xm) ограничена сверху
степенной функцией от m и для каждой NP-полной задачи p(Xm) растет
быстрее, чем любая степенная функция. Иначе говоря, p(Xm)
полиномиальна для эффективно разрешимых задач и неполиномиальна
для труднорешаемых. В частности, для задач, которые обсуждались в
настоящей статье, справедливы следующие оценки:
- для задачи о минимальном остовном дереве
p(Xm) Таким образом, характер роста величины p(Xm) служит, различающим задачи по сложности, о существовании которого ставился вопрос во введении. Естественно возникает новый вопрос: является обнаруженная зависимость между сложностью задачи и плотностью ее полиэдрадьного графа случайной или имеет теоретическое объяснение. Чтобы попытаться ответить на этот вопрос, нам придется поговорить об алгоритмах. 5. Геометрическая интерпретация алгоритмов
Общее свойство всех алгоритмов комбинаторной оптимизации,
которое проявляется даже при поверхностном знакомстве с ними, состоит
в том, что выбор оптимального элемента x* в множестве X происходит в
результате выполнения конечной последовательности линейных
сравнений для вектора c*
Указанное общее свойство алгоритмов допускает простую
геометрическую интерпретацию процедуры решения индивидуальной
задачи. Как было отмечено ранее, индивидуальная задача для вектора c*
заключается в отыскании такого x* Предположим теперь, что для некоторых p точек из X каждые два конуса K(x) и K(y) имеют общую гипергрань. Предположим также, что точка c* принадлежит одному из этих p конусов, но заранее не известно, какому именно. Рассмотрим в Rm гиперплоскость H вида (3) и образуемые ею полупространства H+ и H- . Тогда справедливо утверждение: хотя бы одно из этих полупространств содержит точки по крайней мере p-1 конусов. (Это утверждение наглядно для R3, правда, в таком случае p не может быть больше четырех, и легко доказывается для произвольного m .) Отсюда следует, что для гарантированного отыскания конуса, который содержит точку c*, потребуется не меньше p-1 шагов описанного выше вида. Если связать этот результат с геометрической интерпретацией алгоритмов и учесть теорему 3, станет понятной роль плотности полиэдрального графа задачи как нижней оценки трудоемкости алгоритмов традиционного типа. ЗаключениеКакие выводы можно сделать в итоге ? Можно ли считать, что для задач с высокой плотностью полиэдрального графа не существуют (то есть не могут быть построены) полиномиальные алгоритмы ? Сразу же заметим, что из нашего рассказа утвердительный ответ на последний вопрос вовсе не следует. Более того, описанная интерпретация традиционных алгоритмов свидетельствует о достаточно примитивном единообразии их в геометрическом смысле, хотя в комбинаторном отношении часто эти алгоритмы вовсе не тривиальны. Поэтому нет смысла преувеличивать значение многолетних безуспешных попыток многих специалистов построить полиномиальные алгоритмы для NP- полных задач. Такие попытки без привлечения принципиально новых геометрических идей заведомо обречены на неудачу. Что же касается новых геометрических идей, следует особо отметить появившиеся относительно недавно полиномиальные алгоритмы для задачи линейного программирования; первый из них построил Л.Г.Хачиян в 1979 году. Геометрическая природа этих алгоритмов совершенно иная по сравнению с традиционными, что определяет их привлекательность в связи с изложенным в данной работе. Итак, высокая плотность полиэдральных графов, характерная для NP-полных задач, является серьезным препятствием при конструировании эффективных алгоритмов. Учитывая, что среди изученных задач значительное большинство составляют NP-полные, можно сделать следующее предположение. Если в многомерном пространстве случайным образом выбрать конечное множество точек X , то величина p(X) с высокой вероятностью будет принимать большие значения. Это предположение находит теоретическое подтверждение в работе [3]. В частности, при случайном выборе множества X из 25 000 точек, координаты которых равны нулю или единице, в 100-мерном пространстве с вероятностью 0.99 величина p(X) окажется равной количеству точек, то есть 25 000. Литература
|
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
||
![]() |
![]() |
|||
![]() |