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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 37 промежуточных версий 3 участников)
Строка 1: Строка 1:
{{В разработке}}
+
[[Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем#Индикатор Гиперобъема| Определение гиперобъема]]
  
== Постановка задачи ==
+
Утверждается, что точное вычисление значения гиперобъема множества из <tex>n</tex> точек <tex>d</tex>-мерного пространства является [http://en.wikipedia.org/wiki/Sharp-P #P-трудной задачей], однако допускает эффективную аппроксимацию, а именно может быть аппроксимировано за
<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-трудной задачей], однако допускает эффективную аппроксимацию, а именно может быть аппроксимировано за
 
*полином от количество параметров,
 
 
*полином от количества решений,
 
*полином от количества решений,
 
*полином от качества аппроксимации.
 
*полином от качества аппроксимации.
  
 
== #P-трудность задачи вычисления гиперобъема ==
 
== #P-трудность задачи вычисления гиперобъема ==
Доказательство будет состоять в сведении задачи #MON-CNF (Satisfability problem for monotone boolean formulas).
 
 
 
{{Определение
 
{{Определение
|definition=задача #MON-CNF -- задача вычисления количества удовлетворяющих подстановок для монотонной булевой формулы, записанной в КНФ <tex>f = \bigwedge  \limits _{k=1}^n \bigvee_{i \in C_k} x_i</tex>
+
|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>
+
где все дизъюнкты <tex> C_k \subseteq {1,...,d}</tex>
 
}}
 
}}
  
Задача #MON-CNF является #P-трудной
+
{{Теорема
Сведем ее к задаче вычисления гиперобъема.
+
|statement= Задача вычисления гиперобъема принадлежит классу #P-трудных задач
для MON-CNF формулы
+
|proof= Суть доказательства состоит в сведении задачи #MON-CNF к задаче вычисления значения гиперобъема. Так как доказано
 +
<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>f = \bigwedge  \limits _{k=1}^n \bigvee_{i \in C_k} x_i</tex>
 
<tex>f = \bigwedge  \limits _{k=1}^n \bigvee_{i \in C_k} x_i</tex>
 +
меньше <tex>2^d</tex> на количество удовлетворяющих подстановок ее отрицания
 +
<tex> \overline{f} = \bigvee  \limits _{k=1}^n \bigwedge_{i \in C_k} \neg x_i</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> \overline{f} = \bigvee  \limits _{k=1}^n \bigwedge_{i \in C_k} \not x_i</tex>
 
 
 
и для каждого клоза <tex>\bigwedge_{i \in C_k} \neg x_i</tex> построим гиперкуб <tex>[0,a^k_1]\times...\times[0,a^k_d]</tex>
 
  
 
где  
 
где  
Строка 44: Строка 36:
 
  2 & \text{otherwise}
 
  2 & \text{otherwise}
 
\end{cases}
 
\end{cases}
</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>A_i</tex>
 +
 
 +
<tex> \iff\exists a^k_i \geq x_i + 1 : i \in d  \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}^n A_k )  = |\{(x_1,...,x_d) \in \{0,1\}^d| (x_1,...,x_d)</tex> удовлетворяет <tex>\overline{f} \}|</tex>
 +
 
 +
Таким образом произвели сведение, в значит задача вычисления гиперобъема принадлежит классу #P
 +
}}
 +
 
 +
==Эффективная аппроксимация нахождения значения гиперобъема==
 +
Приведем псевдокод алгоритма для аппроксимации гиперобъема объединения тел. В алгоритме, приведенном в
 +
<ref>
 +
Bringmann K., 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
 +
</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
 +
<tex> V' := \sum\limits_{i = 1}^n V'_i</tex>
 +
while <tex>C \leq T</tex> do
 +
  choose <tex>i \in [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 \in [n]</tex> uniformly
 +
  C := C + 1
 +
  until PointQuery (x, <tex>B_j</tex>)
 +
  M := M + 1
 +
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>C_1 = \{x\}</tex> будет соответствовать клоз <tex>\neg x_1</tex>
+
Если все используемые тела являются гиперпараллелепипедами, то время работы каждого из оракулов составляет в точности <tex>O(d)</tex>, таким образом алгоритм позволяет построить <tex>\epsilon</tex>-аппроксимацию гиперобъема с вероятностью <tex>\geq 3/4</tex> за время <tex>O(\frac{nd}{\epsilon^2})</tex>.
  
а <tex>C_2 = \{1,2\}</tex> клоз <tex>\neg x_1 \wedge \neg x_2</tex>
+
==Источники==
 +
<references />

Текущая версия на 19:37, 4 сентября 2022

Определение гиперобъема

Утверждается, что точное вычисление значения гиперобъема множества из [math]n[/math] точек [math]d[/math]-мерного пространства является #P-трудной задачей, однако допускает эффективную аппроксимацию, а именно может быть аппроксимировано за

  • полином от количества параметров,
  • полином от количества решений,
  • полином от качества аппроксимации.

#P-трудность задачи вычисления гиперобъема

Определение:
Задача #MON-CNF (Satisfability problem for monotone boolean formulas) — задача вычисления количества удовлетворяющих подстановок для монотонной булевой формулы, записанной в КНФ [math]f = \bigwedge \limits _{k=1}^n \bigvee_{i \in C_k} x_i[/math], где все дизъюнкты [math] C_k \subseteq {1,...,d}[/math]


Теорема:
Задача вычисления гиперобъема принадлежит классу #P-трудных задач
Доказательство:
[math]\triangleright[/math]

Суть доказательства состоит в сведении задачи #MON-CNF к задаче вычисления значения гиперобъема. Так как доказано [1] , что #MON-CNF является #P-трудной, то это докажет теорему.

Количество удовлетворяющих подстановок функции [math]f = \bigwedge \limits _{k=1}^n \bigvee_{i \in C_k} x_i[/math] меньше [math]2^d[/math] на количество удовлетворяющих подстановок ее отрицания [math] \overline{f} = \bigvee \limits _{k=1}^n \bigwedge_{i \in C_k} \neg x_i[/math] . Для упрощения вычислений далее будем работать с [math]\overline{f}[/math].

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

где

[math] a^k_i = \begin{cases} 1 & \text{if } i \in C_k \\ 2 & \text{otherwise} \end{cases} [/math].

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

Более того, из-за целочисленности вершин [math]A_i[/math], каждый из этих гиперкубов лежит в хотя бы одном из [math]A_i[/math]

[math] B_{x_1,...,x_d} \subset \bigcup \limits _{k = 1}^n A_k \iff B_{x_1,...,x_d} \subset A_k \iff[/math]

А значит из определения [math]A_i[/math]

[math] \iff\exists a^k_i \geq x_i + 1 : i \in d \iff[/math]

[math]\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) [/math] удовлетворяет [math]\bigwedge_{i \in C_k} \neg x_i[/math] для некоторого [math]k \iff (x_1,...,x_d)[/math] удовлетворяет [math]\overline{f}[/math]

