Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Гл. 7. Пересечения
пересечение N полуплоскостей. Целевая функция определяет семейство параллельных прямых ах + by + к = О, где X — действительный параметр. Те прямые из этого семейства, которые являются опорными для допустимой области, проходят через ее вершины, доставляющие минимальное и максимальное значения целевой функции (рис. 7.19).
Рис. 7.19. Задача линейного программирования с двумя переменными. Верхняя стрелка указывает целевую функцию, заданную семейством параллельных прямых. Нижняя стрелка указывает минимизирующую вершину, определенную прямой, опорной к допустимой области.
Поскольку мы уже умеем определять прямые, опорные к выпуклому ЛЛугольнику, за время О (log N) (см. разд. 3.3.6), то получаем преобразование
ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ С ДВУМЯ ПЕРЕМЕННЫМИ ос„ ПЕРЕСЕЧЕНИЕ ПОЛУПЛОСКОСТЕЙ,
и, используя результат предыдущего раздела (теорему 7.10), получаем следующую теорему:
Теорема 7.11. Задачу линейного программирования с двумя переменными и N ограничениями можно решить за время 0(N log N). После того как она решена, экстремум новой целевой функции можно найти за время 0(logN).
Во-первых, сравним этот подход с симплекс-методом [Gass (1969)]. Если известно одно начальное допустимое решение, то симплекс-метод реализует движение от вершины к вершине по допустимой области, тратя O(N) времени на
7.2. Плоские приложения
каждом шаге. Легко видеть, что в худшем случае в симплекс-методе придется посетить все вершины с затратой общего времени 0(N2). (В этом отношении он очень похож на алгоритм Джарвиса из разд. 3.3.2.) Далее для максимизации новой целевой функции симплекс-метод должен проверить каждое ограничение, и поэтому он потратит O(N) времени. Другими словами, симплекс-метод неоптимален.
Необходимо указать, что метод явного построения допустимого политопа нереалистичен для задачи линейного программирования при больших размерностях, поскольку число вершин может зависеть экспоненциально от числа размерностей (см. разд. 3.1).
Одна из поразительных черт алгоритма симплекс-метода состоит в том, что, хотя известна его экспоненциальная зависимость от числа измерений в худшем случае (и квадратичная оценка при двух переменных), его реальное поведение на практике почти всегда превосходно1). Аналогичное поведение демонстрирует и метод, основанный на пересечении полуплоскостей для широкого класса исходных данных [Bentley, Shamos (1978)]. Этот подход уже использовался нами, например, в разд. 4.1.1, а именно: если математическое ожидание размеров решений подзадач мало, то шаг слияния в алгоритме «разделяй и властвуй» можно реализовать за менее чем линейное время. Это будет иметь место, если многие из полуплоскостей избыточные, т. е. не образуют ребер допустимой области. А сейчас покажем, что для случайных исходных данных, как можно ожидать, большинство полуплоскостей будут избыточными.
Интуитивно понятно и практически легко представимо какое-либо естественное распределение вероятности положения случайных точек на плоскости; менее очевдино то, как можно моделировать случайный выбор полуплоскостей. Однако если прибегнуть к фундаментальному геометрическому преобразованию, введенному в разд. 1.3.3 и известному как поляритет (двойственность) (которое найдет себе важное применение в разд. 7.3), то можно сделать следующее наблюдение. Поляритет— это инволютивное преобразование «точка ¦<->- прямая». С каждой прямой свяжем полуплоскость (содержащую начало координат). Предположим, что нам досталось множество S из N случайных точек, лежащих в какой-нибудь области (скажем, в единичном круге), и мы отображаем их в полуплоскости. Точки, лежащие на выпуклой оболочке 5, перейдут в такое множество прямых, каждая из которых содержит ребро из общей области пересечения этих полуплоскостей. Поэтому, вспоминая результаты, процитированные в разд. 4.1.1, полу-
') То есть полиномиально. — Прим. перев. 12*
356
Гл. 7. Пересечения
чим, что математическое ожидание числа неизбыточных полуплоскостей в множестве из N полуплоскостей для данного случая равно 0(Np), р < 1; похожие результаты справедливы и для других, достаточно естественных случайных моделей. Отсюда следует, что для задачи пересечения N полуплоскостей получается линейная оценка среднего поведения алгоритма. А это немедленно ведет к оценке O(N) для среднего поведения алгоритма решения задачи линейного программирования с двумя переменными. Мы видим, что математическое ожидание числа избыточных полуплоскостей — таких, которые не определяют ребер допустимой области, — очень велико, что может, в частности, объяснить прекрасное поведение симплекс-метода.
Однако нельзя успокаивать себя тем, что математическое ожидание временной оценки алгоритма построения допустимой области пропорционально O(N), поскольку, как упоминалось в разд. 7.1.4, такое построение не является необходимым для решения задачи линейного программирования! Многие годы это наблюдение было бесплодным, до тех пор пока недавно чрезвычайно удачный метод, основанный на нем, не был независимо открыт Меджиддо [Megiddo (1983)] и Дайером [Dyer (1984)]. Этот метод (который легко адаптируется для случая трех измерений и был обобщен Меджиддо [Megiddo (1983)] на любое число измерений) отбрасывает не только избыточные ограничения (т. е. такие, которые не нужны и в задаче о пересечении полуплоскостей), но также и ограничения, гарантирующие отсутствие вершины, доставляющей экстремум целевой функции (называемой оптимальной вершиной). Этот метод основан на применении к точкам плоскости такого линейного преобразования, при котором целевая функция становится равной одной из двух координат, скажем ординате этой плоскости. После этого задача сводится к поиску экстремального значения некой кусочно-линейной выпуклой функции от абсциссы. Ключевой момент заключается в том, что поскольку требуется лишь определить экстремальное значение х0, то нет нужды явно строить эту выпуклую функцию, которая неявно задана множеством линейных ограничений.
