42
правки
Изменения
Нет описания правки
[[Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем#Индикатор Гиперобъема| Определение гиперобъема]]
Утверждается, что точное вычисление значения гиперобъема <tex>S(X)</tex> множества из <tex>n</tex> точек <tex>d</tex>-мерного пространства является [http://en.wikipedia.org/wiki/Sharp-P #P-трудной задачей], однако допускает эффективную аппроксимацию, а именно может быть аппроксимировано за
*полином от количества параметров,
*полином от количества решений,
== #P-трудность задачи вычисления гиперобъема ==
{{Определение
|definition=задача Задача #MON-CNF (Satisfability problem for monotone boolean formulas) --- задача вычисления количества удовлетворяющих подстановок для монотонной булевой формулы, записанной в [[КНФ]] <tex>f = \bigwedge \limits _{k=1}^n \bigvee_{i \in C_k} x_i</tex>
где все дизъюнкты <tex> C_k \subseteq {1,...,d}</tex>
}}
{{Теорема
|statement= Задача вычисления гиперобъема принадлежит классу #P -трудных задач
|proof= Суть доказательства состоит в сведении задачи #MON-CNF к задаче вычисления значения гиперобъема. Так как доказано
<ref>
Заметим, что так как <tex>\mu (B_{x_1,...,x_d}) = 1 \to \mu (\bigcup \limits _{k=1}^n) A_k = |\{(x_1,...,x_d) \in \{0,1\}^d| (x_1,...,x_d)</tex> удовлетворяет <tex>\overline{f} \}|</tex>
Таким образом произвели сведение, в значит задача вычисления гиперобъема принадлежит классу #P
}}
==Эффективная аппроксимация нахождения значения гиперобъема==
Приведем псевдокод алгоритма для аппроксимации гиперобъема. В алгоритме, приведенном в
<ref>
