Изменения

<tex>x = (x_1, x_2, ..., x_d; x_i \ge 0) \in \mathbb{R}^d</tex> - точка в <tex>d</tex>-мерном пространстве.

<tex>X = (\{x^1, x^2, ..., x^n) \} \subset \mathbb{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>\mu</tex> - мера Лебега.

Задача: найти точное значение гиперобъема <tex>S(X)</tex> множества из <tex>n</tex> точек <tex>d</tex>-мерного пространоствапространства.

Все множество <tex>X</tex> представляется в виде объединения <tex>n</tex> гиперкубов гиперпараллелепипедов (<tex>X^i</tex>), соответствующих отдельным точкам <tex>x^i</tex>.

Объем пересечения гиперкубов гиперпараллелепипедов легко считается как произведение по каждой координате минимального значения этой координаты среди всех точек, которым соответствуют гиперкубыгиперпараллелепипеды.

Таким образом, в этом алгоритме перебираются все подмножества точек множества <tex>X</tex>, для каждого множества находится гиперобъем пересечения соответствующих гиперкубов гиперпараллелепипедов, и он прибавляется с соответствующим знаком к ответу.

Алгоритм LebMeasure <ref>Bringmann K., Friedrich. T.: An Efficient Algorithm for Computing Hypervolume Contributions. Evolutionary Computation, Vol. 18, No. 3, MIT Press, pp 383-402. (2010)</ref> обрабатывает точки множества <tex>X</tex> по очереди. Для каждой очередной точки <tex>x</tex> находится объем некоторого максимального по включению гиперкубагиперпараллелепипеда, доминируемого эксклюзивно только этой точкой <tex>x</tex> и она заменяется на некоторое множество ''порожденных'' точек, которые доминируют оставшуюся область, доминировшуюся доминировавшуюся до этого точкой <tex>x</tex>.

Например, если изначально было четыре точки в трехмерном пространстве <center><tex>(6, 7, 4), (9, 5, 5), (1, 9, 3), (4, 1, 9)</tex>, </center> то точка <tex>(6, 7, 4)</tex> эксклюзивно доминирует куб параллелепипед с одним концов в <tex>(6, 7, 4)</tex>, а другим - в <tex>(4, 5, 3)</tex>. После добавления объема этого куба в параллелепипеда к ответу, точка <tex>(6, 7, 4)</tex> порождает три точки: <center><tex>(4, 7, 4), (6, 5, 3), (6, 7, 3)</tex>.</center>При этом, точка <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]<ref name = "while"/>. Правда, если в этом примере точки обрабатываются в обратном порядке, то суммарное количество обработанных точек линейно зависит от <tex>n</tex> и <tex>d</tex>. Тем не менее, существуют примеры, для которых любой порядок обработки приводит к экспоненциальной зависимости числа порожденных точек от размерности пространства <tex>d</tex> и близок эта зависимость близка к <tex>n^d</tex> [<ref name="while">While, L., Hingston, P., Barone, L., Huband, S.: A Faster Algorithm for Calculating Hypervolume. IEEE Transaction on Evolutionary Computation, Vol.10, No. 1], pp 29–38. (2006)</ref>.

Под ''Objectives'' в названии данного алгоритма имеются в виду координаты пространства <tex>\mathbb{R}^d</tex>.

Если алгоритм LebMeasure по очереди рассматривает все точки, то алгоритм HSO <ref>Zhou X., Sun C., Mao N., Li W.: Generalization of HSO algortihms for computing hypervolume for mutiobjective optimization problems, IEEE Congress on Evolutionary Computation. (2007)</ref> рассматривает по очереди все координаты, сводя задачу к меньшей на единицу размерности.

Изначально все точки сортируются по первой координате. Значения этой координаты используются для ''расслоения''(разрезания) всего множества на <tex>n</tex> частей, внутри каждой из которых при движении вдоль первой координаты форма ''разреза'' (гиперплоскости), проходящего перпендикулярно оси первой координаты , не меняется. Таким образом, для подсчета объема каждой части необходимо найти объем разреза , и умножить на длину части вдоль первой координаты. При этом получившийся разрез имеет на единицу меньшую размерность.Заметим, что после сортировки и расслоения первая часть содержит все исходные <tex>n</tex> точекмножества <tex>X</tex>, вторая - все, помимо точки с минимальной первой координатой, вдоль которой происходит расслоение , и т.д., а последняя часть содержит только одну точку с максимальной этой координатой.

