Алгоритмы точного вычисления гиперобъема

Эта статья находится в разработке!

Постановка задачи

[math]x = (x_1, x_2, ..., x_d; x_i \ge 0) \in R^d[/math] - точка в [math]d[/math]-мерном пространстве.

Точка [math]x[/math] доминирует точку [math]y[/math] ([math]x \succ y[/math]), если [math]\forall i : x_i \ge y_i, \exists j : x_j \gt y_j[/math].

[math]X = (x^1, x^2, ..., x^n) \subset R^d[/math] - множество из [math]n[/math] точек в [math]d[/math]-мерном пространстве таких, что [math]\nexists i \neq j : x_i \succ x_j[/math] - никакая точка не доминируется другой точкой из этого множества.

[math]S(X) = \mu (\bigcup \limits_{x \in X} \{y | y \succ x\}) [/math] - гиперобъем множества [math]X[/math].

В частности, если [math]X = \{x\}[/math], то [math]S(X) = \prod \limits_{i=1}^{d} x_i[/math].

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

Алгоритм включения-исключения (Inclusion-Exclusion Algorithm, IEA)

Самый простой алгоритм нахождения гиперобъема базируется на идее комбинаторной формулы включения-искючения. Все множество [math]X[/math] представляется в виде объединения [math]n[/math] гиперкубов ([math]X^i[/math]), соответствующих отдельным точкам [math]x^i[/math].

После этого объем всего множества вычисляется по формуле: [math] S(X) = \sum \limits_{I \in 2^n} (-1)^{|I|+1} S(\bigcap \limits_{ j \in I} X^j) [/math]

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

Таким образом, в этом алгоритме перебираются все подмножества точек множества [math]X[/math], для каждого множества находится гиперобъем пересечения соответствующих гиперкубов и он прибавляется с соответствующим знаком к ответу. Время работы этого алгоритма составляет [math]O(n 2^n)[/math].

Алгоритм LebMeasure

Алгоритм LebMeasure обрабатывает точки множества [math]X[/math] по очереди. Для каждой очередной точки [math]x[/math] находится объем некоторого максимального по включению гиперкуба, доминируемого эксклюзивно только этой точкой [math]x[/math] и она заменяется на некоторое множество порожденных точек, которые доминируют оставшуюся область, доминировшуюся до этого точкой [math]x[/math].

Например, если изначально было четыре точки в трехмерном пространстве [math](6, 7, 4), (9, 5, 5), (1, 9, 3), (4, 1, 9)[/math], то точка [math](6, 7, 4)[/math] эксклюзивно доминирует куб с одним концов в [math](6, 7, 4)[/math], а другим - в [math](4, 5, 3)[/math]. После добавления объема этого куба в ответу, точка [math](6, 7, 4)[/math] порождает три точки: [math](4, 7, 4), (6, 5, 3), (6, 7, 3)[/math].При этом, точка [math](6, 5, 4)[/math] доминируется точкой [math](9, 5, 5)[/math] и сразу удаляется из множества [math]X[/math].

Обработка точек продолжается, пока все точки не будут обработаны. Таким образом, время работы алгоритмы напрямую зависит от количества порожденных точек. Легко заметить, что таких точек не более, чем [math]n^d[/math], поскольку каждая координата каждой порожденной точки равна соответствующей координате некоторой точки исходного множества [math]X[/math].

К сожалению, эта верхняя оценка является достижимой. Например, если исходное множество [math]X[/math] имеет вид: [math](1, n, n, ..., n), (2, n - 1, n - 1, ..., n - 1), ..., (n, 1, 1, ..., 1)[/math], и точки обрабатываются в этом порядке, то всего будет обработано [math]n^{d-1}[/math] точка, что показано в [1]. Правда, если в этом примере точки обрабатываются в обратном порядке, то суммарное количество обработанных точек линейно зависит от [math]n[/math] и [math]d[/math]. Тем не менее, существуют примеры, для которых любой порядок обработки приводит к экспоненциальной зависимости числа порожденных точек от размерности пространства [math]d[/math] и близок к [math]n^d[/math] [1].

Алгоритм Hypervolume by Slicing Objectives (HSO)

Под Objectives в названии данного алгоритма имеются в виду координаты пространства [math]R^d[/math].

Если алгоритм LebMeasure по очереди рассматривает все точки, то алгоритм HSO рассматривает по очереди все координаты, сводя задачу к меньшей на единицу размерности.

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

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

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

Время работы алгоритма напрямую зависит от суммарного количества частей, на которые будет разбито исходное множество. По аналогичным предыдущему алгоритму рассуждениям легко показывается, что частей не более [math]n^d[/math]. Тем не менее, существует более точная оценка.

Теорема:

Суммарное количество частей, полученных алгоритмом HSO, не превышает [math]f(n, d) = {n + d - 2 \choose d - 1}[/math].

Доказательство:

[math]\triangleright[/math]

База: [math]f(n, 1) = 1[/math]. Также, из алгоритма расслоения следует, что из части с [math]n[/math] точками будет получено по одной части для каждого [math]i = 1...n[/math], то есть: [math]f(n, d) = \sum \limits_{i = 1}^{n}f(i, d - 1)[/math].

[math]\triangleleft[/math]