MAX-SAT: дерандомизация/Задачи/ex-derand-maxsat-f0-f1 — различия между версиями
Материал из DISCOPAL
| Строка 8: | Строка 8: | ||
===Стенина Мария, группа 974=== | ===Стенина Мария, группа 974=== | ||
| − | |||
<latex> | <latex> | ||
| − | Организуем вычисления следующим образом. После получения решения задачи линейной релаксации $(p_1, \ldots, p_n)$ заполним две таблицы. Первую назовем $C$, она будет содержать $m$ строк и $n$ столбцов. Каждая строка будет соответствовать одной скобке. В ячейке $(j, k)$ будет записана 1, если в $j$-тую скобку входит $x_k$, 0, если в $j$-тую скобку входит $\bar{x}_k$, и | + | Организуем вычисления следующим образом. После получения решения задачи линейной релаксации $(p_1, \ldots, p_n)$ заполним две таблицы. Первую назовем $C$, она будет содержать $m$ строк и $n$ столбцов. Каждая строка будет соответствовать одной скобке. В ячейке $(j, k)$ будет записана 1, если в $j$-тую скобку входит $x_k$, 0, если в $j$-тую скобку входит $\bar{x}_k$, и None, если $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. | P_j = \prod_{k:C_{jk}=1} (1-p_k) \prod_{k:C_{jk}=0} p_k. | ||
| Строка 19: | Строка 18: | ||
$$ | $$ | ||
P^0 = P; | P^0 = P; | ||
| + | $$ | ||
| + | $$ | ||
| + | P^1 = P; | ||
$$ | $$ | ||
для всех $j = 1, \ldots, m$ | для всех $j = 1, \ldots, m$ | ||
| Строка 25: | Строка 27: | ||
$$ | $$ | ||
$$ | $$ | ||
| − | \text{если } C_{jk} = 1, \text{то } P^0_j = P^0_j / p_k; | + | \text{если } C_{jk} = 1, \text{то } P^0_j = P^0_j / (1 -p_k); |
$$ | $$ | ||
$$ | $$ | ||
| − | + | \text{если } C_{jk} = 1, \text{то } P^1_j = 0; | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | \text{если } C_{jk} = 1, \text{то } P^ | + | |
$$ | $$ | ||
$$ | $$ | ||
| − | \text{если } C_{jk} = 0, \text{то } P^ | + | \text{если } C_{jk} = 0, \text{то } P^1_j = P^0_j / p_k; |
$$ | $$ | ||
Все эти манипуляции занимают время $O(m)$. Далее | Все эти манипуляции занимают время $O(m)$. Далее | ||
| Строка 44: | Строка 42: | ||
Итого имеем заполнение двух таблиц за $O(nm)$ и $n$ итераций по $O(m)$, значит всего $O(nm)$, что и требовалось. | Итого имеем заполнение двух таблиц за $O(nm)$ и $n$ итераций по $O(m)$, значит всего $O(nm)$, что и требовалось. | ||
| + | |||
</latex> | </latex> | ||
Версия 13:33, 9 ноября 2014
Стенина Мария, группа 974