Изменения

Перейти к: навигация, поиск

Оценка сложности вычисления гиперобъема

673 байта убрано, 14:15, 19 июня 2012
Нет описания правки
== Постановка задачи ==<tex>x = (x_1[[Эволюционные алгоритмы многокритериальной оптимизации, x_2, ..., x_d; x_i \ge 0) \in R^d</tex> - точка в <tex>d</tex>-мерном пространстве. Точка <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>-мерного пространства является [http://en.wikipedia.org/wiki/Sharp-P #P-трудной задачей], однако допускает эффективную аппроксимацию, а именно может быть аппроксимировано за
Анонимный участник

Навигация