После этого все полученные части расслаиваются уже по второй координате, далее все полученные - по третьей и т.д. В итоге исходное множество разбивается на несколько непересекающихся гиперкубов гиперпараллелепипедов и остается их найти суммарный гиперобъем. Заметим, что расслаивание части можно прекратить в тот момент, когда в нее входит только одна точка и посчитать объем гиперкубагиперпараллелепипеда, образованного проекцией этой точки на оставшиеся координаты.

База: <center><tex>f(n, 1) = 1</tex>.</center>

1) Покажем, чтоДокажем полезные леммы: <center><tex>{x \choose y} = {x - r \choose y} + \sum \limits_{i = 1}{r} {x - i \choose y - 1}</tex>.</center>Индукция по <tex>r</tex>. База: <center><tex>{x \choose y} = {x - 1 \choose y} + {x - 1 \choose y - 1}</tex>.</center>

2{{Лемма|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>}} {{Лемма|statement=<center><tex>{x \choose y} = \sum \limits_{i = 1}^{x - y + 1} {x - i \choose y - 1}</tex>.</center>|proof=Подставляем в предыдущую лемму <tex>r = x - y</tex> и получаем:<center><tex>{x \choose y} = {y \choose y} + \sum \limits_{i = 1}^{x - y} {x - i \choose y - 1} = {x - (x - y + 1) \choose y - 1} + \sum \limits_{i = 1}^{x - y} {x - i \choose y - 1} = \sum \limits_{i = 1}^{x - y + 1} {x - i \choose y - 1}</tex>.</center>}}

Таким образом, на этот алгоритм получена более низкая оценка времени работы, чем на предыдущий, и это подтверждается на практике [1]<ref name ="while"/>.

Задача KMP состоит в нахождении объема объединения прямоугольных гиперпараллелепипедов в <tex>d</tex>-мерном пространстве. Как показано в описании алгоритма IEA, исходная задача легко сводится к этой, если каждой точке поставить в соответствие гиперкуб гиперпараллелепипед с одной вершиной в центре координат, а противоположной - в этой точке.

Существует несколько алгоритмов решения задачи KMP<ref name = "overmars">Overmars M.H., Yap C.K.: New upper bounds in Klee’s measure problem. SIAM Journal on Computing 20(6), pp 1034–1045. (1991)</ref><ref>Beume N.: S-Metric calculation by considering dominated hypervolume as Klee’s measure problem. Evolutionary Computation, 17(4), pp 477–492. (2009)</ref><ref>Beume N., Rudolph G.: Faster S-metric calculation by considering dominated hypervolume as Klee’s measure problem. In Proc. Second International Conference on Computational Intelligence (IASTED ’06), pp 233–238. (2006)</ref>, самый оптимальный из которых использует идеи сканирующей гиперплоскости, [[Статистики на отрезках. Корневая эвристика|корневой эвристики]] и КД-дерево, и позволяет решать задачу за время <tex>O(n^{d/2}\log n)</tex>. Рассмотрим его.

Возьмем гиперплоскость, перпендикулярную оси <tex>d</tex>-ой координаты, будем ее двигать по этим значениям от минимального до максимального и рассматривать проекцию всех гиперкубов гиперпараллелепипедов на эту гиперплоскость. Заметим, что между точками проекция меняться не будет, а в каждой точке будут появляться или исчезать проекции некоторых гиперкубовгиперпараллелепипедов. Поэтому, если уметь эффективно пересчитывать объем проекции при каждом появлении/исчезновении и прибавлять это значение, умноженное на расстояние между последовательными значениями <tex>d</tex>-ой координаты, то можно легко посчитать суммарный гиперобъем. Как раз для эффективного пересчета используется такая структура, как КД-дерево.

В трехмерном пространстве сканирующая гиперплоскость превращается в обычную плоскость. Будем считать, что сканирующая плоскость двигается перепендикулярно она всегда располагается перпендикулярно оси <tex>OZ</tex>и двигается от минимальных значений по этой оси до максимальных. В каждый момент проекция всех параллелепипедов на эту плоскость предствляет представляет собой множество прямоугольников и необходимо уметь обрабатывать следующие три запроса:

|definition=КД-деревом называется [[Дерево поиска, наивная реализация|сбалансированное двоичное дерево]], где каждой вершине <tex>\alpha</tex> соответствует некоторая область <tex>C_{\alpha}</tex> <tex>d</tex>-мерного пространствепространства, удовлетворяющая следующим свойствам:

# Для каждой внутренней вершины <tex>\alpha</tex> если <tex>Cover_{\alpha} > 0</tex>, тогда <tex>M</tex> равно площади всех всей области <tex>C_{\alpha}</tex>, иначе <tex>M</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>-координат , получаем общий объем.