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

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

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

[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] точек, вторая - все, помимо точки с минимальной координатой, вдоль которой происходит расслоение и т.д., а последняя часть содержит только одну точку с максимальной этой координатой.

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

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

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