25
правок
Изменения
Нет описания правки
Точка <tex>x</tex> доминирует точку <tex>y</tex> (<tex>x \succ y</tex>), если <tex>\forall i : x_i \ge y_i, \exists j : x_j > y_j</tex>.
<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 \succ x\}) </tex> - гиперобъем множества <tex>X</tex>.
В частности, если <tex>X = \{x\}</tex>, то <tex>S(X) = \prod \limits_{i=1}^{d} x_i</tex>.
Задача: найти точное значение гиперобъема <tex>S(X)</tex> множества из <tex>n</tex> точек <tex>d</tex>-мерного пространоства. == Алгоритм включения-исключения (Inclusion-Exclusion Algorithm, IEA) == Самый простой алгоритм нахождения гиперобъема базируется на идее комбинаторной [[формула включения-исключения|формулы включения-искючения]].Все множество <tex>X</tex> представляется в виде объединения <tex>n</tex> гиперкубов (<tex>X^i</tex>), соответствующих отдельным точкам <tex>x^i</tex>. После этого объем всего множества вычисляется по формуле: <center> <tex> S(X) = \sum \limits_{I \in 2^n} (-1)^{|I|+1} S(\bigcap \limits_{ j \in I} X^j) </tex> </center> Объем пересечения гиперкубов легко считается как произведение по каждой координате минимального значения этой координаты среди всех точек, которым соответствуют гиперкубы. Таким образом, в этом алгоритме перебираются все подмножества точек множества <tex>X</tex>, для каждого множества находится гиперобъем пересечения соответствующих гиперкубов и он прибавляется с соответствующим знаком к ответу.Время работы этого алгоритма составляет <tex>O(n 2^n)</tex>.
