Изменения

[[Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем#Индикатор Гиперобъема| Определение гиперобъема]]

Утверждается, что точное вычисление значения гиперобъема <tex>S(X)</tex> множества из <tex>n</tex> точек <tex>d</tex>-мерного пространства является [http://en.wikipedia.org/wiki/Sharp-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 является #P-труднойСведем ее к задаче вычисления значения гиперобъема.Так как доказано<ref>Задача Roth D. On the hardness of approximate reasoning, Artif. Intell., 82: 273–302, 1996, http://cogcomp.cs.illinois.edu/papers/hardJ.pdf</ref>, что #MON-CNF состоит в нахождении количества удовлетворяющих подстановок дляявляется #P-трудной, то это докажет теорему.

 Количество ее удовлетворяющих подстановок равно меньше <tex>2^d</tex> минус на количество удовлетворяющих подстановок ее отрицания 

поэтому далее будем работать с <tex>\overline{f}</tex>.Для каждого клоза конъюнкта <tex>\bigwedge_{i \in C_k} \neg x_i</tex> построим гиперкуб соответствующий ему гиперпараллелепипед<tex>A_k = [0,a^k_1]\times...\times[0,a^k_d]</tex>

</tex>. Рассмотрим теперь <tex>A = \bigcup \limits _{k=1}^n A_k</tex>. Заметим, что так как все вершины гиперпараллелепипедов <tex>A_i</tex> лежат в точках с целочисленными координатами 0,1 или 2, то и <tex>A</tex> можно разбить на гиперкубы вида <tex>B_{x_1,...,x_d} = [x_1,x_1 + 1]\times ... \times [x_d, x_d + 1]</tex>, где <tex>x_i \in \{0,1\}, i \in [d]</tex> (то есть на гиперкубы со сторонами 1 с координатами ближайшей к началу координат вершины 0 или 1). Более того, из-за целочисленности вершин <tex>A_i</tex>, каждый из этих гиперкубов лежит в хотя бы одном из <tex>A_i</tex> <tex> B_{x_1,...,x_d} \subset \bigcup \limits _{k = 1}^n A_k \iff B_{x_1,...,x_d} \subset A_k \iff</tex>

<tex>C_1 = \{xiff\}</tex> будет соответствовать клоз <tex>exists a^k_i \neg x_1geq x_i + 1 : i \in d \iff</tex>

а <tex>C_2 \iff \forall i : x_i = 1 \to a^k_i = 2 \iff \{forall i : x_i = 1\to i \notin C_k \iff (x_1,...,2x_d) </tex> удовлетворяет <tex>\bigwedge_{i \in C_k}\neg x_i</tex> клоз для некоторого <tex>k \neg iff (x_1 ,...,x_d)</tex> удовлетворяет <tex>\wedge \neg x_2overline{f}</tex>.

Заметим, что объединение гиперкубов <tex>A_k</tex> может быть записано так как объединение гиперкубов вида <tex>\mu (B_{x_1,...,x_d} ) = [1 \to \mu (\bigcup \limits _{k=1}^n A_k ) = |\{(x_1,x_1 + ...,x_d) \in \{0,1]\times }^d| (x_1,... \times [x_d, x_d + 1])</tex>, где удовлетворяет <tex>x_i \in \overline{0,1f} \}, i \in [d]|</tex>.

Более тогоТаким образом произвели сведение, в значит задача вычисления гиперобъема принадлежит классу #P}}

==Эффективная аппроксимация нахождения значения гиперобъема==Приведем псевдокод алгоритма для аппроксимации гиперобъема объединения тел. В алгоритме, приведенном в <texref> B_{x_1Bringmann K.,Friedrich T...Approximating the volume of unions and intersections of high-dimensional geometric objects,x_d} \subset \bigcup \limits _{k = 1}^n A_k \iff B_{x_1ISAAC'2008,http://www.mpi-inf.mpg.de/~kbringma/paper/2008ISAAC_Volume.pdf</ref>используются три оракула: <tt>PointQuery</tt>,x_d} <tt>VolumeQuery</tt> и <tt>SampleQuery</tt>, каждый из которых ошибается с вероятностью <tex>\subset A_k epsilon_p, \iff \exists a^k_i epsilon_v</tex> и <tex>\geq x_i + 1 : i \in d \iffepsilon_s</tex>соответственно.

Оракул*<tt>PointQuery(x,B)</tt> возвращает true, если точка <tex>x</tex> лежит внутри <tex> B</tex>.*<tt>VolumeQuery(B)</tt> возвращает объем заданного тела <tex>B</tex>.*<tt>SampleQuery(B)</tt> для заданного тела <tex>B</tex> возвращает произвольную его точку <tex>x \iff in B</tex>.  Для данного алгоритма допускаются следующие ослабления этих оракулов:*<tt>PointQuery(x,B)</tt> возвращает true для всех точек из некоторого тела <tex> B' : \mu ((B' \backslash B) \cup (B \backslash B'))\leq \epsilon_p \mu(B)</tex>*<tt>VolumeQuery(B)</tt> возвращает значение <tex>V' : (1-\epsilon_v)\forall i mu(B) \leq V' \leq (1+\epsilon_v)\mu(B)</tex>*<tt>SampleQuery(B)</tt> возвращает произвольную точку из тела <tex>B' : |f(x) - 1/\mu(B')| < \epsilon_s </tex> M := 0; C : = 0; x_i <tex> \overline \epsilon := \frac{\epsilon - \epsilon_v}{1 + \to epsilon_v} </tex> a^k_i <tex> \overline C := 2 \iff frac{(1+\epsilon_s)(1+\epsilon_v)(1+\epsilon_p)}{(1-\epsilon_v)(1-\forall i epsilon_p)}</tex> <tex> T : x_i = \frac{24 ln (2) (1 + \overline \to i epsilon) n}{\overline \epsilon^2 - 8 (\notin C_k overline C - 1) n}</tex> for all <tex>B_i \iff in S</tex> do compute <tex>V'_i</tex> := VolumeQuery(x_1,...,x_d<tex>B_i</tex>) od <tex> V' := \sum\limits_{i = 1}^n V'_i</tex> удовлетворяет while <tex>C \bigwedge_{leq T</tex> do choose <tex>i \in C_k[n] </tex> with probability <tex>\frac{V'_i}{V'}</tex> x := SampleQuery(<tex>B_i</tex>) repeat if (C > T) then return <tex>\frac {TV'} {nM} </tex> choose random <tex>j \neg x_iin [n]</tex> uniformly C := C + 1 until PointQuery (x, <tex>B_j</tex> для некоторого ) M := M + 1 od return <tex>k \iff frac{TV'}{nM}</tex> Время работы алгоритма составляет  <tex>O(n V(d)+M S(d)+ TP(d)) = O(n V(d) + T(S(d)+P(x_1d)) )</tex>,... где <tex>V(d)</tex>,x_d<tex>S(d)</tex> и <tex>P(d)</tex> удовлетворяет это оценка времени работы оракулов <tt>VolumeQuery</tt>, <tt>SampleQuery</tt> и <tt>PointQuery</tt>, соответственно. Выберем <tex>\overlineepsilon : \epsilon_s, \epsilon_p, \epsilon_v \leq \frac{\epsilon^2}{f47n}</tex>.

ЗаметимЕсли все используемые тела являются гиперпараллелепипедами, что так как то время работы каждого из оракулов составляет в точности <tex>\mu O(B_{x_1,...,x_d}d) = 1 \to \mu (\bigcup \limits _{k=1}^n) A_k = |\{(x_1</tex>,...,x_d) таким образом алгоритм позволяет построить <tex>\in epsilon</tex>-аппроксимацию гиперобъема с вероятностью <tex>\{0,1\}^d| (x_1,...,x_d)geq 3/4</tex> удовлетворяет за время <tex>O(\overlinefrac{fnd}{\epsilon^2})</tex>.