Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Более точно, исходную задачу1)
( минимизировать ах-{-by
\ при условиях atx -f bty 4- ct < 0, t = l, 2, N, ^7'^
можно преобразовать, полагая Y = ax 4- by и X = x, следующим образом (поскольку здесь а и b одновременно не равны
') В данной формулировке предположим без потери общности, что целевую функцию нужно минимизировать.
7.2. Плоские приложения
нулю, предположим без потери общности, что Ь ф 0): ( минимизировать У
1 при условиях atX + р,У -f ct < 0, /=1,2.....N,
(7.7)
где а, = (а,- — (а/Ь)Ы), a Pi = &«•/&. В новой задаче нужно вычислить наименьшее значение У на вершинах выпуклого многоугольника Р (допустимой области), определенного этими ограничениями (рис. 7.20). Чтобы избежать построения всей границы Р, поступим следующим образом. В зависимости от того,
Оптимальная вершина
Рис. 7.20. После преобразования координат нужно i нату в допустимой области.
шменыную орди-
будет ли р,- нулем, отрицательным или положительным числом, разобьем множество индексов {1, Щ на подмножества /0, /-, /+ соответственно. Все ограничения с индексами из /о являются вертикальными прямыми (т. е. параллельными оси У) и определяют допустимый интервал для X следующим образом (рис. 7.21):
щ - max {— с,/а,-: / е /0}, M2 = min{— с,/аг: /е/0}.
С другой стороны, полагая 8,А— (а,-/р\-) и у<А'-чаем, что все ограничения из /+ имеют вид
(с«/Р<), полу-
358
Гл.7. Пересечения
так что они, вместе взятые, определяют кусочно-линейную, выпуклую вверх функцию F+(X) вида
F+ (X) A min (6,Х + yt).
Аналогично ограничения из /_ в совокупности определяют кусочно-линейную, выпуклую вниз функцию F-(X) вида F_ (Х)Атах (6Д + yt).
i е /_
Затем получаем преобразованное ограничение
^F+(X), а поскольку решается задача линейного программи-
У
^—
\
X
и, иг
Рис. 7.21. Иллюстрация функций F-(X), F+(X) и величин ыь иг при переформулировании задачи линейного программирования.
рования на минимум, то F~(X) и является нашей целевой функцией. Задача принимает следующий вид:
(минимизировать F_ (X) при условиях F_№<F+(X),
Эта новая ситуация изображена на рис. 7.21, где показаны связи между «1, «2. F-(X), F+(X) и границей Р.
Элементарной операцией, используемой в этом методе, является вычисление функций F-(X'), F+(X') и их наклонов по обе стороны от заданного значения Х'е! (Обозначим через №{Х') и №(Х') иаклопыгр_(Хг) слева и справа от X' соответственно; аналогично определяются f<?> и f<*).) Покажем теперь, что эту элементарную операцию, названную вычислением функ-
7.2. Плоские приложения
359
ций, можно выполнить за время O(N). Обращаясь для краткости лишь к F-(X), имеем выражение
F_ (X') = max (6,Х' + Y<),
которое можно вычислить за время, пропорциональное |/_| = = О (N). Если существует только одно значение /, равное i0, на котором достигается F_(X'), то /(f> [X') = /(*> (X') = 6io, иначе (если существуют два таких значения /, и г'2), то №(Х') = = min(6tV 6.J и № (Xr) = max (6jV 6(.), поскольку F_ выпукла вниз.
Справедлино утверждение, что для любого X' e[ui, и2] можно получить один из следующих результатов за время O(N):
1. X' недопустимо, а задача не имеет решений;
2. X' недопустимо, но известно, по какую сторону от X' (слева или справа) могут лежать все допустимые значения X;
3. X' допустимо, и известно, по какую сторону от X' лежит минимум F-(X);
4. X' доставляет минимум функции F-(X).
Действительно, если функция H(X) — F-(X)—F+(X) положительна в точке X', то X' недопустимо. Рассматривая наклоны F-(X) и F+{X) при Х = Х', имеем (рис. 7.22): если №(Х')> >f{+)(X'), то Н (X) возрастает в X', и допустимые значения X могут располагаться только слева от X' (рис. 7.22(a), случай 2); если fM(X') < Р?ЦХ'), то аналогично допустимые X могут быть только справа от X' (рис. 7.22(b), случай 2); наконец, если №(Х'ХР{ЧХ') и №(Х')>Г^{Х'), то Н(Х) достигает минимума на X' — задача неразрешима (рис. 7.22(c), случай 1).
Пусть теперь H(X')^L0, т. е. X' допустимо. Оставляем в качестве упражнения вопрос о выборе между случаями 3 и 4 опять на базе информации о четырех наклонах: №(Х'), fW(X'), ff(X'), ff(X').
Теперь стратегия решения начинает проясняться. Нужно пытаться так выбирать абсциссу X', в которой производится вычисление, чтобы если алгоритм и не завершается сразу же, то по крайней мере фиксированную долю а от числа активных в данный момент ограничений можно было «вывести из игры» или отсечь (причем каждое отсекаемое ограничение, наверняка, не должно содержать крайних вершин). Если эта цель достигнута, то после logi/(i_a)JV шагов мощность множества ограничений становится достаточно малой и приемлемой для прямого решения задачи. При таком предположении на г'-м шаге число активных ограничений не превосходит (1 —a)'wW, и требуемая обработка завершится за время, не большее чем К{\ —
Гл. 7. Пересечения
— a)'~lN, где К— некая константа. Поэтому суммарное время работы Т(N) оценивается сверху следующим образом:
