25
правок
Изменения
м
орфографические ошибки
<tex>X = (x^1, x^2, ..., x^n) \subset R^d</tex> - множество из <tex>n</tex> точек в <tex>d</tex>-мерном пространстве таких, что <tex>\nexists i \neq j : x_i \succ x_j</tex> - никакая точка не доминируется другой точкой из этого множества.
<tex>S(X) = \mu (\bigcup \limits_{x \in X} \{y | y x \succ xy\}) </tex> - гиперобъем множества <tex>X</tex>.
В частности, если <tex>X = \{x\}</tex>, то <tex>S(X) = \prod \limits_{i=1}^{d} x_i</tex>.
Объем пересечения гиперкубов легко считается как произведение по каждой координате минимального значения этой координаты среди всех точек, которым соответствуют гиперкубы.
Таким образом, в этом алгоритме перебираются все подмножества точек множества <tex>X</tex>, для каждого множества находится гиперобъем пересечения соответствующих гиперкубов , и он прибавляется с соответствующим знаком к ответу.
Время работы этого алгоритма составляет <tex>O(n 2^n)</tex>.
Алгоритм LebMeasure обрабатывает точки множества <tex>X</tex> по очереди. Для каждой очередной точки <tex>x</tex> находится объем некоторого максимального по включению гиперкуба, доминируемого эксклюзивно только этой точкой <tex>x</tex> и она заменяется на некоторое множество ''порожденных'' точек, которые доминируют оставшуюся область, доминировшуюся до этого точкой <tex>x</tex>.
Например, если изначально было четыре точки в трехмерном пространстве <tex>(6, 7, 4), (9, 5, 5), (1, 9, 3), (4, 1, 9)</tex>, то точка <tex>(6, 7, 4)</tex> эксклюзивно доминирует куб с одним концов в <tex>(6, 7, 4)</tex>, а другим - в <tex>(4, 5, 3)</tex>. После добавления объема этого куба в к ответу, точка <tex>(6, 7, 4)</tex> порождает три точки: <tex>(4, 7, 4), (6, 5, 3), (6, 7, 3)</tex>. При этом точка <tex>(6, 5, 4)</tex> доминируется точкой <tex>(9, 5, 5)</tex> и сразу удаляется из множества <tex>X</tex>.
Обработка точек продолжается, пока все точки не будут обработаны. Таким образом, время работы алгоритмы алгоритма напрямую зависит от количества порожденных точек. Легко заметить, что таких точек не более, чем <tex>n^d</tex>, поскольку каждая координата каждой порожденной точки равна соответствующей координате некоторой точки исходного множества <tex>X</tex>.
К сожалению, эта верхняя оценка является достижимой. Например, если исходное множество <tex>X</tex> имеет вид: <tex>(1, n, n, ..., n), (2, n - 1, n - 1, ..., n - 1), ..., (n, 1, 1, ..., 1)</tex>, и точки обрабатываются именно в этом порядке, то всего будет обработано <tex>n^{d-1}</tex> точка, что показано в [1]. Правда, если в этом примере точки обрабатываются в обратном порядке, то суммарное количество обработанных точек линейно зависит от <tex>n</tex> и <tex>d</tex>. Тем не менее, существуют примеры, для которых любой порядок обработки приводит к экспоненциальной зависимости числа порожденных точек от размерности пространства <tex>d</tex> и близок эта зависимость близка к <tex>n^d</tex> [1].
== Алгоритм Hypervolume by Slicing Objectives (HSO) ==
Если алгоритм LebMeasure по очереди рассматривает все точки, то алгоритм HSO рассматривает по очереди все координаты, сводя задачу к меньшей на единицу размерности.
Изначально все точки сортируются по первой координате. Значения этой координаты используются для ''расслоения''(разрезания) всего множества на <tex>n</tex> частей, внутри каждой из которых при движении вдоль первой координаты форма ''разреза'' (гиперплоскости), проходящего перпендикулярно оси первой координаты , не меняется. Таким образом, для подсчета объема каждой части необходимо найти объем разреза , и умножить на длину части вдоль первой координаты. При этом получившийся разрез имеет на единицу меньшую размерность.Заметим, что после сортировки и расслоения первая часть содержит все исходные <tex>n</tex> точекмножества <tex>X</tex>, вторая - все, помимо точки с минимальной первой координатой, вдоль которой происходит расслоение , и т.д., а последняя часть содержит только одну точку с максимальной этой координатой.
После этого все полученные части расслаиваются уже по второй координате, далее все полученные - по третьей и т.д. В итоге исходное множество разбивается на несколько непересекающихся гиперкубов и остается их найти суммарный гиперобъем. Заметим, что расслаивание части можно прекратить в тот момент, когда в нее входит только одна точка и посчитать объем гиперкуба, образованного проекцией этой точки на оставшиеся координаты.
Описанный процесс можно реализовать как в виде рекурсивной процедуры, расслаивающей множество вдоль очередной координаты и вызывающей себя рекурсивно для каждой части и следующей координаты, так и нерекурсивно, если поддерживать множество всех текущих частей и на очередной итерации разбивать их все вдоль очередной координаты.
|statement=<center><tex>{x \choose y} = {x - r \choose y} + \sum \limits_{i = 1}^{r} {x - i \choose y - 1}</tex>.</center>
|proof=Индукция по <tex>r</tex>. База: <center><tex>{x \choose y} = {x - 1 \choose y} + {x - 1 \choose y - 1}</tex>.</center>
Переход: предполагаем, что утверждение верно для <tex>r = j</tex>. Раскрываем первое слагаемое в правой части предположения, аналогично базе и получаем:
<center><tex>{x \choose y} = {x - j - 1 \choose y} + {x - (j + 1) \choose y - 1} + \sum \limits_{i = 1}^{j}{x - i \choose y - 1} = {x - (j + 1) \choose y} + \sum \limits_{i = 1}^{j}{x - i \choose y - 1}</tex>.</center>
}}
продолжаем доказательство теоремы по индукции:
<center><tex>f(n, d) = {n + d - 2 \choose d - 1} = \sum \limits_{i = 1}^{n} {n + d - 2 + i \choose d - 2} = \sum \limits_{k = n}^{1} {n + d + 2 - (n - k + 1) \choose d - 2} = \sum \limits_{k = 1}^{n} {k + d - 3 \choose d - 2} = \sum \limits_{k = 1}^{n}{k + (d - 1) - 2 \choose (d - 1) - 1} = \sum \limits_{k = 1}^{n}{f(k, d - 1)}</tex></center>
}}
{{Определение
|definition=КД-деревом называется [[Дерево поиска, наивная реализация|сбалансированное двоичное дерево]], где каждой вершине <tex>\alpha</tex> соответствует некоторая область <tex>C_{\alpha}</tex> <tex>d</tex>-мерного пространствепространства, удовлетворяющая следующим свойствам:
# Корневой вершине <tex>root</tex> соответствует <tex>C_{root}</tex> - все пространство.
# Каждое <tex>C_{\alpha}</tex> является гиперпараллелепипедом (возможно бесконечным в некоторых направлениях).
Также для каждой вершины будем хранить значение площади пересечения области этой вершины со всеми прямоугольниками <tex>M</tex>, которое определяется следующим образом:
# Для каждого листа <tex>M</tex> равно площади пересечения всех прямоугольников с областью этого листа.
# Для каждой внутренней вершины <tex>\alpha</tex> если <tex>Cover_{\alpha} > 0</tex>, тогда <tex>M</tex> равно площади всех всей области <tex>C_{\alpha}</tex>, иначе <tex>M</tex> равно сумме этих значений для двух сыновей этой вершины.
Таким образом, значение для корневой вершины <tex>M_{root}</tex> и является искомой площадью объединения всех прямоугольников.
Рассмотрим теперь как именно будет устроено разделение пространства на области КД-деревом для эффективного его использования.
Возьмем проекции всех параллелепипедов на плоскость, перепендикулярную оси <tex>OZ</tex> - множество прямоугольников <tex>V</tex>. Рассмотрим все <tex>x</tex>-координаты границ прямоугольников и разобьем ось <tex>OX</tex> на <tex>2\sqrt{n}</tex> промежутков так, чтобы в каждом из них было не более <tex>\sqrt{n}</tex> границ. Получившиемя Получившиеся <tex>2\sqrt{n}</tex> полос разобьем горизонтальными линиями на итоговые области по отдельности следующим образом. Для каждой полосы у всех прямоугольников, имеющих вертикальную границу в этой полосе , возьмем все горизонтальные границы (их будет не более <tex>2\sqrt{n}</tex>), а среди всех горизонтальных границ, пересекающих область, возьмем каждую <tex>\sqrt{n}</tex>-ую. Таким образом, в итоге получим не более <tex>4\sqrt{n}</tex> областей в каждой верикальной полосе.
Полученные области обладают следующими свойствами:
Все эти утверждения несложно следуют из алгоритма разбиения на области.
Каждая из этих областей будет одним из листов КД-дерева. Для построения всего дерева сначала объединим все области для одной вертикальной полосы, сливая соседние области в одну вершинудерева. После этого аналогично будем сливать соседние вертикальные области и в итоге получим корневую вершину, представляющую всю плоскость.
Построенное КД-дерево обладает следующими свойствами:
Все эти свойства следуют из свойств разбиения на области и логарифмической высоты дерева.
Наконец, получаем итоговый алгоритм. Идем сканирующей плоскостью, перепендикулярной оси <tex>OZ</tex>, добавляя или удаляя прямоугольники из КД-дерева. При этом каждый раз пересчитывается пересчитываем площадь объединения всех текущих прямоугольников и, складывая эти величины, умноженные на соответствующую разницу <tex>z</tex>-координат , получаем общий объем.
Каждая операция добавления или удаления прямоугольников требует изменения <tex>O(\sqrt{n} \log n)</tex> полей <tex>Cover</tex>, а также операций добавления или удаления прямоугольника в <tex>O(\sqrt{n})</tex> листьев, каждая из которых требует <tex>O(\log n)</tex> времени. Итого, на одну операцию добавления или удаления требуется <tex>O(\sqrt{n} \log n)</tex> времени, суммарно таких операций <tex>O(n)</tex>, и получается, что весь алгоритм работает за <tex>O(n \sqrt{n} \log n)</tex>. При этом на хранение всей информации требуется <tex>O(n\sqrt{n}) </tex> памяти - каждый лист может хранить <tex>O(\sqrt{n})</tex> прямоугольников.