Заметим, что так как [math]\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)[/math] удовлетворяет [math]\overline{f} \}|[/math]

Таким образом произвели сведение, в значит задача вычисления гиперобъема принадлежит классу #P
[math]\triangleleft[/math]

Эффективная аппроксимация нахождения значения гиперобъема

Приведем псевдокод алгоритма для аппроксимации гиперобъема объединения тел. В алгоритме, приведенном в [2] используются три оракула: PointQuery, VolumeQuery и SampleQuery, каждый из которых ошибается с вероятностью [math]\epsilon_p, \epsilon_v[/math] и [math]\epsilon_s[/math] соответственно.

Оракул

  • PointQuery(x,B) возвращает true, если точка [math]x[/math] лежит внутри [math] B[/math].
  • VolumeQuery(B) возвращает объем заданного тела [math]B[/math].
  • SampleQuery(B) для заданного тела [math]B[/math] возвращает произвольную его точку [math]x \in B[/math].


Для данного алгоритма допускаются следующие ослабления этих оракулов:

  • PointQuery(x,B) возвращает true для всех точек из некоторого тела [math] B' : \mu ((B' \backslash B) \cup (B \backslash B'))\leq \epsilon_p \mu(B)[/math]
  • VolumeQuery(B) возвращает значение [math]V' : (1-\epsilon_v)\mu(B) \leq V' \leq (1+\epsilon_v)\mu(B)[/math]
  • SampleQuery(B) возвращает произвольную точку из тела [math]B' : |f(x) - 1/\mu(B')| \lt \epsilon_s [/math]
M := 0; C := 0;
[math] \overline \epsilon := \frac{\epsilon - \epsilon_v}{1+ \epsilon_v} [/math]
[math] \overline C := \frac{(1+\epsilon_s)(1+\epsilon_v)(1+\epsilon_p)}{(1-\epsilon_v)(1-\epsilon_p)}[/math]
[math] T := \frac{24 ln (2) (1 + \overline \epsilon) n}{\overline \epsilon^2 - 8 (\overline C - 1) n}[/math]
for all [math]B_i \in S[/math] do
 compute [math]V'_i[/math] := VolumeQuery([math]B_i[/math])
od
[math] V' := \sum\limits_{i = 1}^n V'_i[/math]
while [math]C \leq T[/math] do
 choose [math]i \in [n] [/math] with probability [math]\frac{V'_i}{V'}[/math]
 x := SampleQuery([math]B_i[/math])
 repeat 
  if (C > T) then return [math]\frac {TV'}{nM} [/math]
  choose random [math]j \in [n][/math] uniformly
  C := C + 1
 until PointQuery (x, [math]B_j[/math])
 M := M + 1
od
return [math]\frac{TV'}{nM}[/math]

Время работы алгоритма составляет

[math]O(n V(d)+M S(d)+ TP(d)) = O(n V(d) + T(S(d)+P(d)) )[/math],

где [math]V(d)[/math], [math]S(d)[/math] и [math]P(d)[/math] это оценка времени работы оракулов VolumeQuery, SampleQuery и PointQuery, соответственно.

Выберем [math]\epsilon : \epsilon_s, \epsilon_p, \epsilon_v \leq \frac{\epsilon^2}{47n}[/math].

Если все используемые тела являются гиперпараллелепипедами, то время работы каждого из оракулов составляет в точности [math]O(d)[/math], таким образом алгоритм позволяет построить [math]\epsilon[/math]-аппроксимацию гиперобъема с вероятностью [math]\geq 3/4[/math] за время [math]O(\frac{nd}{\epsilon^2})[/math].

Источники

  1. Roth D. On the hardness of approximate reasoning, Artif. Intell., 82: 273–302, 1996, http://cogcomp.cs.illinois.edu/papers/hardJ.pdf
  2. Bringmann K., 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