Пересечение - полуплоскость
Cтраница 1
Пересечение полученных полуплоскостей и определяет многоугольник решений данной задачи. [1]
Пересечение найденных полуплоскостей и дает область решений заданной системы. [2]
Любая выпуклая область является пересечением полуплоскостей. [3]
 |
Пример того, как СОРТИРОВКУ можно преобразовать в ПЕРЕСЕЧЕНИЕ ПОЛУПЛОСКОСТЕЙ. [4] |
Постановка задачи (7.2) о пересечении N полуплоскостей ( обманчиво) напоминает стандартную постановку задачи линейного программирования [ Gass ( 1969) ] для двух переменных. [5]
Существует простой квадратичный алгоритм для построения пересечения N полуплоскостей. Предположим, что уже известно пересечение первых i полуплоскостей. Это некая выпуклая многоугольная область, ограниченная не более чем i сторонами, хотя и необязательно конечная. Пересечение этой области с очередной полуплоскостью есть не что иное, как ее разрезание прямой линией и сохранение правого или левого куска. Суммарная работа потребует 0 ( N2) времени, однако преимущество данного алгоритма в том, что он открытый. [6]
Во-первых, заметим, что ядром является пересечение N полуплоскостей. [7]
Убедиться, что условие задачи эквивалентно следующему: многоугольник совпадает с пересечением полуплоскостей, границами которых являются прямые, содержащие стороны многоугольника. [8]
Оптимальность следует из того факта, что нижняя оценка gyV), полученная для пересечения N полуплоскостей, тривиально применима к рассматриваемой задаче. [9]
Границы этих полуплоскостей есть параллельные прямые ( их угловые коэффициенты равны), в данном случае пересечение указанных полуплоскостей пусто - система несовместна. [10]
Очевидно, что ядро может быть найдено за время 0 ( п logra) простым применением алгоритма для вычисления пересечения полуплоскостей. [11]
Очевидно, что ядро может быть найдено за время О ( п log п) простым применением алгоритма для вычисления пересечения полуплоскостей. [12]
На этом примере можно увидеть все главные особенности задач линейного программирования: в нем допустимое множество точек представляет собой выпуклый многоугольник, получившийся в результате пересечения полуплоскостей, и наибольшее значение целевой функция достигается в его вершине - крайней точке. [13]
Задан простой многоугольник с п вершинами. Ядро многоугольника - это пересечение полуплоскостей, каждая из которых расположена слева от прямой линии, содержащей ребро многоугольника и ориентированной в соответствии с прохождением ребра в стандартном представлении многоугольника. [14]
С 1; похожие результаты справедливы и для других, достаточно естественных случайных моделей. Отсюда следует, что для задачи пересечения N полуплоскостей получается линейная оценка среднего поведения алгоритма. А это немедленно ведет к оценке 0 ( N) для среднего поведения алгоритма решения задачи линейного программирования с двумя переменными. Мы видим, что математическое ожидание числа избыточных полуплоскостей - таких, которые не определяют ребер допустимой области, - очень велико, что может, в частности, объяснить прекрасное поведение симплекс-метода. [15]
Страницы: 1 2