MAX-SAT: дерандомизация/Задачи/ex-derand-maxsat-f0-f1 — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 4: Строка 4:
 
</latex>
 
</latex>
  
−
[[Category:Нерешенные задачи]]
+
[[Category:На проверку]]
 
<!--Вообще-то, решения уже есть-->
 
<!--Вообще-то, решения уже есть-->
 +
 +
===Стенина Мария, группа 974===
 +
 +
<latex>
 +
Организуем вычисления следующим образом. После получения решения задачи линейной релаксации $(p_1, \ldots, p_n)$ заполним две таблицы. Первую назовем $C$, она будет содержать $m$ строк и $n$ столбцов. Каждая строка будет соответствовать одной скобке. В ячейке $(j, k)$ будет записана 1, если в $j$-тую скобку входит $x_k$, 0, если в $j$-тую скобку входит $\bar{x}_k$, и "-", если $k$-тая переменная не входит в $j$-тую скобку. Заполнение такой таблицы, очевидно, займет время $O(nm)$. Вторую таблицу назовем $P$, она будет содержать один столбец длины $m$. В каждой ячейке будет записана $P_j$, которую вычислим по формуле
 +
$$
 +
    P_j = \prod_{k:C_{jk}=1} (1-p_k) \prod_{k:C_{jk}=0} p_k.
 +
$$
 +
Заполнение этой таблицы тоже займет время не более $O(nm)$.
 +
 +
Далее на каждой итерации будем производить следующие действия. Обозначим номер итерации $k$.
 +
$$
 +
    P^0 = P;
 +
$$
 +
для всех $j = 1, \ldots, m$
 +
$$
 +
  \text{если } C_{jk} = 0, \text{то } P^0_j = 0;
 +
$$
 +
$$
 +
  \text{если } C_{jk} = 1, \text{то } P^0_j = P^0_j / p_k;
 +
$$
 +
$$
 +
    P^1 = P;
 +
$$
 +
для всех $j = 1, \ldots, m$
 +
$$
 +
  \text{если } C_{jk} = 1, \text{то } P^0_j = 0;
 +
$$
 +
$$
 +
  \text{если } C_{jk} = 0, \text{то } P^0_j = P^0_j / p_k;
 +
$$
 +
Все эти манипуляции занимают время $O(m)$. Далее
 +
$$
 +
    f_0 = \sum_{j=1}^m P^0_j, \quad f_1 = \sum_{j=1}^m P^1_j.
 +
$$
 +
Это тоже $O(m)$. Ну и наконец, если $f_0 < f_1$, то $P = P^0$, иначе $P = P^1$. Это можно реализовать за $O(1)$.
 +
 +
Итого имеем заполнение двух таблиц за $O(nm)$ и $n$ итераций по $O(m)$, значит всего $O(nm)$, что и требовалось.
 +
</latex>

Версия 13:21, 9 ноября 2014

Стенина Мария, группа 974

Источник — «https://discopal.ispras.ru/index.php?title=MAX-SAT:_дерандомизация/Задачи/ex-derand-maxsat-f0-f1&oldid=3180»