1632
правки
Изменения
м
Karl BringmannK., Tobias Friedrich, T. Approximating the volume of unions and intersections of high-dimensional geometric objects, ISAAC'2008, http://www.mpi-inf.mpg.de/~kbringma/paper/2008ISAAC_Volume.pdf
SampleQuery(B) для заданного тела <tex>B</tex> возвращает произвольную его точку <tex>x \in B</tex>.
PointQuery(x,B) возвращает true, если точка <tex>x</tex> лежит внутри <tex> B</tex>.
rollbackEdits.php mass rollback
== #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>
}}
|proof= Суть доказательства состоит в сведении задачи #MON-CNF к задаче вычисления значения гиперобъема. Так как доказано
<ref>
Roth D. Roth. 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>\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>\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,...,x_d) </tex> удовлетворяет <tex>\bigwedge_{i \in C_k} \neg x_i</tex> для некоторого <tex>k \iff (x_1,...,x_d)</tex> удовлетворяет <tex>\overline{f}</tex>
Заметим, что так как <tex>\mu (B_{x_1,...,x_d}) = 1 \to \mu (\bigcup \limits _{k=1}^nA_k ) A_k = |\{(x_1,...,x_d) \in \{0,1\}^d| (x_1,...,x_d)</tex> удовлетворяет <tex>\overline{f} \}|</tex>
Таким образом произвели сведение, в значит задача вычисления гиперобъема принадлежит классу #P
==Эффективная аппроксимация нахождения значения гиперобъема==
Приведем псевдокод алгоритма для аппроксимации гиперобъемаобъединения тел. В алгоритме, приведенном в
<ref>
</ref>
используются три оракула: <tt>PointQuery</tt>, <tt>VolumeQuery </tt> и <tt>SampleQuery</tt>, каждый из которых ошибается с вероятностью <tex>\epsilon_p, \epsilon_v</tex> и <tex>\epsilon_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 \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)\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;
<tex> \overline \epsilon := \frac{\epsilon - \epsilon_v}{1+ \epsilon_v} </tex>
<tex> \overline C := \frac{(1+\epsilon_s)(1+\epsilon_v)(1+\epsilon_p)}{(1-\epsilon_v)(1-\epsilon_p)}</tex>
<tex> T := \frac{24 ln (2) (1 + \overline \epsilon) n}{\overline \epsilon^2 - 8 (\overline C - 1) n}</tex>
for all <tex>B_i \in S</tex>do
compute <tex>V'_i</tex> := VolumeQuery(<tex>B_i</tex>)
od
return <tex>\frac{TV'}{nM}</tex>
Время работы алгоритма составляет <tex>O(n V(d)+M S(d)+ TP(d)) =O(n V(d) + T(S(d)+P(d)) )</tex>, где <tex>V(d)</tex>, <tex>S(d)</tex> и <tex>P(d)</tex> это оценка времени работы оракулов <tt>VolumeQuery</tt>, <tt>SampleQuery</tt> и <tt>PointQuery</tt>, соответственно. Выберем <tex>\epsilon : \epsilon_s, \epsilon_p, \epsilon_v \leq \frac{\epsilon^2}{47n}</tex>. Если все используемые тела являются гиперпараллелепипедами, то время работы каждого из оракулов составляет в точности <tex>O(d)</tex>, таким образом алгоритм позволяет построить <tex>\epsilon</tex>-аппроксимацию гиперобъема с вероятностью <tex>\geq 3/4</tex> за время <tex>O(\frac{nd}{\epsilon^2})</tex>. = Примечания =Источники==
<references />
