Информационный сайт

 

Реклама
bulletinsite.net -> Книги на сайте -> Программисту -> Сигал И.Х. -> "Введение в прикладное дискретное программирование " -> 59

Введение в прикладное дискретное программирование - Сигал И.Х.

Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование — М.: ФИЗМАТЛИТ, 2003. — 240 c.
ISBN 5-9221-0377-6
Скачать (прямая ссылка): vvedenievprikladnoeprogrammirovanie2003.djvu
Предыдущая << 1 .. 53 54 55 56 57 58 < 59 > 60 61 62 63 64 65 .. 84 >> Следующая


со значением абсциссы жтах, то переходим к шагу с номером t + 1; если совпадает с указанной точкой, то в дальнейшем на шаге t +1 для выбираемой очередной точки при построении уравнения прямой учитываем, что Xt+1 < Xi. Алгоритм завершает работу, если в качестве очередной точки і выбирается первая точка г і из множества V.
170

Разд. III. Приближенные методы и алгоритмы

Алгоритм 2. Этот алгоритм основан на следующем простом факте. Если (р, q) — ребро оболочки, то следующее ребро (q, г) выбирается так, что угол между направлениями, определяемыми ребрами (p,q) и (g,r), минимален (т.е. максимален косинус этого угла). Выберем в качестве начальной точку с минимальным значением абсциссы, а в качестве начального направления — ось ординат. Вычислим п — 1 значений косинуса угла между направлением оси ординат и направлением из начальной точки на каждую из оставшихся точек. Выбрав минимальное значение, найдем начальное ребро (p,q). Затем аналогично найдем ребро (q, г), выбрав минимальное из п — 2 значений косинуса угла между направлением (р, q) и (q, г) и т.д. Очевидно, что с трудоемкостью 0(п2) арифметических операций выпуклая оболочка будет построена, T2(rTi) = (п2).

Алгоритм 3. Выберем «внутреннюю точку» в множестве точек, например, по правилу

хг Ці

г = 1 _ г = 1

в качестве полюса*) и для каждой из точек (хі,Уі) найдем полярный угол в направлении против часовой стрелки от положительного направления оси абсцисс. Упорядочим точки по неубыванию полярного угла. Трудоемкость такого упорядочения оценивается как 0(п\пп) арифметических операций. Тогда последовательные вершины выпуклой оболочки располагаются в порядке, соответствующем возрастанию значений полярного угла относительно любой внутренней точки. Просмотр начинается с точки с минимальным значением ординаты. В дальнейшем последовательно просматриваются пары соседних точек (по значению полярного угла). Точка является внутренней точкой оболочки, если она есть внутренняя точка треугольника Opq, где р и q — последовательные вершины выпуклой оболочки, 0 — начало координат. Внутренние точки удаляются. С трудоемкостью O(nlnn) операций выпуклая оболочка будет построена, (п) = 0(п\пп).

Алгоритм 4. Этот алгоритм основан на том, что выпуклая оболочка объединения двух выпуклых многоугольников может быть найдена за время, пропорциональное суммарному числу их вершин. Упорядочим точки (хі, у і) по неубыванию значений ординат Х{ и разобъем исходное множество точек на последовательные пары (при нечетном числе точек последнее множество состоит из трех точек). Полученное множество точек образуют множества точек первого уровня, выпуклые оболочки этих множеств есть отрезки (треугольник для последне-

*) Такая точка называется центром тяжести точек множества Р.
Гл. 1. Локальная оптимизация

171

го из множеств при нечетном числе точек). Объединив оболочки для последовательных пар множеств, получим на втором уровне оболочки для множеств из четырех точек, далее на третьем уровне — для множеств из восьми точек и т.д. На каждом уровне число операций оценивается как О(п), число уровней оценивается как О (In п), поэтому за O(nlnn) операций оболочка будет построена, T4 (n) = O(nlnn).

Алгоритм объединения оболочек подмножеств описан в [31], где также описаны и другие алгоритмы этого раздела. В этой же книге описаны алгоритмы построения выпуклой оболочки в пространстве произвольной размерности.

АЛГОРИТМ 5. Описанные выше алгоритмы имеют относительно высокую трудоемкость (кроме алгоритмов 3 и 4), так как при выборе очередного ребра оболочки рассматриваются все точки множества. Нами предлагается декомпозиционный подход, основанный на идее разбиения исходного множества точек на непересекающиеся подмножества. После построения оболочки для любого из подмножеств можно удалить все внутренние точки многоугольников, объединив точки оболочек подмножеств в новое множество и повторив процедуру.

Обозначим через Т(т) трудоемкость алгоритма построения выпуклой оболочки для множества из т точек. Упорядочим исходное множество точек по неубыванию значений абсцисс. Найдем хт-1П = = minXi и жтах = тахжі, разобъем отрезок [жтіп,жтах] на к частей и проведем через точки деления прямые, параллельные оси ординат. При этом множество P разбивается на к непересекающихся подмножеств PSj S = 1, 2,..., к: к

р = U Ps, Pi n Pj = іф j,

S= I

Ps = I-PsI, S = 1,2,...,*,

к

J2pg = n-

S= і

Построим по одному из описанных ранее алгоритмов выпуклые оболочки для всех подмножеств Ps. Для оценки трудоемкости алгоритма построения оболочек всех подмножеств и определения их мощностей рассмотрим следующую задачу:

к

у] T (Ps) ->¦ max, (7.2.1)

к

= n, ps > 0 целые, s = 1, 2,..., к. (7.2.2)

5=1
172

Разд. III. Приближенные методы и алгоритмы

Отбросив условие целочисленности для значений Ps, составим функцию Лагранжа:

к /к \

L(pi,P2,---,Pk,X) = Et + A (X^-nI •

5=1 \5=1 /

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

дЬ_дТ _ і о и

о H-A 0, s 1 ? 2,..., /и,
Предыдущая << 1 .. 53 54 55 56 57 58 < 59 > 60 61 62 63 64 65 .. 84 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100